Alternativă alternativă la caching-ul "răspunsurilor" cunoscute

Cred că cel mai bun mod de a forma această întrebare este cu un exemplu ... așa că motivul real pe care l-am decis să îl întreb despre asta este din cauza faptului că Problema 55 privind proiectul Euler . În această problemă, cere să găsească numărul de numere Lychrel sub 10.000. Într-un limbaj imperativ, aș primi lista numerelor care au dus la palindromul final și le-aș împinge pe aceste numere într-o listă în afara funcției mele. Aș verifica apoi fiecare număr de intrare pentru a vedea dacă aceasta face parte din acea listă și, dacă da, opriți pur și simplu testul și concluzionați că numărul nu este un număr Lychrel. Aș face același lucru și cu numerele non-lychrel și cu numerele precedente.

Am mai facut asta inainte si sa descurcat minunat. Cu toate acestea, pare a fi un hassle mare pentru a pune în aplicare acest lucru în Haskell, fără a adăuga o grămadă de argumente suplimentare funcțiilor mele de a ține predecesorii și o funcție parentală absolută de a deține toate numerele de care am nevoie pentru a stoca.

Mă întreb doar dacă există un fel de instrument pe care mi-l lipsește aici sau dacă există standarde ca modalitate de a face acest lucru? Am citit faptul că Haskell este un fel de "cache natural" (de exemplu, dacă aș fi vrut să definească numerele impare ca odds = filter odd [1 ..] , aș putea să mă refer la asta ori de câte ori am vrut , dar se pare că se complică când trebuie să adaug elemente dinamice la o listă.

Orice sugestii cu privire la modul de a aborda acest lucru?

Mulțumiri.

PS: Nu cer un răspuns la problema proiectului Euler, vreau doar să-l cunosc pe Haskell puțin mai bine!

0
Sugestie: Control.Monad.State se poate ocupa de trecerea cache-urilor pentru tine.
adăugat autor Daniel Fischer, sursa

1 răspunsuri

Cred că căutați memorarea . Există mai multe moduri de a face acest lucru. O modalitate destul de simplă este cu pachetul MemoTrie . Alternativ, dacă știți că domeniul dvs. de intrare este un set limitat de numere (de exemplu [0,10000)), puteți crea o matrice în care valorile sunt rezultatele calculelor dvs. și apoi puteți doar să indexați în matrice cu ajutorul datelor introduse. Metoda Array nu va funcționa pentru dvs., deoarece, deși, chiar dacă numerele dvs. de intrare sunt mai mici de 10.000, iterațiile ulterioare pot crește în mod trivial mai mare de 10.000.

Acestea fiind spuse, când am rezolvat problema 55 în Haskell, nu m-am deranjat să fac nici o memoizare. Sa dovedit a fi suficient de rapid pentru a rula (până la) 50 iterații pe toate numerele de intrare. De fapt, rularea exact acum durează 0,2 secunde pentru a finaliza pe mașina mea.

0
adăugat
Afișează funcția mea de inversare intreg, care nu face nici o conversie de tip a fost oribil ineficient. Am fixat acest lucru și acum programul funcționează sub o secundă și pe mașina mea, fără nici o memoizare. Acesta este un instrument minunat de a avea în viitor totuși. Vă mulţumesc pentru ajutor!
adăugat autor Benjamin Kovach, sursa
@BenjaminKovach: Am constatat că atunci când am nevoie de a mușca cu cifrele unui număr, acesta tinde să fie mai rapid pentru a converti doar la un șir și a cartografia fiecare char înapoi la un int decât face pentru a încerca și de a face conversia manual. În soluția mea la Problema 55, funcția mea inversă este definită ca revint = read. invers. arată . Și, în mod similar, pentru testarea palindromului, folosesc show pentru a obține un șir și pentru a testa acest lucru.
adăugat autor Kevin Ballard, sursa