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

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ů

23.10.2014 7:13 /MaReK Olšavský
CERN používá OpenStack přibližně rok. Jaké je aktuální používání při výzkumu ukazuje článek na OpenSource.com. Vyprodukovaných dat, z měření, není malé množství a pro jejich zpracování je potřebný výkon několikatisíců serverů a pracovních stanic.
Přidat komentář

23.10.2014 7:13 /MaReK Olšavský
Prodejce starších her; jež jsou často hratelnější, než moderní grafické orgie; Good Old Games dosáhl milníku 100 her připravených pro Linux (nejde o portace, ale připravené konfigurace DOSBoxu/Wine).
Přidat komentář

23.10.2014 7:13 /MaReK Olšavský
O malou reklamu pro Ubuntu se postaral Andy Swan, se svým laptopem, při analýze počasí pro tragickou Velkou Cenu Japonska 2014 (Formule 1).
Přidat komentář

22.10.2014 7:19 /MaReK Olšavský
Programovacímu jazyku Swift, jenž nedávno zveřejnil Apple a je uzavřený, vzniká svobodná odpověď Phoenix (repozitář). Jazyk bude stejný, takže lze očekávat, že se Apple bude bránit i soudně. Název Phoenix už nejspíše také někdo používá, starší pamatují, že se tak chvíli jmenoval dnešní Mozilla Firefox.
Přidat komentář

22.10.2014 7:19 /MaReK Olšavský
Programátorům v PHP je určen nástroj RIPS, který jim pomůže odhalit zranitelnosti v jejich kódu. Pokud znáte další nástroje, podělte se o ně v diskusi.
Přidat komentář

22.10.2014 7:18 /MaReK Olšavský
HDMI sticků, které povyšují možnosti TV, je na trhu nepřeberné množství, ale Apec Electronics se nepokouší zaujmout nejlevnější cenou. Za US$ 110 dostanete Android běžící na 4 jádrovém Atomu (takže platformu x86), přičemž místo Androidu lze pořídit verzi s MS Windows 8.1.
Přidat komentář

21.10.2014 7:34 /MaReK Olšavský
Ačkoliv je Debian poměrně konzervativní distribucí, je kolem něj živo. Vedle vydání Debianu 7.7 může zaujmout skupina vývojářů, kteří chystají další fork Debianu, jenž chtějí „osadit“ systemd, namísto stávajícího sysvinit.
Přidat komentář

21.10.2014 7:17 /MaReK Olšavský
OpenBSD se, nedlouho před vydáním další finální verze, dostalo k významnému milníku, 300 000. commitu v repozitářích.
Přidat komentář

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

> Poslední diskuze

16.10.2014 7:56 / Leo
Sanba

13.10.2014 7:20 / MaReK Olšavský
Re: PDF a podpis

10.10.2014 8:01 / Hynek Beran
PDF a podpis

10.10.2014 7:41 / Dusan Hlavac
Re: Takže nic.

10.10.2014 6:36 / MaReK Olšavský
Re: Může, ale nemusí

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