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

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ů

19.12.2014 7:20 /MaReK Olšavský
Předvánoční dárek pro databázaře vyšel v podobě PostgreSQL 9.4. O novinkách napsal český článek Pavel Stěhule. Opravy chyb a drobná vylepšení jsou standardem, podpora datového typu JSON je velkým skokem vpřed.
Přidat komentář

19.12.2014 7:20 /MaReK Olšavský
Zdá se, že by se Intel mohl přecijen uchytit; vedle ARM; v segmentu chytrých telefonů. Čínské Lenovo plánuje pro rok 2015 nasazení Intelovského Atomu v nových smrtphonech.
Přidat komentář

19.12.2014 7:20 /MaReK Olšavský
Jazzový zpěvačka/pianistka Dinah Washington propůjčila jméno CMS Wordpress 4.1, jehož nejvýraznější novinkou je mód pro „nerušené psaní“.
Přidat komentář

18.12.2014 7:00 /MaReK Olšavský
Porovnání FreeBSD a OpenBSD (delší článek) vyšlo na blogu Network Filter. Asi nikoho nepřekvapí, že nelze jednoznačně určit vítěze a jednoznačné doporučení „nasaďte XYZ“.
Přidat komentář

18.12.2014 7:00 /MaReK Olšavský
Snad již poslední novinkou o vydání distribuce Fedora 21 jsou verze pro 64 bitové mikroprocesory ARM (oznámení) a pro mikroprocesory Power (oznámení). Obě verze budou mít asi poměrně malou cílovou skupinu ve správcích serverů. BTW: OpenPOWER Foundation se rozrostla o Rackspace.
Přidat komentář

18.12.2014 7:00 /MaReK Olšavský
Vznik další distribuce často komentuji slovy „kdybyste měli pocit, že distribucí je málo“, ale podle dlouhodobého sledování stránek DistroWatch naopak počet distribucí klesá. Lze to vnímat jako pozitivní jev, kdy se vývojáři spojují, místo vytváření bezpočtu derivátů.
Přidat komentář

17.12.2014 7:19 /MaReK Olšavský
Martin Malý napsal článek pro (nás) pamětníky o počítačích za železnou oponou. Zatím zvládl podchytit stav pouze někdejšího Česko—Slovenska :-).
Přidat komentář

17.12.2014 7:19 /MaReK Olšavský
National Geographic je známý svými populárně naučnými TV stanicemi, nebo vydáváním časopisu. Jak používá svobodný software prozradil Shah Selbe.
Přidat komentář

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

> Poslední diskuze

16.12.2014 3:59 / Jaroslav Kelt Kuchera
Download Perl

11.12.2014 6:42 / MaReK Olšavský
Po instalaci

10.12.2014 19:26 / Vladimir VASIL
Re: Sanba

11.11.2014 14:24 / Libor Suchý
Nekonečný while cyklus

10.11.2014 19:09 / Libor Suchý
Re: tabulka - bitovy sucet

Více ...

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