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

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ů

25.7.2014 7:17 /MaReK Olšavský
Miguel de Icaza rozšiřuje tým vyvíjejíci Mono a hodlají se na výkon Mono, svobodné implementace .NETu. Mono není jen pro GNU/Linux, ale i pro Android, nebo iOS.
Přidat komentář

25.7.2014 7:17 /MaReK Olšavský
Firma PredictionIO, jež připravuje software pro výuku, získala investici US$ 2.5 mil. do vývoje. Na jejich platformě údajně pracuje 4 000 vývojářů.
Přidat komentář

24.7.2014 7:19 /MaReK Olšavský
Na stránkách OpenSource.com vyšel příjemný příběh o startu malé firmy díky F/L/OSS. Za pozornost stojí i tyto malé příběhy, nejen přechody států a velkých firem na svobodná řešení, či svobodné formáty (jímž je i aktuální přechod Spojeného Království).
Přidat komentář

24.7.2014 7:19 /MaReK Olšavský
Mozilla hodlá soupeřit s Googlem i v segmentu „minipočítačů do HDMI“. soupeř Chromecastu, ale s Firefox OS. Podle informací, jež jsou aktuálně k dispozici, by příchod takového zařízení nemusel trvat dlouho.
Přidat komentář

24.7.2014 7:19 /MaReK Olšavský
Oracle již vydal svůj klon RHEL 7, který však není „pouze rekompilací“ s jinými značkami (jako mnohem populárnější a známější CentOS, či Scientific Linux), ale má i vlastní přidanou hodnotu v Ksplice, nebo vlastním jádře. Pokud uživatel/správce nemá dostatek financí na zaplacení RHELu 7, může být Oracle Linux lepší možností, než CentOS, či Scientific, ale „zaplatí“ minimálně vydáním svých údajů firmě Oracle.
Komentářů: 2

23.7.2014 7:25 /MaReK Olšavský
NVidia opravdu vstoupila na trh tabletů modelem Shield Tablet, za cenu US$ 299 (za ovladač se platí dalších US$ 59). V tabletu je mikroprocesor Tegra K1 (Cortex-A15 jádro, výroba nVidia), FullHD display a 16&bnsp;GB velké úložiště. Nejedná se o zástupce levných tabletů s Androidem, cílovou skupinou kupujících by měli být hráči.
Přidat komentář

23.7.2014 7:25 /MaReK Olšavský
Po odchodu Jono Bacona musel Canonical přestavět strukturu teamu, v němž již není jediný „komunitní manager“. Ubuntu není malou distribucí a pro řízení jejího vývoje je potřeba mnohem více lidí.
Přidat komentář

22.7.2014 6:32 /MaReK Olšavský
PHP 6 mělo být již před několika lety, blížící se PHP 5.6 (aktuálně je v RC2) nabízí snad vše, co mělo obsahovat PHP 6. Vzhledem k aktuálnímu stavu je pravděpodobné, že přístí „velkou“ verzí bude PHP 7, verze 6 se v číselné řadě přeskočí.
Přidat komentář

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

> Poslední diskuze

25.7.2014 7:06 / MaReK Olšavský
Re: ksplice

24.7.2014 8:06 / Stanislav David
ksplice

15.7.2014 6:16 / MaReK Olšavský
2017

25.6.2014 19:04 / Petr Ježek
více argumentů

25.6.2014 19:01 / Petr Ježek
nejde o ideologii

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