Koodi jõudlus Fibonacci arvude genereerimisel
30.05.2009 | Gunnar
See kanne on küll sissejuhatuseks järgmisele, kuid otsustasin teema juures pisut põhjalikumalt peatuda ja veidike koodiga mängida. Selles kandes genereerime Fibonacci arve, kasutades kahte erinevat funktsiooni, mis oma algoritmilt on tegelikult samad. Huvipakkuvaks teemaks on funktsioonide jõudluse võrdlemine.
Järgmiseks vaatame kahte Fibonacci arvude genereerimise algoritmi teostusest.
Rekursiivne funktsioon
Esimesena võtame käsile lühema ja lihtsama versiooni algoritmi teostusest.
{
if (x == 0 || x == 1)
return x;
return FibonacciRecursive(x - 1) +
FibonacciRecursive(x - 2);
}
Kogenud programmeerijad hoiavad praegu kahe käega pead kinni ja keelduvad seda versiooni ilma jõudluse osas testimata toast välja lubama. Esimene põhjust selgub kande lõpus, teise põhjuse lobisen kohe välja – rekursiivset koodi on keerukam testida ja siluda.
“Lame” funktsioon
Nüüd vaatame funktsiooni teist versiooni. See on pikem ja keerukam lugeda, kuid see-eest ei ole see rekursiivne.
{
var previousValue = -1;
var currentResult = 1;´
for (var i = 0; i <= x; ++i)
{
var sum = currentResult + previousValue;
previousValue = currentResult;
currentResult = sum;
}
return currentResult;
}
Vaatame nüüd, kuidas need kaks versiooni samast asjast jõudluse osas käituvad.
Mõõdame jõudlust
Nüüd jõuame selle kohani, kus tuleb välja rekursiivse versiooniga seotud probleem. Muide, algajad programmeerijad ei pruugi seda probleemi avastada enne kui see produktsioonis tekib, sest paljud algajad testivad oma funktsioone küllaltki piiratud tingimustega ning korralikke mõõtmisi nad tavaliselt ei tee. Aga vaatame tulemusi.
Horisontaalses teljel on toodud funktsiooni sisendväärtused. Vertikaalsel teljel aga aeg sekundites, mis vastava sisendi juures väärtuse arvutamiseks kulus. Näeme, et orienteeruvalt 30 juures hakkab rekursiivse funktsiooni jõudlus langema eksponentsiaalselt.
Muide, see näide ei kehti ainult Fibonacci arvude genereerimise korral. Analoogset eksponentsiaalset jõudluse kadu võime märgata ka muude rekursiivsete funktsioonide korral – näiteks faktoriaali arvutamine.
Märkus. Funktsionaalsed keeled on ehitatud enamasti üles pisut teistmoodi ja nendele me ei saa siintoodut laiendada. Ma testisin rekursiivset versiooni sellise funktsionaalse keele nagu F# peal ja seal oli selle funktsiooni jõudlus umbes nagu siinsel “lamedal” versioonil.
30.05.2009 kell 20:36
Mis on hetke seis C# kompilaatoril saba-rekursiooni toetamisel (tail recursion)? Ma kiire googeldamisega ei leidnud väga head ülevaadet. Kui leiad midagi siis huvitaks, et kui on tulnud siis millal ja ehk mõni asjalik link. Olen natsi teise platvormi peal ja ei oska kippelt hinnata .NET blogi postide sisu paikapanevust.
30.05.2009 kell 21:40
tom_, proovi neid linke, äkki on abiks:
Tail recursion on .NET
Siin selgitatakse, et C# kompilaator tail-recursioni osas mingeid optimeerimisi ei tee. Samas on IL tasemel võimalik vastavad muudatused sisse viia. 64-bitisel platvormil teeb siiski kompilaator vastavad kohendused ise ära. Muude kompilaatorite osas ei oska ma kaasa rääkida.
Paar linki veel MSDN-i blogidest:
Tail call performance on x86
Tail call JIT conditions
Äkki on abiks