Memoizacija

S Vikipedije, slobodne enciklopedije

Memoizacija u računarstvu, je tehnika optimizacije koja se najpre koristi da bi se ubrzalo izvršavanje računarskih programa tako što se skladište rezultati „skupih“ poziva funkcija i vraćaju keširani rezultat kada se ponovo jave isti ulazi. Memoizacija se takođe koristi u drugim kontekstima (i za potrebe koje se ne odnose na ubrzavanje računarskih programa), kao što je u jednostavnoj uzajamnoj rekurziji opadajuće parsiranje[1] u opštem top-daun (odozgo-nadole) algoritmu[2][3] za parsiranje, koji prilagođava dvosmislenost i levu rekurziju u polinomialnom vremenu i prostoru. Iako je vezana za keširanje, memoizacija ukazuje na specifičan slučaj ove optimizacije, razlikovajući je od oblika keširanja kao što su baferovanje ili zamena stranica. U kontekstu nekih logičkih programskih jezika, memoizacija je takođe poznata kao tabeliranje;[4] pogledati takođe lukap tabele.

Etimologija[uredi | uredi izvor]

Termin „memoizacija“ je uveo Donald Miči (Donald Michie) 1968. godine i izveden je od latinske reči „memorandum“ („biti zapamćen“), koja se u Engleskom jeziku skraćeno „memo“ i ima značenje „pretvarati rezultate funkcija u nešto što će biti zapamćeno“. Termin „memoizacija“ može da se pomeša sa terminom „memorizacija“, jer su etimološki srodni. Međutim, „memoizacija“ ima specifično značenje u računarstvu.

Pregled[uredi | uredi izvor]

Memoizaciona funkcija „pamti“ rezultate koji odgovaraju nekom skupu specifičnih ulaza. Naknadni pozivi sa sačuvanim ulazima će pre vraćati sačuvani rezultat nego računati ga opet i tako eliminišu prvobitnu cenu poziva funkcije sa zadatim parametrima za sve, osim za prvi poziv. Skup sačuvanih asocijacija mogu imati fiksnu veličinu kojim upravlja algoritam zamene ili fiksni skup, u zavisnosti od prirode funkcije i njene upotrebe. Funkcija može biti memoizovana samo ako je referencialno transparentna; to znači samo ako poziv funkcije ima u potpunosti isti efekat kao i zamena poziva funkcije sa svojom povratnom vrednošću. (Međutim, postoje izuzeci.) Dok su povezani sa lukap tabelama, s' obzirom da memoizacija često koristi takve tabele u svojoj implementaciji, memoizacija popunjava keš sa rezultatima transparentno u toku izvršenja, ako je potrebno, pre nego unapred. Memoizacija je način na koji se smanjuje trošak vremena izvršenja funkcije u zamenu za trošak memorijskog prostora; što znači da memoizovane fukncije postaju optimizovane po brzini na račun većeg korišćenja memorijskog prostora računara. Trošak vreme/prostor algoritma ima spcifično ime u računarstvu: teorija računarske kompleksnost. Sve fukncije imaju računarsku kompleksnost u vremenu (tj. vreme potrebno da se funkcija izvrši) i u memorijskom prostoru. Iako se kompromis javlja (npr korišćeni memorijski prostor u odnosu na ubrzanje) ovo se razlikuje od nekih drugih optimizacija koje uključuju vreme-prostor kompromis, kao što je smanjenje cene operacija, u tome što se memoizacija izvodi u fazi izvršenja programa, a ne u fazi kompilacije. Štaviše, smanjenje cene operacija potencijalno zamenjuje skupu operaciju, kao što je množenje sa manje skupom operacijom, kao što je sabiranje, i rezultati uštede mogu biti veoma zavisni od računara, tako da nisu portabilne između različitih računara, dok je memoizacija više nezavisna od računara - kros-platform strategija. Razmotriti sledeći pseudokod fukncije za izračunavanje faktorijela od 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

Za svaki ceo broj n takav da je n≥0, krajnji rezultat funkcije factorial je invarijantan; ako se poziva kao x = factorial(3), rezultat će biti takav da će x uvek biti dodeljena vrednost 6. Nememoizovana verzija gornje funkcije, zbog prirode rekurzivnog algoritma koji je korišćen, zahtevaće n + 1 poziva funkcije faktorijel da dođe do rezultata, i svaki poziv ima troškove u vremenu za koje je potrebno da funkcija vrati izračunatu vrednost. U zavisnosti od računara, trošak može biti suma sledećih troškova:

  1. postavki steka poziva fukncije.
  2. poređenja n sa 0.
  3. oduzimanja 1 od n.
  4. postavljanja steka za rekurzivne pozive.
  5. množenja rezultata rekurzivnog poziva funkcije faktorijel sa n.
  6. memorisanja povratne vrednosti tako da može biti korišćena u kontestu poziva.

U nemomizovanoj implementaciji, svaki prvi poziv funkcije factorial uključuje kumulativne troškove koraka 2 do 6, koji su proporcionalni inicijalnoj vrednosti n.

Memoizovana verzija funkcije factorial sledi: 

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

U konkretnom primeru, ako se funkcija faktorijel prvi put pozove sa brojem 5 i ako se kasnije pozove sa bilo kojim brojem koji je manji ili jednak broju 5, te povratne vrednosti će biti memoizovane, zato što je funkcija faktorijel bila rekurzivno pozivana sa vrednošćima 5, 4, 3, 2, 1 i 0 i povratna vrednost za svaki od tih poziva je bila uskladištena. Ako je kasnije pozvana sa brojevima većim od 5, npr. 7, biće napravljena samo 2 rekurzivna poziva (7 i 6), a vrednost za 5! je već skladištena od prethodnog poziva. Na taj način memoizacija omogućava da funkcija postane efikasnija u vremenu izvršenja, što se više poziva. To konačno doprinosi opštem ubrzanju izvršenja funkcije.

Ostala razmatranja[uredi | uredi izvor]

Funkcionalno programiranje[uredi | uredi izvor]

Memoizacija se mnogo koristi u kompajlerima za funkcionalne programske jezike, koji često koriste strategiju evaulacije poziva po imenu. Da bi izbegli dopunske troškove vezane za izračunavanje vrednosti argumenata, kompajleri za ove jezike često koriste pomoćne funkcije koje se zovu tankovi (pretvarači) da bi izračunali vrednosti argumenta i memoizovali ove funkcije da bi se izbeglo ponovno izračunavanje.

Automatska memoizacija[uredi | uredi izvor]

Dok memoizacija može da bude pridružena funkcijama interno i eksplicitno od strane programera, na isti takav način gore pomenuta memoizovana funkcija faktorijel može da bude automatski memoizovana eksterno[1]. Tehnike koje je koristio Peter Norvig (Peter Norvig) imaju primenu, ne samo u Lispu (jezik u kome je predstavio automatsku memizaciju), nego i u drugim programskim jezicima. Primena automatske memoizacije su formalno istražene i u studijama prepisivanja termina[5] i veštačkoj inteligenciji.[6]

U programskim jezicima gde su funkcije prvoklasni objekti (kao što su Lua, Pajton ili Perl[1]), automatska memoizacija se može implementirati zamenom (u fazi izvršenja) funkcije sa izračunatom vrednošću čim je vrednost izračunata za zadati skup parametara. Funkcija koja radi zamenu vrednost–funkciju–objekat može generalno da zapakuje svaku referencijalno transparentnu funkciju. Pogledati sledeći pseudokod (gde je pretpostavljeno da su funkcije prve klase): 

  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

Da bismo pozvali automatski memoizvanu verziju funkcije faktorijel koristeći ovu strategiju, pre nego direktnim pozivom, pseudokod poziva memoized-call(factorial(n)). Svaki takav poziv prvo proverava da li je vektor vrednosti alociran da uskladišti rezultate i ako nije, dodaje vektor. Ako ne postoje ulazi na poziciji values[arguments] (gde se arguments koriste kao ključ asocijativnog vektora), poziva se funkcija faktorijel sa zadatim argumentima. Na kraju, ulaz u vektor na poziciji ključa se vraća pozivaocu funkcije.

Gornja strategija zahteva eksplicitno pakovanje na svaki poziv funkcije koja treba da bude memoizovana. U jezicima koji omogućavaju zatvaranje, memoizacija može da se primeni implicitno pomoću funkcionalnog objekta sa funktorom koji vraća taj zapakovani memoizovani funkcionalni objekat. U pseudokodu se to može napisati na sledeći način: 

 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

Umesto da se pozove funkcija faktorijel, se kreira novi funkcionalni objekat memfact na sledeći način: 

memfact = construct-memoized-functor(factorial)

Gornji primer pretpostavlja da je funkcija faktorijel već definisana pre poziva construct-memoized-functor. Od ove tačke pa nadalje memfact(n) se poziva kad god je potrebno izračunati faktorijel od n. U jezicima kao što je Lua postoje sofisticiranije tehnike koje omogućavaju da funkcija bude zamenjena sa novom funkcijom sa istim imenom što dozvoljava: 

 factorial = construct-memoized-functor(factorial)

U suštini, takve tehnike uključuju dodavanje originalnog funkcionalnog objekta kreiranom funktoru i prosleđivanje poziva originalnoj funkciji koja je memoizovana preko alijasa, kada je potreban poziv stvarnoj funkciji (da bi se izbegle beskonačne rekurzije) kao što je prikazano dole: 

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

(Primedba: neki od prikazanih koraka mogu biti implicitno odrađeni u implementiranom jeziku i dati su radi ilustracije.)

Parseri[uredi | uredi izvor]

Kada top-daun parser pokušava da parsira nejednoznačne ulaze u odnosu na nejednoznačnu kontekstno slobodnu gramatiku (CFG) može da mu bude potreban eksponencijalni broj koraka (u odnosu na dužinu ulaza) da bi ispitao sve alternative CFG-a, da bi proizveo sva moguća stabla parciranja. To će na kraju zahtevati eksponencijalni memorijski prostor. Memoizacija je ispitana kao strategija parsiranja 1991. godine od strane Norviga, koji je pokazao da algoritam koji je sličan korišćenju dinamičkog programiranja iz skupova stanja u Erlijevom algoritmu (1970. godine) i tabelama u CYK algoritmu Koka Jungera i Kasamiju može biti generisan uvođenjem automatske memoizacije u jednostavan povratni rekurzivni silazni parser da bi rešio problem eksponencijalne vremenske kompleksnosti.[1] Osnovna ideja u Norvigovom pristupu je da kada se parser primeni na ulaz, rezultat se uskladišti u memo-tabeli za buduću upotrebu, ako se isti parser ponovo koristi na istom ulazu. Ričard Frost je takođe koristio memoizaciju da bi smanjio eksponencijalnu vremensku kompleksnost parserskih kombinatora koji može da se posmatra kao „čisto funkcionalni top-daun-bektreking“ parsing tehnika.[7] On je pokazao da bazični memizovani parser kombinatori mogu da se koriste za konstruisanje za izgradnju kompletnih parsera kao izvršna specifikacija CFG-a.[8][9] Ovo se ponovo istraživali Džonson and Dörre.[10][11] i Dere u kontekstu parsiranja 1995. godine. 2002. godine ovo je detaljno istražio i Ford u formi nazvanoj pekret-parsiranje.[12]

2007. godine Frost, Hafis i Kalahan[2] opisali su top-daun algoritam za parsiranje koji koristi memoizaciju da bi umanjili redundantna izračunavanja i da bi omogućili bilo koji oblik da bi obezbedili izvršenje bilo kog oblika nejednoznačnih CFG u polinomialnom vremenu (Θ(n4) za gramatike sa levom rekurzijom i Θ(n³) za gramatike sa nelevom rekurzijom). Njihov top-daun algoritam za parciranje takođe zahteva polinomialni prostor za potencijalno eksponencijalna nejednoznačna stabla parsiranja pomoću „kompkatnog predstaljanja“ i „lokalno grupiranje nejednoznačnosti“. Njihovo kompaktno predstavljanje je uporedivo sa kompaktnim predstavljanjem u Tomitinom botom-up[13] parsingu. Njihovo korišćenje memoizacije nije samo ograničeno na povraćaj prethodno izračunatih rezultata kada se parser upotrebljava na istim ulaznim vrednostima više puta (što je suštinski važno za zahtev za polinomialnim vremenom); ono je specijalizovano i za sledeće dopunske zadatke:

  • Proces memoizacije (koji može da se razmatra kao „omotač“ oko bilo kog izvršenja parsera) uključuje rastući direktno levo rekurzivno parsiranje, uvodeći restrikciju dubine u zavisnosti od dužine ulaza i trenutne pozicije.
  • Lukap procedura memo-tabele algoritma određuje upotrebljivost uskladištenih rezultata tako što upoređuje kontekst uskladištenih rezultata sa tekućim kontekstom parsera. To poređenje konteksta je ključno za primenu indirektne ili skrivene leve rekurzije.
  • Kada se izvede uspešan lukap u memo-tabeli, umesto da vrati kompletan skup rezultata, proces vraća samo reference na rezultate i konačno ubrzava ukupno izvršenje.
  • Za vreme ažuriranja memo-tabele, proces memoizacije grupiše (potencijalno ekponencijalne) nejednoznačne rezultate i obezbeđuje polinomialne zahteve za prostorom.

Frost, Hafis i Kalahan su takođe opisali implementaciju algoritma u PADL’08[3] kao skup funkcija višeg reda (zvani parser kobminatori) u Haskel-u, koji omogućava direktno izvršne specifikacije CFG kao procesora jezika. Značaj snage njihovog polinomialnog algoritma da uključi „bilo koji oblik“ jednoznačnog CFG sa top-daun parsiranjem je vitalna za sintaksnu i semantičku analizu prilikom obrade prirodnih jezika. Na X-SAIGA sajtu može se saznati više o detaljima algoritma i implementacije.

Dok je Norvig povećao snagu parsera pomoću memoizacije, unapređeni parser je i dalje bio vremenski kompleksan kao i Erlijev algoritam koji prikazuje slučaj korišćenja memoizacije za nešto drugo nego što je memoizacija brzine. Džonson i Dere[11] prikazuju drugu takvu primenu memoizacije koja se ne odnosi na brzinu: korišćenje memoizacije da bi se odložila rezolucija lingvističkih ograničenja do tačke u procesu parsiranja gde su akumulirane dovoljne informacije, da bi se ta ograničenja razrešila. Nasuprot tome, u primeni memoizacije za optimizaciju brzine, Ford je prikazao da memoizacija može da garantuje da gramatike za parsiranje izraza mogu da se izvrše u linearno vremenu, čak i kod jezika koji imaju najgore bektreking-ponašanje.[12] Razmotrite sledeću gramatiku: 

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

Ova gramatika generiše jednu od sledeće tri varijacije nizova: xac, xbc, ili xbd (gde se za x podrazumeva jedan ili više x-ova). Sledeće razmotrite kako ova gramatika korišćena kao specifikacija za parsiranje može da utiče na top-daun, levo-desno parsiranje niza xxxxxbd:

Pravilo A će prepoznati xxxxxbd (tako što će prvo spuštanje u X da bi prepoznao jedan x i ponovno spuštanje u x dok god svi mali x-ovi nisu prepoznati i posle toga prepoznat b) i vratiće se na S i prepustiće da prepozna c. Sledeći iskaz S-a će se spustiti u B, što će dovesti do ponovnog spuštanja u X i prepoznaće x–eve pomoću više rekurzivnih poziva X i kasnije b i vratiće se u s i konačno prepoznati d.

Ključni koncept ovde je inherentan u frazi „ponovno se spušta u X“. Proces predviđanja, promašaja, povratka i pokušaja sa sledećom alternativom se u parsiranju zove bektreking i upravo bektreking predstavlja mogućnost za memizaciju u parsiranju. Razmotrite funkciju RuleAcceptsSomeInput(Rule, Position, Input), gde su sledeći parametri:

  • Ruleje naziv pravila koje se razmatra.
  • Positionje ofset koji trenutno razmatramo u okviru ulaza.
  • Inputje ulaz koji razmatramo.

Neka povratna vrednost funkcije RuleAcceptsSomeInput bude dužina ulaza prihvaćenog od strane Rule ili 0 ako to pravilo ne prihvata ni jedan ulaz na zadatom ofsetu u nizu. U bektreking scenariju sa memoizacijom, proces parsiranja je sledeći:

Kada se pravilo A spusti na X na ofsetu 0, memorisaće se dužina 5 i pravilo X. Posle promašaja na d, B tada pre nego što se spustimo ponovo na X da upitamo poziciju 0 u odnosu na pravilo X u memoizacionoj mašini se vraća dužina od 5 tako da se štedi ponovni silazak u X i to se ponavlja.

U gornjem primeru jedno ili više spustanja u X mogu da se dese npr. za niz kao što su xxxxxxxxxxxxxxxxbd. U stvari, može da bude bilo koji broj x ispred b. Dok poziv S mora rekurzivno da se spušta u X koliko god ima x, B nikada neće morati da se spusti u X pošto je izlazna vrednost funkcije RuleAcceptsSomeInput(X, 0, xxxxxxxxxxxxxxxxbd) u ovom slučaju 16.

Parseri koji koriste sintaksne predikate su takođe u mogućnosti da memoizuju rezultate parsiranja predikata i na taj način redukuju konstrukcije kao što su: 


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

na jedno spuštanje u A.

Ako parser napravi stablo za vreme parsiranja, on mora da memoizuje, ne samo dužinu ulaza koja odgovara nekom ofsetu u odnosu na zadato pravilo, nego takođe mora da skladišti podstablo koje je generisano tim pravilom na tom ofsetu u ulazu, pošto se naredni pozivi pravila neće u stvari spustiti i obnoviti to stablo. Iz istog razloga memoizovani algoritmi parsiranja koji generišu pozive eksternog koda (ponekad se nazivaju semantičke akcione rutine) kada je pravilo uskladišteno, mora da postoji neki plan koji će obezbediti da se takva pravila pozivaju po predvidljivom redosledu.

Pošto, za bilo koji zadati parser sa bektrekingom ili sintaksnim predikatom neće svaka gramatika imati potrebu za bektrekingom ili proverom predikata, dopunski troškovi skladištenja rezultata parsiranja svakog pravila, svaki ofset u ulazu (i skladištenje stabla parsiranja ako proces parsiranja to radi implicitno) može da uspori parser. Ovaj efekat može da bude ublažen eksplicitnom selekcijom pravila koje će parser memoizovati.[14]

Vidi još[uredi | uredi izvor]

Reference[uredi | uredi izvor]

  1. ^ a b v Norvig, Peter, "Techniques for Automatic Memoization with Applications to Context-Free Parsing," Computational Linguistics, Vol. 17 No. 1. str. 91–98, March 1991.
  2. ^ a b Frost, Richard, Hafiz, Rahmatullah, and Callaghan, Paul. " Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars." 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE , Pages: 109 – 120, June 2007, Prague.
  3. ^ a b Frost, Richard, Hafiz, Rahmatullah, and Callaghan, Paul. " Parser Combinators for Ambiguous Left-Recursive Grammars." 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN , Volume 4902/2008, Pages: 167–181, January 2008, San Francisco.
  4. ^ Warren, David. "Tabling and Datalog Programming". Accessed 29 May 2009.
  5. ^ Hoffman, Berthold, "Term Rewriting with Sharing and Memoïzation," Algebraic and Logic Programming: Third International Conference, Proceedings, H. Kirchner and G. Levi (eds.). str. 128–142, Volterra, Italy, 2–4 September 1992.
  6. ^ Mayfield, James, et al., Using Automatic Memoization as a Software Engineering Tool in Real-World AI Systems, Proceedings of the Eleventh IEEE Conference on Artificial Intelligence for Applications (CAIA '95). str. 87-93, 1995.
  7. ^ Frost, Richard. and Szydlowski, Barbara. "Memoizing Purely Functional Top-Down Backtracking Language Processors. " "Sci. Comput. Program. " 1996 – 27(3): 263–288.
  8. ^ Frost, Richard. "Using Memoization to Achieve Polynomial Complexity of Purely Functional Executable Specifications of Non-Deterministic Top-Down Parsers. " "SIGPLAN Notices" 29(4): 23–30.
  9. ^ Frost, Richard. "Monadic Memoization towards Correctness-Preserving Reduction of Search. " "Canadian Conference on AI 2003." p 66-80.
  10. ^ Johnson, Mark, "Memoization of Top-Down Parsing,” Computational Linguistics, Vol. 21 No. 3. str. 405–417, September 1995.
  11. ^ a b Johnson, Mark & Dörre, Jochen, "Memoization of Coroutined Constraints," Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics, Cambridge, Massachusetts, 1995.
  12. ^ a b Ford, Bryan, Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking, Master’s thesis, Massachusetts Institute of Technology, September, 2002.
  13. ^ Tomita, Masaru. “Efficient Parsing for Natural Language.” Kluwer, Boston, MA, 1985.
  14. ^ Acar, Umut A. A. et al., "Selective Memoization," Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, New Orleans, Louisiana. str. 14–25, 15–17 January 2003.

Spoljašnje veze[uredi | uredi izvor]

Primeri memoizacije u različitim programskim jezicima
Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Мемоизација&oldid=26934686”