Memoization - Memoization

İle karıştırılmaması gereken Ezberleme.
"Tablo" buraya yönlendirir. Parlamento prosedürü için bkz. Tablo (meclis prosedürü).

İçinde bilgi işlem, hafızaya alma veya ezber bir optimizasyon öncelikle hızlandırmak için kullanılan teknik bilgisayar programları pahalı sonuçları saklayarak işlev çağrıları ve aynı girdiler tekrar ortaya çıktığında önbelleğe alınmış sonucu döndürmek. Hafızaya alma aynı zamanda diğer bağlamlarda da (ve hız kazanımları dışındaki amaçlar için) kullanılmıştır. karşılıklı yinelemeli iniş ayrıştırma.[1] İlgili olmasına rağmen Önbelleğe almak not alma, bu optimizasyonun belirli bir durumunu ifade eder ve onu aşağıdaki gibi önbelleğe alma biçimlerinden ayırır. tamponlama veya sayfa değiştirme. Bazıları bağlamında mantık programlama diller, not alma olarak da bilinir masa.[2]

Etimoloji

"Memoization" terimi, Donald Michie 1968'de[3] ve türetilmiştir Latince kelime "muhtıra "(" hatırlanacak "), Amerikan İngilizcesinde genellikle" not "olarak kısaltılır ve bu nedenle" bir işlevin [sonuçlarını] hatırlanacak bir şeye dönüştürmenin "anlamını taşır." Hafızaya alma "ile karıştırılabilirken"ezberleme "(çünkü bunlar etimolojik soydaşlar ), "hafızaya alma", hesaplamada özel bir anlama sahiptir.

Genel Bakış

Belleğe alınmış bir işlev, bazı belirli girişlere karşılık gelen sonuçları "hatırlar". Hatırlanan girdilere sahip sonraki çağrılar, yeniden hesaplamak yerine hatırlanan sonucu döndürür, böylece verilen parametrelerle bir çağrının birincil maliyetini, bu parametrelerle işleve yapılan ilk çağrı hariç tümünden ortadan kaldırır. Hatırlanan ilişkilendirmeler kümesi, işlevin doğasına ve kullanımına bağlı olarak bir değiştirme algoritması veya sabit bir küme tarafından kontrol edilen sabit boyutlu bir küme olabilir. Bir işlev yalnızca, referans olarak şeffaf; yani, yalnızca işlevi çağırmak, işlev çağrısını kendi dönüş değeriyle değiştirmekle tam olarak aynı etkiye sahipse. (Bununla birlikte, bu kısıtlamanın özel durum istisnaları mevcuttur.) arama tabloları, notlandırma uygulamasında genellikle bu tür tabloları kullandığından, not alma, sonuçların önbelleğini önceden değil, gerektiğinde şeffaf bir şekilde anında doldurur.

Memoization, bir işlevin değerini düşürmenin bir yoludur. zaman karşılığında maliyet Uzay maliyet; yani, hafızaya alınmış işlevler şunlar için optimize edilir: hız daha yüksek bir kullanım karşılığında bilgisayar hafızası Uzay. Zaman / mekan "maliyeti" algoritmalar bilgi işlemde belirli bir adı vardır: hesaplama karmaşıklığı. Tüm işlevlerin hesaplama karmaşıklığı vardır. zaman (yani yürütmek için zaman alırlar) ve Uzay.

Bir uzay-zaman değiş tokuşu (yani, kullanılan alan hız kazanılır), bu, zaman-uzay değiş tokuşunu içeren diğer bazı optimizasyonlardan farklıdır, örneğin güç azalması, bu notta bir Çalışma süresi ziyade Derleme zamanı optimizasyon. Dahası, mukavemet azaltma potansiyel olarak çarpma gibi maliyetli bir işlemin yerine ekleme gibi daha az maliyetli bir işlemle yer değiştirir ve tasarrufla elde edilen sonuçlar oldukça yüksek olabilir. makineye bağımlı (makinelerde taşınabilir değildir), oysa hafızaya alma daha makineden bağımsızdır, çapraz platform strateji.

Aşağıdakileri göz önünde bulundur sözde kod hesaplama işlevi faktöryel nın-nin n:

işlev faktörlü (n negatif olmayan bir tam sayıdır) eğer n 0 ise 1 döndür [kongre ile 0! = 1] aksi takdirde faktöriyel dön (n - 1) kez n [yinelemeli olarak faktöriyel çağır                                         1 parametresi n'den küçük] ifend işlevini sonlandır

Her biri için tamsayı n öyle ki n≥0, fonksiyonun nihai sonucu faktöryel dır-dir değişmez; olarak çağrılırsa x = faktöryel (3), sonuç öyle ki x niyet her zaman 6. değeri atanmalıdır. Yukarıdaki hafızaya alınmamış uygulama, yinelemeli dahil olan algoritma, n + 1 Çağrılar faktöryel bir sonuca varmak için ve bu çağrıların her biri, fonksiyonun hesaplanan değeri döndürmesi için geçen sürede ilişkili bir maliyete sahiptir. Makineye bağlı olarak, bu maliyet aşağıdakilerin toplamı olabilir:

  1. İşlevsel çağrı yığını çerçevesini kurmanın maliyeti.
  2. Karşılaştırma maliyeti n 0'a kadar.
  3. 1'den 1'i çıkarma maliyeti n.
  4. Özyinelemeli çağrı yığını çerçevesini kurmanın maliyeti. (Yukarıdaki gibi.)
  5. Özyinelemeli çağrının sonucunu çarpmanın maliyeti faktöryel tarafından n.
  6. Geri dönüş sonucunu, arama bağlamı tarafından kullanılabilmesi için saklama maliyeti.

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

Hafızaya alınmış bir versiyonu faktöryel fonksiyon aşağıdaki gibidir:

fonksiyon faktöryel (n negatif olmayan bir tam sayıdır) eğer n 0 ise 1 döndür [kongre ile 0! = 1] else if n içinde arama tablosu sonra geri dön n için arama tablosu değeri    aksi halde x = faktöryel (n - 1) kez olsun n [özyinelemeli olarak faktöriyel çağır                                         1 parametresi n'den küçük] mağaza x içinde arama tablosu içinde ninci slot [n'nin sonucunu hatırla! sonrası için] x end ifend işlevi döndür

Bu özel örnekte, eğer faktöryel ilk olarak 5 ile çağrılır ve daha sonra beşten küçük veya ona eşit herhangi bir değerle çağrılırsa, bu dönüş değerleri de hafızaya alınmış olacaktır, çünkü faktöryel 5, 4, 3, 2, 1 ve 0 değerleri ve dönüş değerleri ile özyinelemeli olarak çağrılacaktır. her biri bunlardan depolanmış olacak. Daha sonra 7 gibi 5'ten büyük bir sayı ile çağrılırsa, sadece 2 özyinelemeli çağrı yapılacaktır (7 ve 6) ve 5! önceki aramadan kaydedilmiş olacak. Bu şekilde, hafızaya alma, bir işlevin ne kadar sık ​​çağrılırsa o kadar zaman verimli hale gelmesine izin verir ve böylece sonuçta genel hızlanma sağlanır.

Diğer bazı hususlar

Fonksiyonel programlama

Ana makale: Thunk § Fonksiyonel programlama

Memoization, derleyicilerde yoğun olarak kullanılır. fonksiyonel programlama sıklıkla kullanılan diller isimle aramak değerlendirme stratejisi. Bağımsız değişken değerlerinin hesaplanmasında ek yükten kaçınmak için, bu diller için derleyiciler ağırlıklı olarak adı verilen yardımcı işlevleri kullanır. thunks argüman değerlerini hesaplamak ve tekrarlanan hesaplamaları önlemek için bu fonksiyonları hafızaya almak.

Otomatik not alma

İşlevlere not eklenebilirken dahili olarak ve açıkça tarafından bilgisayar programcısı aynı şekilde yukarıdaki hafızaya alınmış versiyonu faktöryel uygulandığında, referans olarak şeffaf işlevler de otomatik olarak hafızaya alınabilir dışarıdan.[1] Tarafından kullanılan teknikler Peter Norvig sadece başvuruda bulunmak Ortak Lisp (makalesinin otomatik not almayı gösterdiği dil), ama aynı zamanda çeşitli başka Programlama dilleri. Otomatik not alma uygulamaları da resmi olarak araştırılmıştır. terim yeniden yazma[4] ve yapay zeka.[5]

Fonksiyonların olduğu programlama dillerinde birinci sınıf nesneler (gibi Lua, Python veya Perl [1] ), belirli bir parametre seti için bir değer hesaplandıktan sonra bir fonksiyonun hesaplanan değeriyle değiştirilmesi (çalışma zamanında) ile otomatik hafızaya alma uygulanabilir. Bu işlev için değer nesnesi değişimini gerçekleştiren işlev, herhangi bir bildirimsel olarak saydam işlevi genel olarak sarabilir. Aşağıdaki sözde kodu göz önünde bulundurun (burada fonksiyonların birinci sınıf değerler olduğu varsayılır):

işlev memoized-çağrı (F bir işlev nesnesi parametresidir) eğer F ekli dizi yok değerler sonra bir ilişkilendirilebilir dizi aranan değerler; eklemek değerler -e F; biterse;
    Eğer F.değerler [bağımsız değişkenler] o zaman boş F.değerler [bağımsız değişkenler] = F(argümanlar); biterse;
    dönüş F.değerler [bağımsız değişkenler]; işlevi sonlandır

Otomatik olarak hafızaya alınmış bir versiyonunu aramak için faktöryel aramak yerine yukarıdaki stratejiyi kullanmak faktöryel doğrudan, kod çağırır memoized-call (faktöriyel (n)). Bu tür her çağrı önce sonuçları depolamak için bir tutucu dizinin tahsis edilip edilmediğini kontrol eder ve yoksa bu diziyi ekler. Pozisyonda giriş yoksa değerler [bağımsız değişkenler] (nerede argümanlar ilişkilendirilebilir dizinin anahtarı olarak kullanılır), a gerçek arama yapıldı faktöryel sağlanan argümanlarla. Son olarak, anahtar konumdaki dizideki giriş, arayana geri döndürülür.

Yukarıdaki strateji şunları gerektirir: açık hafızaya alınacak bir işleve her çağrıda sarma. İzin veren dillerde kapanışlar, hafızaya alma yapılabilir dolaylı olarak aracılığıyla functor Bir sarılmış, hafızaya alınmış bir işlev nesnesi döndüren fabrika dekoratör modeli. Sözde kodda bu şu şekilde ifade edilebilir:

işlev yapısı-memoized-functor (F bir işlev nesnesi parametresidir) adında bir işlev nesnesi ayırın hafızaya alınmış versiyon;
    Memoized-version (argümanlar) if olsun kendini hiçbir ekli dizi değeri içermez, sonra [kendini bir referanstır bu nesne] adlı ilişkilendirilebilir bir dizi ayırın değerler; eklemek değerler -e kendini; biterse; eğer öz.değerler [bağımsız değişkenler] bos sonra öz.değerler [bağımsız değişkenler] = F(argümanlar); biterse; kendine dön.değerler [bağımsız değişkenler]; izin ver;
    dönüş hafızaya alınmış versiyon; işlevi sonlandır

Aramak yerine faktöryel, yeni bir işlev nesnesi Memfact aşağıdaki gibi oluşturulur:

 memfact = memoize edilmiş-oluşturucu (faktöryel)

Yukarıdaki örnek, işlevin faktöryel zaten tanımlandı önce çağrı oluştur-memoized-functor yapılmış. Bu noktadan itibaren, memfact (n) faktöriyeli olduğu zaman çağrılır n arzulandı. Lua gibi dillerde, bir işlevin aynı ada sahip yeni bir işlevle değiştirilmesine izin veren daha karmaşık teknikler vardır ve bu da şunlara izin verir:

 faktöriyel = memoize edilmiş-oluşturucu (faktöryel)

Esasen, bu tür teknikler, orijinal işlev nesnesi yaratılan işleve ve asıl işleve çağrı iletme, asıl işleve bir çağrı gerektiğinde (sonsuza kadar özyineleme ), aşağıda gösterildiği gibi:

işlev yapısı-memoized-functor (F bir işlev nesnesi parametresidir) adında bir işlev nesnesi ayırın hafızaya alınmış versiyon;
    İzin Vermek hafızaya alınmış versiyon(argümanlar) be if kendini hiçbir ekli dizi değeri içermez, sonra [kendini bu nesneye bir referanstır] adlı ilişkilendirilebilir bir dizi ayırın değerler; eklemek değerler -e kendini; adında yeni bir işlev nesnesi ayırın takma ad; eklemek takma ad -e kendini; [daha sonra çağırma yeteneği için F dolaylı olarak] öz.takma ad = F; biterse; eğer öz.değerler [bağımsız değişkenler] bos sonra öz.değerler [bağımsız değişkenler] = öz.takma ad(argümanlar); [değil doğrudan arama F] end if; kendine dön.değerler [bağımsız değişkenler]; izin ver;
    dönüş hafızaya alınmış versiyon; işlevi sonlandır

(Not: Yukarıda gösterilen adımlardan bazıları, uygulama dili tarafından dolaylı olarak yönetilebilir ve açıklama amacıyla sağlanmıştır.)

Ayrıştırıcılar

Zaman yukarıdan aşağı ayrıştırıcı ayrıştırmaya çalışır belirsiz belirsiz bir bağlamdan bağımsız gramer (CFG), tüm olası ayrıştırma ağaçlarını üretmek için CFG'nin tüm alternatiflerini denemek için üstel bir adım sayısına (girişin uzunluğuna göre) ihtiyaç duyabilir. Bu sonuçta üstel bellek alanı gerektirecektir. Memoization, bir ayrıştırma 1991'deki strateji, Peter Norvig'in kullanımına benzer bir algoritmanın dinamik program ve durum setleri Earley'in algoritması (1970) ve CYK algoritması Cocke, Younger ve Kasami, otomatik not alma özelliğini basit bir geri izleme yinelemeli iniş ayrıştırıcı üstel zaman karmaşıklığı problemini çözmek için.[1] Norvig’in yaklaşımındaki temel fikir, girdiye bir ayrıştırıcı uygulandığında, aynı ayrıştırıcı aynı girdiye tekrar uygulandığında sonucun daha sonra yeniden kullanılmak üzere hatırlanabilir bir dosyada saklanmasıdır. Richard Frost, aynı zamanda üstel zaman karmaşıklığını azaltmak için not alma özelliğini kullandı. ayrıştırıcı birleştiriciler "Tamamen İşlevsel Yukarıdan Aşağıya Geri İzleme" ayrıştırma tekniği olarak görülebilir.[6] Temel hafızaya alınmış ayrıştırıcı birleştiricilerin, CFG'lerin çalıştırılabilir özellikleri olarak karmaşık ayrıştırıcıları oluşturmak için yapı taşları olarak kullanılabileceğini gösterdi.[7][8] Johnson ve Dörre tarafından 1995 yılında yeniden ayrıştırma bağlamında araştırıldı.[9][10] 2002 yılında Ford tarafından oldukça derinlemesine incelendi. packrat ayrıştırma.[11]

2007'de Frost, Hafiz ve Callaghan[kaynak belirtilmeli ] her türlü belirsiz CFG'yi içinde barındırmak için fazlalık hesaplamalardan kaçınmak için hafızayı kullanan yukarıdan aşağıya bir ayrıştırma algoritması tanımladı polinom zaman (Θ (n4) için sol yinelemeli gramer ve Θ (n3) sol yinelemeli olmayan gramerler için). Yukarıdan aşağıya ayrıştırma algoritmaları, potansiyel olarak üstel belirsiz ayrıştırma ağaçları için 'kompakt temsil' ve 'yerel belirsizlik gruplaması' ile polinom uzay gerektirir. Kompakt gösterimleri, Tomita’nın kompakt temsili ile karşılaştırılabilir. aşağıdan yukarıya ayrıştırma.[12] Hafızaya alma kullanımları, yalnızca bir ayrıştırıcı aynı giriş konumuna tekrar tekrar uygulandığında (polinom zaman gereksinimi için esastır) önceden hesaplanan sonuçların geri alınmasıyla sınırlı değildir; aşağıdaki ek görevleri gerçekleştirmek üzere uzmanlaşmıştır:

  • Hafızaya alma süreci (herhangi bir ayrıştırıcı yürütmesinin etrafında bir "sarmalayıcı" olarak görülebilir), sürekli büyüyen bir doğrudan sol yinelemeli giriş uzunluğu ve mevcut giriş konumuna göre derinlik kısıtlamaları uygulayarak ayrıştırın.
  • 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 sonucun yeniden kullanılabilirliğini de belirler. Bu bağlamsal karşılaştırma, uyum sağlamanın anahtarıdır dolaylı (veya gizli) sol özyineleme.
  • Bir hatırlanabilir dosyada başarılı bir arama gerçekleştirirken, tüm sonuç kümesini döndürmek yerine, işlem yalnızca gerçek sonucun referanslarını döndürür ve sonunda genel hesaplamayı hızlandırır.
  • Hatırlanabilirin güncellenmesi sırasında, hafızaya alma süreci belirsiz (potansiyel olarak üstel) sonuçları gruplandırır ve polinom alan gereksinimini sağlar.

Frost, Hafiz ve Callaghan ayrıca PADL’08'deki algoritmanın uygulanmasını anlattı[kaynak belirtilmeli ] bir dizi olarak üst düzey işlevler (aranan ayrıştırıcı birleştiriciler ) içinde Haskell, CFG'lerin doğrudan çalıştırılabilir özelliklerinin dil işlemcileri olarak oluşturulmasını sağlar. Polinom algoritmalarının "her türlü belirsiz CFG'yi" yukarıdan aşağıya ayrıştırma ile uydurma gücünün önemi, sözdizimi ve anlambilim analizi açısından hayati önem taşımaktadır. doğal dil işleme. X-SAIGA site, algoritma ve uygulama ayrıntıları hakkında daha fazla bilgiye sahiptir.

Norvig artarken güç Hafızaya alma yoluyla ayrıştırıcıya bakıldığında, artırılmış ayrıştırıcı, hız optimizasyonundan başka bir şey için hafızaya alma kullanımının bir örneğini gösteren Earley'in algoritması kadar zaman karmaşıktı. Johnson ve Dörre[10] Bu tür başka bir hız ile ilgili olmayan hatırlatma uygulamasını gösterin: dilsel kısıt çözümlemesini, bu kısıtlamaları çözmek için yeterli bilginin toplandığı bir çözümlemede bir noktaya kadar geciktirmek için hafızaya alma kullanımı. Buna karşılık, hızlı optimizasyon hafızaya alma uygulamasında Ford, hafızaya alma işleminin şunları garanti edebileceğini gösterdi: ifade gramerlerini ayrıştırma ayrıştırılabilir doğrusal zaman bile Diller bu, en kötü durum geri izleme davranışıyla sonuçlandı.[11]

Aşağıdakileri göz önünde bulundur dilbilgisi:

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

(Gösterim notu: Yukarıdaki örnekte, üretim S → (A c) | (B d) okur: "An S ya bir Bir ardından bir c veya a B ardından bir d. "Üretim X → x [X] "An" okur X bir x ardından isteğe bağlı X.")

Bu dilbilgisi, aşağıdaki üç varyasyondan birini oluşturur dizi: xac, xbcveya xbd (nerede x burada anlamı anlaşılıyor bir veya daha fazla x'sDaha sonra, ayrıştırma özelliği olarak kullanılan bu dilbilgisinin dizenin yukarıdan aşağıya, soldan sağa ayrıştırılmasını nasıl etkileyebileceğini düşünün. xxxxxbd:

Kural Bir tanıyacak xxxxxb (önce alçalarak X birini tanımak xve tekrar iniyor X hepsine kadar x'ler tüketilir ve ardından b) ve sonra geri dönün Sve bir c. Sonraki fıkra S daha sonra B'ye inecek ve tekrar iner X ve tanır xbirçok özyinelemeli çağrı vasıtasıyla Xve sonra a bve geri döner S ve sonunda bir d.

Buradaki temel kavram, ifadenin özünde tekrar iner X. İleriye bakma, başarısız olma, yedekleme ve sonra bir sonraki alternatifi yeniden deneme süreci, ayrıştırmada geri izleme olarak bilinir ve ayrıştırmada hatırlama fırsatları sunan, öncelikle geri izlemedir. Bir işlevi düşünün RuleAcceptsSomeInput (Kural, Konum, Giriş), burada parametreler aşağıdaki gibidir:

  • Kural söz konusu kuralın adıdır.
  • Durum girdide şu anda dikkate alınan ofsettir.
  • Giriş değerlendirilmekte olan girdidir.

İşlevin dönüş değeri olsun RuleAcceptsSomeInput tarafından kabul edilen girdinin uzunluğu Kural, veya kural dizedeki ofsette herhangi bir girdi kabul etmiyorsa 0. Böyle bir hafızaya sahip bir geriye dönük izleme senaryosunda, ayrıştırma süreci aşağıdaki gibidir:

Kural ne zaman Bir iner X ofset 0'da, bu konuma göre 5 uzunluğunu ve kural X. Başarısız olduktan sonra d, B sonra tekrar aşağı inmek yerine X, kurala göre 0 konumunu sorgular X hafızaya alma motorunda ve 5 uzunluğunda döndürülür, böylece gerçekte tekrar aşağı inmek zorunda kalmadan tasarruf edilir. Xve devam ediyor sanki aşağı indi X eskisi kadar çok kez.

Yukarıdaki örnekte, biri veya birçok iner X aşağıdaki gibi dizelere izin vererek oluşabilir xxxxxxxxxxxxxxxxbd. Aslında olabilir herhangi bir numara nın-nin xöncesi b. S'ye yapılan çağrı, olduğu kadar X'e yinelemeli olarak inmelidir. x's, B hiçbir zaman X'e inmek zorunda kalmayacak, çünkü dönüş değeri RuleAcceptsSomeInput (X, 0, xxxxxxxxxxxxxxxxbd) 16 olacaktır (bu özel durumda).

Kullanan ayrıştırıcılar sözdizimsel yüklemler aynı zamanda yüklem ayrıştırmalarının sonuçlarını da ezberleyebilir, böylece aşağıdaki gibi yapıları azaltır:

S → (A)? AA → / * bir kural * /

içine bir iniş Bir.

Bir ayrıştırıcı bir ayrıştırma ağacı ayrıştırma sırasında, yalnızca hatırlamak zorunda değil uzunluk Girdinin belirli bir kurala göre bir ofsette eşleşen, ancak aynı zamanda bu kural tarafından üretilen alt ağacı, ayrıştırıcının kurala sonraki çağrıları gerçekte alçalmayacağı ve yeniden oluşturmayacağı için, bu kural tarafından üretilen alt ağacı girdideki ofsette depolaması gerekir. ağaç. Aynı nedenden ötürü, harici koda çağrı üreten hafızaya alınmış ayrıştırıcı algoritmaları (bazen anlamsal eylem rutini ) Bir kural eşleşmesinin, bu tür kuralların tahmin edilebilir bir sırayla çağrılmasını sağlamak için bazı şemaları kullanması gerektiğinde.

Herhangi bir geri izleme veya sözdizimsel yüklem yeteneğine sahip ayrıştırıcı için her dilbilgisi ihtiyaç Geriye dönük izleme veya yüklem kontrolleri, her kuralın ayrıştırma sonuçlarını girdideki her ofsete karşı depolamanın ek yükü (ve ayrıştırma işlemi bunu örtük olarak yapıyorsa ayrıştırma ağacını depolamak) aslında yavaşla bir ayrıştırıcı. Bu etki, ayrıştırıcının hatırlayacağı kuralların açık seçilmesiyle azaltılabilir.[13]

Ayrıca bakınız

Referanslar

  1. ^ a b c Norvig, Peter (1991). "Bağlamsız Ayrıştırma Uygulamaları ile Otomatik Hafızaya Alma Teknikleri". Hesaplamalı dilbilimleri. 17 (1): 91–98.
  2. ^ Warren, David. "Tablo ve Veri Günlüğü Programlama". Alındı 29 Mayıs 2009.
  3. ^ Michie Donald (1968). "'Memo 'İşlevleri ve Makine Öğrenimi " (PDF). Doğa. 218 (5136): 19–22. Bibcode:1968Natur.218 ... 19M. doi:10.1038 / 218019a0. S2CID  4265138.
  4. ^ Hoffman, Berthold (1992). "Paylaşım ve Hatırlama ile Yeniden Yazım". Kirchner, H .; Levi, G. (editörler). Cebirsel ve Mantıksal Programlama: Üçüncü Uluslararası Konferans, Bildiriler, Volterra, İtalya, 2-4 Eylül 1992. Bilgisayar Bilimlerinde Ders Notları. 632. Berlin: Springer. sayfa 128–142. doi:10.1007 / BFb0013824. ISBN  978-3-540-55873-6.
  5. ^ Mayfield, James; et al. (1995). "Otomatik Hafızayı Gerçek Dünya Yapay Zeka Sistemlerinde Yazılım Mühendisliği Aracı Olarak Kullanma" (PDF). Onbirinci IEEE Uygulamalar için Yapay Zeka Konferansı Bildirileri (CAIA '95). sayfa 87–93. doi:10.1109 / CAIA.1995.378786. hdl:11603/12722. ISBN  0-8186-7070-3. S2CID  8963326.
  6. ^ Frost, Richard; Szydlowski, Barbara (1996). "Tamamen İşlevsel, Yukarıdan Aşağıya Geri İzleme Dil İşlemcilerini Belleğe Alma". Sci. Bilgisayar. Program. 27 (3): 263–288. doi:10.1016/0167-6423(96)00014-7.
  7. ^ Frost Richard (1994). "Belirleyici Olmayan Yukarıdan Aşağıya Ayrıştırıcıların Tamamen İşlevsel Yürütülebilir Özelliklerinin Polinom Karmaşıklığını Elde Etmek İçin Hatırlamayı Kullanma". SİGPLAN Bildirimleri. 29 (4): 23–30. doi:10.1145/181761.181764. S2CID  10616505.
  8. ^ Frost Richard (2003). "Aramada Doğruluğu Korumaya Yönelik Monadik Hafızalama". AI 2003 Kanada Konferansı. Bilgisayar Bilimlerinde Ders Notları. 2671. sayfa 66–80. doi:10.1007/3-540-44886-1_8. ISBN  978-3-540-40300-5.
  9. ^ Johnson, Mark (1995). "Yukarıdan Aşağıya Ayrıştırmanın Hatırlanması". Hesaplamalı dilbilimleri. 21 (3): 405–417. arXiv:cmp-lg / 9504016. Bibcode:1995cmp.lg .... 4016J.
  10. ^ a b Johnson, Mark ve Dörre, Jochen (1995). "İlişkili Kısıtlamaların Hatırlanması". Hesaplamalı Dilbilim Derneği 33. Yıllık Toplantısı Bildirileri. Cambridge, Massachusetts. arXiv:cmp-lg / 9504028.
  11. ^ a b Ford Bryan (2002). Packrat Parsing: Backtracking ile Pratik Bir Doğrusal Zaman Algoritması (Yüksek lisans tezi). Massachusetts Teknoloji Enstitüsü. hdl:1721.1/87310.
  12. ^ Tomita, Masaru (1985). Doğal Dil için Etkili Ayrıştırma. Boston: Kluwer. ISBN  0-89838-202-5.
  13. ^ Acar, Umut A .; et al. (2003). "Seçmeli Memoization". 30. ACM SIGPLAN-SIGACT Programlama Dillerinin İlkeleri Sempozyumu Bildirileri, 15–17 Ocak 2003. ACM SIGPLAN Bildirimleri. 38. New Orleans, Louisiana. sayfa 14–25. arXiv:1106.0447. doi:10.1145/640128.604133.

Dış bağlantılar

Çeşitli programlama dillerinde hafızaya alma örnekleri