LINUXSOFT.cz Přeskoč levou lištu
Uživatel: Heslo:  
   CZUKPL

> Perl (138) - Memoizace - cachování podprogramů

Perl Zejména u projektů zpracovávajících velká množství dat je již ve fázi implementace nezbytné přemýšlet o optimalizaci jednotlivých programových úseků. Jedním z efektivních nástrojů s jednoduchou myšlekou je memoizace.

18.8.2011 00:00 | Jiří Václavík | Články autora | přečteno 6104×

Memoizace je optimalizační technika, která zefektivňuje chod vhodných úseků programu. Používá se u podprogramů, které jsou často spouštěny se stejnými vstupními daty.

Princip memoizace je v tom, že po zavolání podprogramu nejprve zkontrolujeme, zda jsme ho již se stejnými vstupními daty nespouštěli. Když zjistíme, že ne, spustíme ho, vrátíme výsledek a navíc si ho někde ponecháme uložený. Když ale zjistíme, že totožný výpočet již běžel, volání podprogramu přeskočíme a vrátíme uložený výsledek.

To však neznamená, že memoizace je něco, co bychom mohli bezhlavě používat všude. Memoizace je obchod - měníme rychlost programu za paměťové nároky. Cenu určuje charakter podprogramu - čím více je možností vstupu, tím je rychlost dražší.

Co memoizovat

Typičtí kandidáti na memoizaci často bývají rekurzivní funkce, které se rozběhnou vždy stejným způsobem. Ve většině případů je rekurzivní varianta výpočtu sice intuitivnější, avšak méně efektivní. Zefektivnění lze vždy provést přepsáním algoritmu s rekurzí na algoritmus bez ní (což lze mimochodem udělat algoritmicky pro libovolnou rekurzi).

Může nastat i extrémní případ, kdy rekurze způsobuje exponenciální složitost u programu, který by mohl být třeba i lineární. Ukážeme si jeden takový příklad a pak zkusíme cachovat.

Ještě před tím uveďme, že kandidáti pro memoizaci pochází často také z nerekurzivních funkcí. Bez kontextu sice nelze skoro nikdy říci, zda jde o vhodné kandidáty, ale uveďme jen pro představu pár příkladů, kde to většinou výhodné bude. Každý jistě vymyslí mnoho dalších.

  • matematické výpočty - různé posloupnosti (zejména rekurzivně zadané), náročné operace pro malý definiční obor, konkrétně např. faktoriál
  • mirrorování webu, nebudeme opakovaně stahovat stejnou URL
  • různé konverze na malém definičním oboru

Příklad typického neefektivního podprogramu - Fibonacciho posloupnost

Fibonacciho posloupnost je definovaná jako 1 pro nultý a první člen (někdy 0 a 1) a pro ostatní jako součet dvou předchozích. Začíná tedy čísly 1 1 2 3 5 8 13 21 34 55.

Podívejme se na následující triviální podprogram, který pro dané n spočítá ntý člen posloupnosti.

sub fibonacci {
    my $n = shift;
    return 1 if ($n <= 1);
    return fibonacci($n - 1) + fibonacci($n - 2);
}

Zkusme si teď spočítat prvních 36 členů posloupnosti a stopnout, jak dlouho to bude trvat.

use Time::HiRes qw(time);

for(0 .. 35){
    my $t= time();
    my $f = fibonacci($_);
    print sprintf("f(%2d) = %8d, doba: %f\n", $_, $f, time() - $t);
}

Zajímá-li vás výstup, zde je:

f( 0) =         1, doba: 0.000024
f( 1) =         1, doba: 0.000007
f( 2) =         2, doba: 0.000013
f( 3) =         3, doba: 0.000012
f( 4) =         5, doba: 0.000018
f( 5) =         8, doba: 0.000022
f( 6) =        13, doba: 0.000032
f( 7) =        21, doba: 0.000047
f( 8) =        34, doba: 0.000073
f( 9) =        55, doba: 0.000116
f(10) =        89, doba: 0.000190
f(11) =       144, doba: 0.000471
f(12) =       233, doba: 0.000483
f(13) =       377, doba: 0.000909
f(14) =       610, doba: 0.001499
f(15) =       987, doba: 0.002130
f(16) =      1597, doba: 0.003329
f(17) =      2584, doba: 0.005423
f(18) =      4181, doba: 0.008336
f(19) =      6765, doba: 0.016447
f(20) =     10946, doba: 0.027183
f(21) =     17711, doba: 0.039360
f(22) =     28657, doba: 0.058051
f(23) =     46368, doba: 0.098867
f(24) =     75025, doba: 0.150952
f(25) =    121393, doba: 0.241542
f(26) =    196418, doba: 0.398880
f(27) =    317811, doba: 0.637901
f(28) =    514229, doba: 0.996751
f(29) =    832040, doba: 1.626886
f(30) =   1346269, doba: 2.650302
f(31) =   2178309, doba: 4.216838
f(32) =   3524578, doba: 6.935077
f(33) =  5702887, doba: 11.239907
f(34) =  9227465, doba: 18.135487
f(35) = 14930352, doba: 29.593933

Výpočet pro 35 již trvá půl minuty. Jak je to možné? Vždyť v celém programu opakovaně provádíme pouze sčítání dvou malých čísel!

Všimněme si posloupnosti dob výpočtů vpravo. Přibližně platí, že každá hodnota je součtem dvou předcházejících. To naznačuje, že v ntém kroku vždy provádíme tolik operací jako v dvou předcházejícíh dohromady.

Pro f(0) a f(1) pouze vrátíme výsledek. Řekněme, že potřebujeme jednu operaci. Pro f(2) voláme f(0) a f(1) a ty sčítáme, dohromady 3 operace. Pro f(3) voláme f(1) a f(2) a opět sčítáme. To je 5 operací. Posloupnost počtu výpočtů je 1 1 3 5 9 15 25 41 67 109 177 287 465 753 1219 1973 3193 5167 8361 13529 21897 atd. Půjdeme-li na konec, dostaneme pro f(35) 29 860 703 volání naší funkce. Na to, že jde o velmi snadný výpočet je to trochu moc. Jak tomu zamezit?

Jak funguje memoizace

Koho zajímá jen výsledný efekt, může bez obav přeskočit na sekci o modulu Memoize.

Pojďme zkusit upravit náš podprogram fibonacci tak, aby pracoval rychleji. K tomu účelu si vytvoříme nějakou cache ve formě hashe nebo pole, tj. globální proměnnou nebo proměnnou uzavřenou do bloku společně s podprogramem.

Nám bude stačit obyčejné pole. Na začátku podprogramu se podíváme, zda jsme již náhodou stejné volání neprováděli. Pokud ano, přeskočíme celý velký strom výpočtů a okamžitě vrátíme výsledek. Pokud ne, výsledek spočítáme jako dříve a uložíme ho do cache.

{
    my @vypocitane;

    sub fibonacci {
        my $n = shift;

        return $vypocitane[$n] if defined $vypocitane[$n];

        my $vysledek;

        if ($n <= 1) {
            $vysledek = 1;
        }
        else {
            $vysledek = fibonacci($n - 1) + fibonacci($n - 2);
        }

        return $vypocitane[$n] = $vysledek;
    }
}

Jaká je zde posloupnost počtu výpočtů? 1 1 3 3 3 3 3 3 3 atd. Je velký rozdíl dělat 30 000 000 nebo 3 výpočty. Proto dostaneme výsledky hned.

f( 0) =        1, doba: 0.000026
f( 1) =        1, doba: 0.000007
f( 2) =        2, doba: 0.000016
f( 3) =        3, doba: 0.000009
f( 4) =        5, doba: 0.000010
f( 5) =        8, doba: 0.000009
f( 6) =       13, doba: 0.000009
f( 7) =       21, doba: 0.000009
f( 8) =       34, doba: 0.000009
f( 9) =       55, doba: 0.000009
f(10) =       89, doba: 0.000009
f(11) =      144, doba: 0.000009
f(12) =      233, doba: 0.000010
f(13) =      377, doba: 0.000009
f(14) =      610, doba: 0.000009
f(15) =      987, doba: 0.000009
f(16) =     1597, doba: 0.000009
f(17) =     2584, doba: 0.000009
f(18) =     4181, doba: 0.000009
f(19) =     6765, doba: 0.000009
f(20) =    10946, doba: 0.000009
f(21) =    17711, doba: 0.000009
f(22) =    28657, doba: 0.000014
f(23) =    46368, doba: 0.000009
f(24) =    75025, doba: 0.000008
f(25) =   121393, doba: 0.000009
f(26) =   196418, doba: 0.000009
f(27) =   317811, doba: 0.000009
f(28) =   514229, doba: 0.000010
f(29) =   832040, doba: 0.000009
f(30) =  1346269, doba: 0.000009
f(31) =  2178309, doba: 0.000009
f(32) =  3524578, doba: 0.000009
f(33) =  5702887, doba: 0.000008
f(34) =  9227465, doba: 0.000008
f(35) = 14930352, doba: 0.000008

Modul Memoize

Abychom nemuseli dělat tento proces pokaždé, napsal Damian Conway modul Memoize, který ho provede za nás.

use Memoize;
memoize("fibonacci");

sub fibonacci {
    my $n = shift;
    return 1 if ($n <= 1);
    return fibonacci($n - 1) + fibonacci($n - 2);
}

U větších projektů s mnoha memoizovanými funkcemi pak poslouží ještě lépe např. Attribute::Memoize:

use Attribute::Memoize;
sub fibonacci :MEMOIZE {
    my $n = shift;
    return 1 if ($n <= 1);
    return fibonacci($n - 1) + fibonacci($n - 2);
}

Co vlastně modul Memoize udělá? Nejprve se vytvoří nový anonymní memoizovaný podprogram. Ten se pojmenuje stejně jako ten náš původní, který tak je zapomenut.

Další možnosti modulu Memoize

Funkce memoize má několik parametrů. Například lze memoizovanou funkci pojmenovat jinak než původní podprogram. To se může hodit pro účely testování rychlosti.

memoize("fibonacci", INSTALL => "memoized_fibonacci");

Pomocí volby NORMALIZER => normalizacni_funkce vytváříme třídy ekvivalence mezi voláními. Co když například v následujících volání nezávisí na pořadí?

f(a => 1, b => 2);
f(b => 2, a => 1);

Pak jsou ekvivalentní a pro větší efektivitu memoizace to můžeme specifikovat pomocí normalizační funkce. Často je ale třeba testovat, zda se to vyplatí.

Normalizační funkce má jako vstup parametry původního podprogramu a výstupem je unikátní řetězec pro každou třídu ekvivalence. V našem případě by například parametry a => 1, b => 2 stejně jako b => 2, a => 1 transformovala například na řetězec "a, 1, b, 2". Standardní normalizační funkce zřetězí parametry speciálním ASCII znakem 28 (file separator, hexa 1c).

Podívejme se na příklad normalizační funkce, která zahladí rozdíly mezi pořadím dvojic.

sub normalizacni_funkce {
    my %hash = @_;
    my $id = '';
    for (sort keys %hash){
        $id .= $_ . "\x{1c}" . $hash{$_} . "\x{1c}";
    }
    return $id;
}

Normalizační funkci lze použít i k opačnému účelu. Pokud náš program závisí na čase, nelze memoizovat. Pokud však závisí jen na určité složce (například sekundě od 0 do 59), stačí ji přidat do výstupního řetězce.

Když už budeme memoizovat, často budeme chtít uchovávat cache i pro další spuštění programu. Paměť se obvykle sama maže. Jak zajistit perzistenci? V dokumentaci je naznačeno použití mechanizmu tie a souborové databáze.

use DB_File;
tie %cache => "DB_File", "soubor_s_daty", O_RDWR|O_CREAT, 0666;
memoize("funkce", SCALAR_CACHE => [HASH => \%cache]);

Cache můžeme kdykoliv vyprázdnit voláním

flush_cache("funkce")

Co nememoizovat

  • (kritické) Funkce závislé na něčem jiném než parametrech (typicky čas, náhoda, globální proměnné, čtení databáze, čtení souborů atd.)
  • (kritické) Funkce, které vrací odkaz na strukturu, která by se mohla měnit
  • (kritické) Funkce, které tisknou něco na výstup nebo působí jinou činnost (zápis do databáze nebo souboru, změna globálních proměnných atd.)
  • Funkce, jejichž definiční obor je příliš velký a je velká šance, že se parametry trefí opět do nových hodnot
  • Funkce, jejichž memoizovaná verze je pomalejší než originální (vždy bychom to měli otestovat)

Verze pro tisk

pridej.cz

 

DISKUZE

Nejsou žádné diskuzní příspěvky u dané položky.



Příspívat do diskuze mohou pouze registrovaní uživatelé.
> Vyhledávání software
> Vyhledávání článků

15.5.2017 23:50 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě DIY, CNC, SDR nebo morseovka? Přijď na sraz spolku OpenAlt, který se bude konat ve čtvrtek 18. května od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

12.5.2017 16:42 /Honza Javorek
PyCon CZ, česká konference o programovacím jazyce Python, se po dvou úspěšných ročnících v Brně bude letos konat v Praze, a to 8. až 10. června. Na konferenci letos zavítá např. i Armin Ronacher, známý především jako autor frameworku Flask, šablon Jinja2/Twig, a dalších projektů. Těšit se můžete na přednášky o datové analytice, tvorbě webu, testování, tvorbě API, učení a mentorování programování, přednášky o rozvoji komunity, o použití Pythonu ve vědě nebo k ovládání nejrůznějších zařízení (MicroPython). Na vlastní prsty si můžete na workshopech vyzkoušet postavit Pythonem ovládaného robota, naučit se učit šestileté děti programovat, efektivně testovat nebo si v Pythonu pohrát s kartografickým materiálem. Kupujte lístky, dokud jsou.
Přidat komentář

2.5.2017 9:20 /Eva Rázgová
Putovní konference československé Drupal komunity "DrupalCamp Československo" se tentokrát koná 27. 5.2017 na VUT FIT v Brně. Můžete načerpat a vyměnit si zkušenosti z oblasti Drupalu 7 a 8, UX, SEO, managementu týmového vývoje, využití Dockeru pro Drupal a dalších. Vítáni jsou nováčci i experti. Akci pořádají Slovenská Drupal Asociácia a česká Asociace pro Drupal. Registrace na webu .
Přidat komentář

1.5.2017 20:31 /Pavel `Goldenfish' Kysilka
PR: 25.5.2017 proběhne v Praze konference na téma Firemní informační systémy. Hlavními tématy jsou: Informační systémy s vlastní inteligencí, efektivní práce s dokumenty, mobilní přístup k datům nebo využívání cloudu.
Přidat komentář

15.4.2017 15:20 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě IoT a radiokomunikace? Přijď na sraz spolku OpenAlt, který se bude konat ve středu 19. dubna od 18:30 v Šenkovně (Sokolská 60, Praha 2).
Přidat komentář

5.3.2017 19:12 /Redakce Linuxsoft.cz
PR: 23. března proběhne v Praze konferenci na téma Cloud computing v praxi. Hlavními tématy jsou: Nejžhavější trendy v oblasti cloudu a cloudových řešení, Moderní cloudové služby, Infrastruktura současných cloudů, Efektivní využití cloudu, Nástrahy cloudových řešení a jak se jim vyhnout.
Přidat komentář

27.2.2017 22:12 /František Kučera
Pozvánka na 137. sraz OpenAlt – Praha: Tentokrát jsme si pro vás připravili neobvyklou akci. Ve středu 1.3. v 17:30 nás přivítá sdružení CZ.NIC ve svých prostorách v Milešovské ulici číslo 5 na Praze 3, kde si pro nás připravili krátkou prezentaci jejich činnosti. Následně navštívíme jejich datacentrum pod Žižkovskou věží. Provedou nás prostory, které jsou běžnému smrtelníkovi nedostupné!
Po ukončení prohlídky se všchni odebereme do hostince U vodoucha, Jagelonská 21, Praha 3 pochutnat si na některém z vybraných piv či dát si něco na zub. Rezervaci máme od 19:30, heslo je OpenAlt.
Ale pozor! Do prostor datového centra máme omezený přístup, dostane se tam pouze 10 lidí! Takže kdo přijde dříve, ten má přednost, a občanky s sebou! Kdo nebude chtít na prohlídku datového centra, může se pomalu přesunout do hostince U vodoucha a u nepřeberné nabídky piv počkat na ostatní.
Přidat komentář

18.1.2017 0:49 /František Kučera
Členové a příznivci spolku OpenAlt se pravidelně schází v Praze a Brně. Fotky z pražských srazů za uplynulý rok si můžete prohlédnout na stránkách spolku. Příští sraz se koná už 19. ledna – tentokrát je tématem ergonomie ovládání počítače – tzn. klávesnice, myši a další zařízení. Také budete mít příležitost si prohlédnout pražský hackerspace Brmlab.
Přidat komentář

   Více ...   Přidat zprávičku

> Poslední diskuze

1.8.2017 7:32 / Cassidy
structural consultants

30.7.2017 11:12 / Jaromir Obr
Národní znaky

27.7.2017 12:24 / Jaromir Obr
Cteni/zapis

26.7.2017 21:12 / Jaromir Obr
Podminka

15.6.2017 9:34 / Ondřej Havlas
php,

Více ...

ISSN 1801-3805 | Provozovatel: Pavel Kysilka, IČ: 72868490 (2003-2017) | mail at linuxsoft dot cz | Design: www.megadesign.cz | Textová verze