not alma - Memoization

Olarak işlem , memoization veya memoisation bir bir optimizasyon hızlandırmak için temel olarak kullanılan teknik bilgisayar programları pahalı sonuçlarını saklayarak fonksiyon çağrısı aynı girişler tekrar ortaya çıktığında önbelleğe sonucu geri gönderilmesi. Notlandırma, basit karşılıklı özyinelemeli iniş ayrıştırma gibi başka bağlamlarda da (ve hız kazanımları dışındaki amaçlar için) kullanılmıştır . Önbelleğe alma ile ilgili olmasına rağmen , not alma , bu optimizasyonun belirli bir durumunu ifade eder ve onu arabelleğe alma veya sayfa değiştirme gibi önbelleğe alma biçimlerinden ayırır . Bazı mantıksal programlama dilleri bağlamında , memoization, tablolama olarak da bilinir .

etimoloji

"Memoization" terimi , 1968'de Donald Michie tarafından icat edildi ve Latince " memorandum " ("hatırlanacak") kelimesinden türetildi , genellikle Amerikan İngilizcesinde "not" olarak kısaltıldı ve bu nedenle "dönüş" anlamını taşıyor. Sonuçları] bir işlevin hatırlanacak bir şeye dönüşmesi". "Memoization", " ezberleme " ile karıştırılabilirken (çünkü bunlar etimolojik kökenlidir ), "not alma", hesaplamada özel bir anlama sahiptir.

genel bakış

Hafızaya alınmış bir fonksiyon, bazı özel girdi setlerine karşılık gelen sonuçları "hatırlar". Hatırlanan girdileri olan müteakip çağrılar, yeniden hesaplamak yerine hatırlanan sonucu döndürür, böylece verilen parametrelere sahip bir çağrının birincil maliyetini, bu parametrelerle işleve yapılan ilk çağrı dışında hepsinden elimine eder. Hatırlanan ilişkilendirmeler kümesi, işlevin doğasına ve kullanımına bağlı olarak, bir değiştirme algoritması tarafından kontrol edilen sabit boyutlu bir küme veya sabit bir küme olabilir. Bir işlev yalnızca referans olarak şeffafsa not alınabilir ; yani, yalnızca işlevi çağırmak, o işlev çağrısını dönüş değeriyle değiştirmekle tam olarak aynı etkiye sahipse. (Ancak, bu kısıtlamaya yönelik özel durum istisnaları mevcuttur.) Arama tablolarıyla ilgili olsa da , memoization uygulamasında bu tür tabloları sıklıkla kullandığından, memoization, önceden değil, gerektiğinde anında sonuç önbelleğini şeffaf bir şekilde doldurur.

Memoization, alan maliyeti karşılığında bir işlevin zaman maliyetini düşürmenin bir yoludur ; yani, hafızaya alınan işlevler , bilgisayar bellek alanının daha yüksek kullanımı karşılığında hız için optimize edilir . Algoritmaların zaman/mekan "maliyeti", hesaplamada belirli bir ada sahiptir: hesaplama karmaşıklığı . Tüm işlevlerin zaman içinde (yani yürütülmesi zaman alır) ve uzayda bir hesaplama karmaşıklığı vardır .

Bir uzay-zaman değiş tokuşu meydana gelse de (yani, kullanılan alan kazanılan hızdır), bu, güç azaltma gibi zaman-mekan değiş tokuşunu içeren diğer bazı optimizasyonlardan farklıdır, çünkü notlandırma derleme zamanı yerine bir çalışma zamanıdır. optimizasyon. Ayrıca, mukavemet azaltma potansiyel olarak çarpma gibi maliyetli bir işlemi toplama gibi daha az maliyetli bir işlemle değiştirir ve tasarruf sonuçları makineye oldukça bağımlı olabilir (makineler arasında taşınabilir değildir), oysa not alma daha makineden bağımsız, çapraz -platform stratejisi.

Aşağıdaki düşünün pseudocode hesaplamak için işlevini çarpınımını ait n :

function factorial (n is a non-negative integer)
    if n is 0 then
        return 1 [by the convention that 0! = 1]
    else
        return factorial(n – 1) times n [recursively invoke factorial 
                                        with the parameter 1 less than n]
    end if
end function

Her için tamsayı , n şekilde n ≥ 0fonksiyonunun son sonucu, factorialbir değişmez ; olarak çağrıldığında x = factorial(3), sonuç şekildedir X olacak zaman doğası göz önüne alındığında, sigara memoized gerçeklemenin değeri 6. atanabilir özyinelemeli gerektirecektir, ilgili algoritma , n + 1 ve çağrıları factorialbir sonucu elde etmek için, her biri ve bu çağrılar, işlevin hesaplanan değeri döndürmesi için gereken süre içinde ilişkili bir maliyete sahiptir. Makineye bağlı olarak, bu maliyet aşağıdakilerin toplamı olabilir:

  1. İşlevsel çağrı yığını çerçevesini kurma maliyeti.
  2. n ile 0'ı karşılaştırmanın maliyeti .
  3. n'den 1'i çıkarmanın maliyeti .
  4. Özyinelemeli çağrı yığını çerçevesini kurma maliyeti. (Yukarıdaki gibi.)
  5. Maliyet için özyinelemeli aramanın sonucunu çoğalmaya factorialtarafından n .
  6. Çağıran bağlam tarafından kullanılabilecek şekilde dönüş sonucunu saklama maliyeti.

Notlandırılmamış bir uygulamada, her üst düzey çağrı factorial, n'nin başlangıç ​​değeriyle orantılı olarak 2'den 6'ya kadar olan adımların kümülatif maliyetini içerir .

factorialFonksiyonun hafızaya alınmış bir versiyonu aşağıdaki gibidir:

function factorial (n is a non-negative integer)
    if n is 0 then
        return 1 [by the convention that 0! = 1]
    else if n is in lookup-table then
        return lookup-table-value-for-n
    else
        let x = factorial(n – 1) times n [recursively invoke factorial
                                         with the parameter 1 less than n]
        store x in lookup-table in the nth slot [remember the result of n! for later]
        return x
    end if
end function

Bu özel örnekte, factorialönce 5 ile çağrılırsa ve daha sonra beşe eşit veya daha küçük herhangi bir değerle çağrılırsa, bu dönüş değerleri de factorial5, 4, 3, 2, 1 ve 0 ve bunların her birinin dönüş değerleri saklanmış olacaktır. Daha sonra 7 gibi 5'ten büyük bir numara ile aranırsa, yalnızca 2 özyinelemeli arama yapılır (7 ve 6) ve 5 değeri! önceki aramadan kaydedilmiş olacaktır. Bu şekilde, memoization, bir fonksiyonun ne kadar sık ​​çağrılırsa o kadar zaman açısından verimli hale gelmesine izin verir ve böylece nihai genel hızlanma ile sonuçlanır.

Diğer bazı hususlar

Fonksiyonel programlama

Memoization, derleyicilerde , genellikle adla çağrı değerlendirme stratejisini kullanan işlevsel programlama dilleri için yoğun bir şekilde kullanılır . Argüman değerlerini hesaplarken ek yükü önlemek için, bu diller için derleyiciler , argüman değerlerini hesaplamak için thunks adı verilen yardımcı işlevleri yoğun bir şekilde kullanır ve tekrarlanan hesaplamaları önlemek için bu işlevleri not alır.

Otomatik not alma

Notlandırma, bir bilgisayar programcısı tarafından dahili ve açık bir şekilde fonksiyonlara yukarıdaki notlandırılmış versiyonun uygulandığı şekilde eklenebilirken , referans olarak şeffaf fonksiyonlar da otomatik olarak harici olarak not alınabilir . Peter Norvig tarafından kullanılan tekniklerin yalnızca Common Lisp'te (makalesinin otomatik not almayı gösterdiği dil) değil, aynı zamanda çeşitli diğer programlama dillerinde de uygulaması vardır . Otomatik not alma uygulamaları, terim yeniden yazma ve yapay zeka çalışmalarında resmi olarak araştırılmıştır . factorial

Fonksiyonların birinci sınıf nesneler olduğu programlama dillerinde ( Lua , Python veya Perl gibi ), belirli bir küme için bir değer hesaplandıktan sonra bir fonksiyonun hesaplanan değeriyle (çalışma zamanında) değiştirilerek otomatik notlandırma uygulanabilir. parametreler. Bu işlev nesnesi için değer değiştirmeyi yapan işlev, genel olarak herhangi bir başvurusal olarak saydam işlevi sarabilir. Aşağıdaki sözde kodu göz önünde bulundurun (işlevlerin birinci sınıf değerler olduğu varsayıldığında):

function memoized-call (F is a function object parameter)
    if F has no attached array values then
        allocate an associative array called values;
        attach values to F;
    end if;
    if F.values[arguments] is empty then
        F.values[arguments] = F(arguments);
    end if;
    return F.values[arguments];
end function

Doğrudan factorialçağırmak yerine, yukarıdaki stratejiyi kullanmanın otomatik olarak not alınmış bir sürümünü çağırmak için factorialkod çağırır . Bu tür çağrıların her biri, önce sonuçları depolamak için bir tutucu dizisinin ayrılıp ayrılmadığını kontrol eder ve değilse, bu diziyi ekler. Konumda ( ilişkisel dizinin anahtarı olarak kullanılırlar) herhangi bir giriş yoksa , sağlanan argümanlarla gerçek bir çağrı yapılır . Son olarak, dizideki anahtar konumundaki giriş, arayana döndürülür. memoized-call(factorial(n))values[arguments]argumentsfactorial

Yukarıdaki strateji , not edilecek bir işleve yapılan her çağrıda açık bir şekilde sarmalamayı gerektirir . Kapanışlara izin veren bu dillerde, not alma, bir dekoratör deseninde sarılmış, not alınmış bir işlev nesnesi döndüren bir işlev fabrikası aracılığıyla dolaylı olarak gerçekleştirilebilir . Sözde kodda bu şu şekilde ifade edilebilir:

function construct-memoized-functor (F is a function object parameter)
    allocate a function object called memoized-version;
    let memoized-version(arguments) be
        if self has no attached array values then [self is a reference to this object]
            allocate an associative array called values;
            attach values to self;
        end if;

        if self.values[arguments] is empty then
            self.values[arguments] = F(arguments);
        end if;

        return self.values[arguments];
    end let;
    return memoized-version;
end function

call yerine aşağıdaki gibi factorialyeni bir işlev nesnesi memfactoluşturulur:

 memfact = construct-memoized-functor(factorial)

Yukarıdaki örnek , çağrı yapılmadan önce işlevin factorialzaten tanımlandığını varsayar . Bu noktadan itibaren, n'nin faktöriyeli istendiğinde çağrılır . Lua gibi dillerde, bir fonksiyonun aynı ada sahip yeni bir fonksiyonla değiştirilmesine izin veren daha karmaşık teknikler mevcuttur; construct-memoized-functormemfact(n)

 factorial = construct-memoized-functor(factorial)

Esasen, bu tür teknikler, aşağıda gösterildiği gibi, orijinal işlev nesnesini oluşturulan işleve eklemeyi ve gerçek işleve bir çağrı gerektiğinde (sonsuz özyinelemeyi önlemek için ) bir takma ad aracılığıyla not alınan orijinal işleve çağrıları iletmeyi içerir :

function construct-memoized-functor (F is a function object parameter)
    allocate a function object called memoized-version;
    let memoized-version(arguments) be
        if self has no attached array values then [self is a reference to this object]
            allocate an associative array called values;
            attach values to self;
            allocate a new function object called alias;
            attach alias to self; [for later ability to invoke F indirectly]
            self.alias = F;
        end if;

        if self.values[arguments] is empty then
            self.values[arguments] = self.alias(arguments); [not a direct call to F]
        end if;

        return self.values[arguments];
    end let;
    return memoized-version;
end function

(Not: Yukarıda gösterilen adımlardan bazıları, uygulama dili tarafından dolaylı olarak yönetilebilir ve örnek olarak verilmiştir.)

ayrıştırıcılar

Bir zaman yukarıdan aşağıya ayrıştırıcı çalışır bir ayrıştırmak için belirsiz belirsiz göre girişini serbest içerik (CFG), bu CFG tüm alternatifleri denemek için (giriş uzunluğuna göre) adımlarının üstel sayıda gerekebilir olası tüm ayrıştırma ağaçlarını üretmek için. Bu sonuçta üstel bellek alanı gerektirecektir. Notlandırma, 1991 yılında , Earley'nin algoritmasındaki (1970) dinamik programlama ve durum kümelerinin kullanımına benzer bir algoritmanın ve Cocke, Younger ve Kasami'nin CYK algoritmasındaki tabloların kullanımına benzer bir algoritmanın, Peter Norvig tarafından bir ayrıştırma stratejisi olarak keşfedildi. üstel zaman karmaşıklığı problemini çözmek için basit bir geri izleme özyinelemeli iniş ayrıştırıcısına otomatik notlandırma getirilerek oluşturulabilir . Norvig'in yaklaşımındaki temel fikir, girdiye bir ayrıştırıcı uygulandığında, aynı ayrıştırıcı aynı girdiye yeniden uygulanırsa, sonucun sonraki yeniden kullanım için bir not defterinde saklanmasıdır. Richard Frost ayrıca , “Tamamen İşlevsel Yukarıdan Aşağıya Geri İzleme” ayrıştırma tekniği olarak görülebilen ayrıştırıcı birleştiricilerin üstel zaman karmaşıklığını azaltmak için notlandırma kullandı . Temel notlandırılmış ayrıştırıcı birleştiricilerin, CFG'lerin yürütülebilir özellikleri olarak karmaşık ayrıştırıcılar oluşturmak için yapı taşları olarak kullanılabileceğini gösterdi. 1995 yılında Johnson ve Dörre tarafından ayrıştırma bağlamında yeniden keşfedildi. 2002 yılında Ford tarafından packrat parsing adı verilen formda oldukça derinlemesine incelenmiştir .

2007'de Frost, Hafız ve Callaghan, polinom zamanında herhangi bir belirsiz CFG formunu yerleştirmek için fazlalık hesaplamalardan kaçınmak için notlandırma kullanan yukarıdan aşağıya bir ayrıştırma algoritması tanımladılar ( Θ (n 4 ) sol özyinelemeli dilbilgileri için ve Θ(n 3 ) için sol özyinelemeli olmayan gramerler). Yukarıdan aşağıya ayrıştırma algoritmaları ayrıca, 'kompakt temsil' ve 'yerel belirsizlik gruplandırma' yoluyla potansiyel olarak üstel belirsiz ayrıştırma ağaçları için polinom alanı gerektirir. Kompakt gösterimleri, Tomita'nın aşağıdan yukarıya ayrıştırmanın kompakt gösterimi ile karşılaştırılabilir . Bunların memoization kullanımı, bir ayrıştırıcı aynı giriş konumuna tekrar tekrar uygulandığında (polinom zaman gereksinimi için esastır) daha önce hesaplanan sonuçların alınmasıyla sınırlı değildir; aşağıdaki ek görevleri gerçekleştirmek için uzmanlaşmıştır:

  • Notlandırma işlemi (herhangi bir ayrıştırıcı yürütme etrafında bir 'sarmalayıcı' olarak görülebilir) , giriş uzunluğuna ve mevcut giriş konumuna göre derinlik kısıtlamaları uygulayarak sürekli büyüyen bir doğrudan sol özyinelemeli ayrıştırmayı barındırır.
  • Algoritmanın not tablosu 'arama' prosedürü, kaydedilen sonucun hesaplama bağlamını ayrıştırıcının mevcut bağlamıyla karşılaştırarak kaydedilen bir sonucun yeniden kullanılabilirliğini de belirler. Bu bağlamsal karşılaştırma, dolaylı (veya gizli) sol özyinelemeyi barındırmanın anahtarıdır .
  • Bir memotable'da başarılı bir arama gerçekleştirirken, tam sonuç kümesini döndürmek yerine, süreç yalnızca gerçek sonucun referanslarını döndürür ve sonunda genel hesaplamayı hızlandırır.
  • Memotable'ın güncellenmesi sırasında, memoization işlemi (potansiyel olarak üstel) belirsiz sonuçları gruplandırır ve polinom alan gereksinimini sağlar.

Frost Hafız ve Callaghan da bir dizi olarak PADL'08 algoritmanın uygulanmasını tarif yüksek sıralı işlevler (denilen ayrıştırıcı combinators olarak) Haskell'e dil işlemci olarak CFGS doğrudan yürütülebilir özellikleri yapımını sağlar. Polinom algoritmalarının yukarıdan aşağıya ayrıştırma ile 'herhangi bir belirsiz CFG biçimini' barındırma gücünün önemi, doğal dil işleme sırasında sözdizimi ve anlambilim analizi açısından hayati önem taşımaktadır . X-Saiga sitesi algoritması ve uygulama detayları hakkında daha vardır.

Norvig , not alma yoluyla ayrıştırıcının gücünü artırırken, artırılmış ayrıştırıcı hala Earley algoritması kadar zaman karmaşıktı; bu, notlandırmanın hız optimizasyonundan başka bir şey için kullanıldığını gösteren bir durumu gösteriyor. Johnson ve Dörre, hız ile ilgili olmayan bir başka memoization uygulamasını göstermektedir: dilsel kısıtlama çözümlemesini, bu kısıtlamaları çözmek için yeterli bilginin toplandığı bir ayrıştırmada bir noktaya geciktirmek için memoization kullanımı. Buna karşılık, not almanın hız optimizasyonu uygulamasında, Ford, not almanın, en kötü durumda geri izleme davranışıyla sonuçlanan dillerde bile , ayrıştırma ifade dilbilgilerinin doğrusal zamanda ayrıştırılabileceğini garanti edebileceğini gösterdi .

Aşağıdaki dilbilgisini göz önünde bulundurun :

S → (A c) | (B d)
A → X (a|b)
B → X b
X → x [X]

(Gösterim Not: Yukarıdaki örnekte, üretim S → (A c ) | (B D ) yer alan "bir S bir ya olan bir a, ardından c ya da B bir takiben d ." Üretim X → x [ X], " X , x'tir ve ardından isteğe bağlı bir X'tir .")

Bu dilbilgisi aşağıdaki üç varyasyonlarının birini oluşturur dizge : XAC , XBc veya XBd ( x ortalama anlaşılır burada bir veya daha fazla X 'in düşünün sonraki.) Kadar bir ayrıştırma özellikleri, kudreti etkilenerek olarak kullanılan bu gramer, xxxxxbd dizesinin yukarıdan aşağıya, soldan sağa ayrıştırılması :

Kural bir tanıyacak xxxxxb (içine ilk olarak azalan ile X bir tanıma x ve yeniden inen X tüm kadar X 'in tüketildiği ve daha sonra kabul b ) ve daha sonra geri S ve tanımak için başarısız c . Bir sonraki maddesi S , sonra da B, içine inecek tekrar iner X ve tanır X 'bir çok özyinelemeli çağrıları aracılığıyla s X , ve daha sonra bir b için ve dönüş S ve son olarak bir kabul d .

Buradaki anahtar kavram, tabirde doğasında bulunan yine X'e iner . İleriye bakma, başarısız olma, yedekleme ve ardından bir sonraki alternatifi yeniden deneme süreci, ayrıştırmada geri izleme olarak bilinir ve ayrıştırmada not alma için fırsatlar sunan öncelikle geri izlemedir. RuleAcceptsSomeInput(Rule, Position, Input)Parametrelerin aşağıdaki gibi olduğu bir fonksiyon düşünün :

  • Rule incelenen kuralın adıdır.
  • Position girdide şu anda dikkate alınan ofsettir.
  • Input dikkate alınan girdidir.

İşlevin dönüş değeri, RuleAcceptsSomeInputtarafından kabul edilen girişin uzunluğu olsun Ruleveya bu kural dizedeki o ofsette herhangi bir girişi kabul etmiyorsa 0 olsun. Bu tür bir memoization içeren bir geri izleme senaryosunda, ayrıştırma işlemi aşağıdaki gibidir:

Kural zaman bir iner X de ofset 0, bu konum ve kural karşı uzunluğu 5 memoizes X . d ' de başarısız olduktan sonra , B , tekrar X'e inmek yerine, notlandırma motorundaki kural X'e karşı 0 konumunu sorgular ve 5 uzunluğunda döndürülür, böylece aslında tekrar X'e inmekten kurtarılır ve şu şekilde devam eder: daha önce olduğu kadar çok kez X'e inmiş olsaydı .

Yukarıdaki örnekte, xxxxxxxxxxxxxxxxbd gibi dizelere izin vererek X'e bir veya daha fazla iniş meydana gelebilir . Aslında, söz konusu olabilir herhangi bir sayıda ve x daha önce 's b . Olduğu gibi S çağrı yinelemeli defalarca olarak X iner gerekir iken x 'ler, B dönüş değeri beri hiç X içine inerek zorunda kalmayacaksınız (bu özel durumda) 16 olacaktır. RuleAcceptsSomeInput(X, 0, xxxxxxxxxxxxxxxxbd)

Sözdizimsel yüklemleri kullanan ayrıştırıcılar ayrıca yüklem ayrıştırmalarının sonuçlarını da not alabilir, böylece aşağıdaki gibi yapıları azaltır:

S → (A)? A
A → /* some rule */

A'ya bir iniş için .

Bir ayrıştırıcı bir ayrıştırma sırasında bir ayrıştırma ağacı oluşturursa , yalnızca belirli bir kurala göre belirli bir uzaklıkta eşleşen girdinin uzunluğunu değil , aynı zamanda o kural tarafından oluşturulan alt ağacı, giriş, çünkü ayrıştırıcı tarafından kurala yapılan sonraki çağrılar aslında inmeyecek ve o ağacı yeniden oluşturmayacaktır. Aynı nedenle, bir kural eşleştiğinde harici koda (bazen semantik eylem rutini olarak da adlandırılır) çağrılar üreten notlandırılmış ayrıştırıcı algoritmaları, bu tür kuralların öngörülebilir bir sırada çağrılmasını sağlamak için bir şema kullanmalıdır.

Herhangi bir geri izleme veya sözdizimsel yüklem yeteneğine sahip ayrıştırıcı için, her dilbilgisi geri izleme veya yüklem kontrollerine ihtiyaç duymayacağından , her kuralın ayrıştırma sonuçlarını girdideki her ofset karşısında depolamanın (ve ayrıştırma işlemi bunu dolaylı olarak yapıyorsa ayrıştırma ağacını depolamanın) ek yükü olabilir. aslında bir ayrıştırıcıyı yavaşlatır . Bu etki, ayrıştırıcının ezberleyeceği kuralların açıkça seçilmesiyle hafifletilebilir.

Ayrıca bakınız

Referanslar

Dış bağlantılar

Çeşitli programlama dillerinde not alma örnekleri