Přejít k navigační liště

Zdroják » JavaScript » Jak nejlépe spočítat faktoriál v JavaScriptu?

Jak nejlépe spočítat faktoriál v JavaScriptu?

Články JavaScript

Nedávná diskuse na Facebooku mě přiměla, abych toto téma prozkoumal do větších detailů, než mi umožňovaly tamní komentáře. Tato otázka totiž kupodivu nemá jednoduchou odpověď. Když o ní začnete více přemýšlet, ponoříte se do některých zajímavějších oblastí JavaScriptu, které možná ne všichni znají.

Vezměme to od začátku. Všichni známe matematickou definici faktoriálu: „faktoriál nezáporného celého čísla n je roven součinu všech kladných celých čísel menších nebo rovných n“. Navíc aby se některé výpočty zjednodušily (a naše implementace zkomplikovala), faktoriál nuly je definován jako 1.

Pokud jste někdy studovali programování, první ukázka, kterou jste viděli v rámci výuky rekurze, byl nejspíš právě výpočet faktoriálu. Učebnicová implementace by mohla vypadat takto:

function factorialFromDefinition(n) {
    if (n == 0) return 1;
    return n * factorialFromDefinition(n - 1);
}

for (let i = 0; i < 8; i++) {
    console.log("factorial(" + i + ") = " + factorialFromDefinition(i));
}

Když tuto ukázku spustíme, dostaneme očekávaný výstup.

factorial(0) = 1
factorial(1) = 1
factorial(2) = 2
factorial(3) = 6
factorial(4) = 24
factorial(5) = 120
factorial(6) = 720
factorial(7) = 5040

Pokud použijeme tzv. šipkovou notaci funkcí a navíc přepíšeme příkaz if na podmínkový ternární operátor, změní se naše funkce na následující jednořádkový zápis.

const factorialFromDefinitionArrow =
    n => n == 0 ? 1 : n * factorialFromDefinitionArrow(n - 1);ň

Máme krátké a zároveň čitelné řešení; je to tedy vše? Naopak, spíše začínáme.

Potíže s rekurzí

Naše řešení obsahuje dva problémy, které se nemusejí projevit u tak triviálních úloh, jako je počítání faktoriálů, ale mohou nás snadno nemile překvapit při složitějším použití rekurze:

  • Volání funkcí je obecně vzato pomalé. Tady mi budete muset věřit, protože řádná demonstrace by sama o sobě byla poměrně komplikovaná.
  • Existuje určité maximální množství zanoření volání jednotlivých funkcí, které vám programovací jazyk (resp. běhové prostředí, které váš program spouští) dovolí. Pokud toto množství překročíte, narazíte na tak nechvalně známou chybu, že podle ní byl pojmenován mezi programátory velmi populární web.

Bohužel ani tento druhý problém nejde v JavaScriptu předvést na faktoriálech, protože ty rostou tak rychle, že brzy dosáhneme nekonečna:

factorial(170) = 7.257415615307994e+306
factorial(171) = Infinity

Pokud ovšem naši funkci trochu pozměníme a necháme ji počítat trojúhelníkové číslo, snadno vyvoláme chybu typu „stack overflow“.

const triangularNumber =
    n => n == 1 ? 1 : n + triangularNumber(n - 1);

Zatímco volání triangularNumber(10000) vrátí 50005000, volání triangularNumber(100000) způsobí chybu RangeError: Maximum call stack size exceeded.

Iterativní řešení

Vraťme se k faktoriálům. Přestože naše řešení přesně následuje matematickou definici, evidentně má své slabiny (přinejmenším v teoretické rovině). Jak je můžeme vylepšit?

Jestliže problém spočívá v rekurzi, můžeme se jí zbavit. Naštěstí lze faktoriály snadno počítat pomocí cyklu.

const factorialIterative = function(n) {
    if (n == 0) return 1;
    let result = 1;
    for (let i = 2; i <= n; i++) result *= i;
    return result;
}

Jediným nedostatkem tohoto řešení je, že nevypadá úplně funkcionálně, a my přece všichni zbožňujeme funkcionální programování, zvláště v JavaScriptu, že?

Funkcionální řešení bez rekurze

Zkusme to tedy funkcionálně, ale bez rekurze. Můžeme totiž vygenerovat pole čísel od 0 do n a následně použít funkci reduce pro provedení patřičných násobení.

Existuje několik způsobů, jak takové pole vytvořit, ale pokud chcete předvést své pokročilé znalosti JavaScriptu, použijete pochopitelně funkci Array.from: Array.from({length: n + 1}, (_, i) => i). Takto ji použijeme později, nicméně nyní si to trochu usnadníme a použijeme pole od 1 do n. Následným použitím funkce reduce získáme novou jednořádkovou verzi výpočtu faktoriálu.

const factorialArrayReduce = n => Array.from({length: n}, (_, i) => i + 1)
    .reduce((accumulator, currentValue) => accumulator * currentValue);

Nedostatkem je to, že tato varianta neumí spočítat faktoriál nuly, ale když ji trochu rozšíříme, poradíme si i s tímto:

const factorialArrayReduceBetter =
    n => Array.from({length: n + 1}, (_, i) => i)
        .reduce((acc, curr) => acc * (curr == 0 ? 1 : curr), 1);

Použití generátoru

Pokud toto řešení porovnáte s předchozí funkcí factorialIterative, měli byste se zamračit. Za prvé většina lidí uzná, že je to sice hezké, jednořádkové a funkcionální, ale zároveň hůře čitelné než iterativní varianta.

Za druhé je tu ono volání Array.from. Pokud jste to při předchozím čtení přehlédli, toto volání skutečně vytvoří pole všech těch čísel přesně tak, jak jsme požádali. V případě jiné úlohy by takovéto řešení mohlo vést ke skutečně velmi velkému poli (které předně bude zabírat spoustu paměti a za druhé bude i trvat ho vytvořit). Když se nad tím zamyslíme, my je ale vlastně celé vůbec nepotřebujeme – zpracováváme jeho prvky jeden po druhém. Pokud jste někdy slyšeli o generátorech, víte, kam mířím. Pokud ne, uslyšíte o nich nyní.

Generátory jsou objekty schopné postupně vracet (tedy generovat) sekvence hodnot. Pokud jste příznivci jednořádkových zápisů, budete bohužel zklamáni, jelikož pro generátory neexistuje v JavaScriptu nějaký zkrácený zápis obdobný šipkové notaci pro funkce.

Horší je ale to, že přestože přes hodnoty poskytované generátorem můžeme snadno iterovat, pro generátory aktuálně bohužel neexistují obdoby takových metod, jako je třeba reduce; ty jsou definovány pouze pro pole. To znamená, že pro přepsání předchozího řešení si musíme sami implementovat i funkci reduce.

Opět máme dvě varianty řešení (ta jednodušší nezvládne spočíst faktoriál nuly).

function* sequenceGenerator(start, count) {
    let current = start;
    for (let i = 0; i < count; i++) yield current++;
}

const reduce = (iterable, reducer, initialValue) => {
    let accumulator = initialValue;
    for (let current of iterable) accumulator = reducer(accumulator, current);
    return accumulator;
}

const factorialGeneratorReduce =
    n => reduce(sequenceGenerator(1, n), (acc, curr) => acc * curr, 1);

const factorialGeneratorReduceBetter =
    n => reduce(
        sequenceGenerator(0, n + 1),
        (acc, curr) => acc * (curr == 0 ? 1 : curr),
        1
    );

Zapamatování předchozích výsledků

Ještě bychom si měli položit jednu otázku. Co se stane, když v nějakém místě programu zavoláme factorialIterative(100) a později zavoláme factorialIterative(101)? V tu chvíli budeme počítat faktoriál čísla 101 úplně od začátku, přestože kdybychom si předtím zapamatovali faktoriál té stovky, postačilo by nám vynásobit jej číslem 101. Pokud by náš program neustále počítal nějaké faktoriály, mohlo by to vést k výkonnostním potížím.

Tím se dostáváme (konečně) k poslednímu řešení. V něm zavedeme cache pro všechny faktoriály, které jsme v minulosti spočetli. Pokud jsme požádáni o faktoriál nějakého čísla, nejdříve zkontrolujeme, jestli jsme tento faktoriál už v minulosti nepočítali. Pokud ano, okamžitě vrátíme známý výsledek. Pokud ne, spočítáme a uložíme si faktoriály všech čísel až do vstupního parametru a poté vrátíme nově spočtenou hodnotu.

const factorialCached = function() {
    const cache = [1];
    return function(n) {
        if (n >= cache.length) {
            for (let i = cache.length; i <= n; i++) {
                cache[i] = cache[i - 1] * i;
            }
        }
        return cache[n];
    }
}();

Závěr

Jak jsem zmiňoval hned na začátku: otázka „nejlepší“ implementace faktoriálu není tak jednoduchá, jak by se mohla zdát. I implementace jedné z nejjednodušších matematických funkcí má řadu různých řešení a každé z nich má své výhody a nevýhody.

Komentáře

Subscribe
Upozornit na
guest
15 Komentářů
Nejstarší
Nejnovější Most Voted
Inline Feedbacks
View all comments
Ondřej Žára

Otázka přetečení zásobníku volání je ještě krapet komplikovanější, protože ES6 předepisuje TCO, tedy Tail Call Optimization — podporu pro to, aby jisté formy rekurze nezpůsobovaly narůstání velikosti zásobníku.

Tedy ukázka s triangularNumber například v Chrome 71 způsobí skutečně výjimku, zatímco ve Firefoxu 64 vrátí 5000050000. To samo o sobě není důkazem TCO, ale konstatováním, že zmiňované chování se může napříč implementacemi dost lišit.

Ondřej Žára

Celá ta věc pěkně smrdí. ES6 sice o TCO mluví, ale v praxi se k podpoře má málokdo — v Node.js jednu dobu byla pod nějakým experimentálním flagem, ale tato hotová naprogramovaná věc byla následně zcela odstraněna. Fór je v tom, že TCO je geniální konstrukt pro funkcionální programování (také strojovou dokazatelnost a podobně), ale mizí tím možnost inspekce zásobníku. Takže chyby pak nemají tracebacky (nebo je mají chybně) a podobně. Proto je nejisté, zda-li se TCO v JS vůbec uchytí — specifikace nespecifikace.

Co se týče nepředvídatelného chování, osobně bych to tipnul tak, že hloubka zásobníku není omezena číselnou konstantou, ale množstvím nějakého kusu paměti, kterou má interpret zrovna k dispozici. Takže podle aktuální nálady GC to může pokaždé dopadnout různě.

Jarin

Ono to neni ani tak podle nalady GC jako spis podle toho, kdy virtualni masina skonci s optimalizacema. Interpreter a optimalizovany kod maji ruzne velikosti zaznamu na zasobniku, takze zasobnik pretece ruzne (hloubka zasobniku je omezena ciselnou konstantou).

Co se tyka TCO, je to opravdu problem s inspekci zasobniku ve vyjimkach – TCO nici zaznamy na zasobniku, a tak jsou obavy, ze by to rozhodilo ruzne logovaci nastroje.

(Pro uplnost, pracuji v Chrome/v8 teamu.)

R.Th

Trochu bokom, ale nedá mi to:
Citovaná definícia vôbec nehovorí o rekurzii, prečo ju teda factorialFromDefinition() používa?!

Mlocik97

Citovaná definícia vôbec nehovorí o rekurzii, …

co?

Martin Hassman

To je hodně kuriozní otázka a také hodně nesrozumitelná. Takže, co vlastně čekáte za odpověď?

Vladimir L

Ja tomu porozumel tak, ze podle R.Th. se neshoduje rekurzivni definice s Ondrou uvedenou „soucin cisel od 1 do n a v pripade nuly je napevno 1“. Nitpicking, rekurzivni definice faktorialu je taky pekna, ale komentar naznacuje, ze se funkce mela jmenovat v kontextu clanku factorialRecursive a myslim, ze ocekava autorovo vysypani si popela na hlavu :).

FilipJirsak

Žádná definice matematického jevu nebo problému nemluví o rekurzi. Rekurze je jenom jeden z možných způsobů implementace. A řekl bych, že v případě článku je vztah integrálu a použití rekurze opačný, než to na první pohled vypadá – sice je to napsané tak, že autor chtěl spočítat faktoriál, tak použil rekurzi, ale spíš to bude opačně, že chtěl psát o rekurzi, a k tomu se často jako příklad používá právě faktoriál. Protože samotná implementace je triviální a neodvádí tak pozornost čtenáře od podstaty, kterou je rekurze, nikoli nějaký výpočet.

Razor

To je blbost. Spousta matematických definic a problémú hovoří o rekurzi.

Martin Hassman

Celé se to komplikuje tím, že slovo rekurze může mít dle kontextu více významů, viz třeba https://cs.wikipedia.org/wiki/Rekurze S příchodem více lidí a komentářů (tj. typicky krátkých textů, kde je kontext jasný spíše hůře nebo vůbec) se diskuse stává obtížnou ne-li nemožnou.

bofteam

Někdy používám funkcionální zápis ve smyslu níže, i když to možná není uplně čisté.

const f = (n) => ((n > 1) ? Array.from({length: n}).reduce((a, v, i) => (a * (i + 1)), 1) : 1);
Tomáš Roll

Nejrychlejší je tabulka.

EuroAsm

Přesně tak. Zkoušel jsem vytvořit statickou tabulku makrem v asembleru a jde to bez rekurze i s rekurzí.

fortran1986

Pekný článok ďakujem autorovi… len ma udivuje keď sa ľudia snažia programovať funkcionálne v imperatívnom jazyku ako JS, ktorý nemá ani podporu TCO (aj keď dá sa doplnmiť pomocou trampoline funkcie) ani podporu curried funkcií bez ktorých je funkcionálne programovanie IMHO peklo.

Moja rekurzívna funkcia v F#: https://tinyurl.com/factorial-f má 3 riadky (dala by sa skrátiť aj na jeden ale to už by bolo neprehľadné). F# kód sa kompiluje sa do JS. To Mko za číslicami znamená literál pre typ decimal. Predtým som tam mal integer ale ten veľmi rýchlo pretiekol. Zvolil som decimal lebo ten má najmenej obmedzení. BigInt by som asi použil skôr, ale ten je objektový a to by už potom nemalo taký elegantný zápis.

Enum a statická analýza kódu

Mám jednu univerzální radu pro začínající programátorty. V učení sice neexistují rychlé zkratky, ovšem tuhle radu můžete snadno začít používat a zrychlit tak tempo učení. Tou tajemnou ingrediencí je statická analýza kódu. Ukážeme si to na příkladu enum.