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 6368×

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ů

14.11.2017 16:56 /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 – tradičně první čtvrtek před třetím pátkem v měsíci: 16. listopadu od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

12.11.2017 11:06 /Redakce Linuxsoft.cz
PR: 4. ročník odborné IT konference na téma Datová centra pro business proběhne již ve čtvrtek 23. listopadu 2017 v konferenčním centru Vavruška, v paláci Charitas, Karlovo náměstí 5, Praha 2 (u metra Karlovo náměstí) od 9:00. Konference o návrhu, budování, správě a efektivním využívání datových center nabídne odpovědi na aktuální a často řešené otázky, např Jaké jsou aktuální trendy v oblasti datových center a jak je využít pro vlastní prospěch? Jak zajistit pro firmu či jinou organizaci odpovídající služby datových center? Podle jakých kritérií vybrat dodavatele služeb? Jak volit součásti infrastruktury při budování či rozšiřování vlastního datového centra? Jak efektivně spravovat datové centrum? Jak eliminovat možná rizika? apod.
Přidat komentář

13.9.2017 8:00 /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 – tentokrát netradičně v pondělí: 18. září od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

3.9.2017 20:45 /Redakce Linuxsoft.cz
PR: Dne 21. září 2017 proběhne v Praze konference "Mobilní řešení pro business". Hlavní tématy konference budou: nejnovější trendy v oblasti mobilních řešení pro firmy, efektivní využití mobilních zařízení, bezpečnostní rizika a řešení pro jejich omezení, správa mobilních zařízení ve firmách a další.
Přidat komentář

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ář

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

> Poslední diskuze

15.12.2017 15:11 / Petit
freehold nj

15.12.2017 15:06 / Petit
nj freehold

5.12.2017 11:50 / Thomas
kitchen renovations

18.9.2017 14:37 / Rojas
high security vault

15.9.2017 7:33 / Wilson
new zealand childcare jobs

Více ...

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