Hashlife - Hashlife
Hashlife je memoizovaný algoritmus pro výpočet dlouhodobého osudu dané počáteční konfigurace v Conwayově hře o život a souvisejících celulárních automatech , mnohem rychleji, než by bylo možné pomocí alternativních algoritmů, které simulují každý časový krok každé buňky automatu. Algoritmus poprvé popsal Bill Gosper na začátku 80. let, když se věnoval výzkumu ve výzkumném středisku Xerox Palo Alto Research Center . Hashlife byl původně implementován na strojích Symbolics Lisp pomocí rozšíření Flavours .
Hashlife
Hashlife je navržen tak, aby využíval velké množství prostorové a časové redundance ve většině životních pravidel. Například v Conwayově životě končí mnoho zdánlivě náhodných vzorů jako sbírky jednoduchých zátiší a oscilátorů .
Zastoupení
Pole je typicky považováno za teoreticky nekonečnou mřížku s dotyčným vzorem vycentrovaným blízko počátku . K reprezentaci pole se používá čtvercový strom . Vzhledem k čtverci 2 2 k buněk, 2 k na straně, na k té úrovni stromu, hash tabulka ukládá 2 k −1 -by-2 k −1 čtverec buněk do středu, 2 k - 2 generace v budoucnosti. Například pro čtverec 4 × 4 ukládá střed 2 × 2, jednu generaci dopředu; a pro čtverec 8 × 8 ukládá střed 4 × 4, dvě generace vpřed.
Hashing
Zatímco quadtree má obvykle mnohem větší režii než jiné jednodušších reprezentací (například za použití matrice z bitů ), umožňuje různé optimalizace. Jak název napovídá, algoritmus používá hašovací tabulky k ukládání uzlů kvadrantového stromu. Mnoho podvzorů ve stromu je obvykle navzájem identických; například studovaný vzor může obsahovat mnoho kopií stejné kosmické lodi nebo dokonce velké řádky prázdného prostoru. Všechny tyto podvzorky budou mít hash na stejné pozici v hašovací tabulce, a tak lze pomocí stejné položky hash tabulky uložit mnoho kopií stejného podvzorku. Kromě toho je nutné tyto dílčí vzory vyhodnotit pouze jednou, nikoli jednou na kopii jako v jiných algoritmech Life.
To samo o sobě vede k významnému zlepšení požadavků na zdroje; například generace různých chovatelů a spacefillers , které rostou na polynomu rychlostech, může být hodnocena v Hashlife pomocí logaritmického prostor a čas.
Superrychlost a ukládání do mezipaměti
Dalšího zrychlení mnoha vzorů lze dosáhnout vyvíjením různých uzlů při různých rychlostech. Například by bylo možné vypočítat dvojnásobný počet generací dopředu pro uzel na ( k +1) -té úrovni ve srovnání s jednou na k- té. U řídkých nebo opakujících se vzorů, jako je klasická zbraň kluzáků , to může vést k obrovskému zrychlení, což člověku umožní rychlejší , někdy exponenciálně, počítat větší vzory u vyšších generací . Chcete-li plně využít této funkce, měli byste také uložit podvzorky z minulých generací .
Vzhledem k tomu, že různé vzory mohou běžet při různých rychlostech, některé implementace, jako je vlastní hlifeprogram Gosper , nemají interaktivní displej, ale jednoduše vypočítají přednastavený výsledek pro počáteční vzor, obvykle spuštěný z příkazového řádku . Novější programy, jako je Golly , však mají grafické rozhraní, které může řídit motor založený na Hashlife.
Typické chování programu Hashlife na příznivém vzoru je následující: nejprve algoritmus běží pomaleji ve srovnání s jinými algoritmy kvůli konstantní režii spojené s hashováním a budováním stromu ; ale později se shromáždí dostatek dat a jejich rychlost se ohromně zvýší - rychlé zvýšení rychlosti se často označuje jako „ explodující “.
Nevýhody
Stejně jako mnoho jiných memoizovaných kódů, i Hashlife může spotřebovat podstatně více paměti než jiné algoritmy, zejména u vzorů střední velikosti se spoustou entropie, nebo které obsahují podvzorky špatně zarovnané s hranicemi uzlů kvadrantového stromu (tj. Síla dvou velikostí); mezipaměť je zranitelná součást. Může také spotřebovat více času než jiné algoritmy na těchto vzorcích. Golly má mimo jiné simulátory života možnosti přepínání mezi Hashlife a konvenčními algoritmy.
Hashlife je také výrazně složitější realizovat . Například potřebuje vyhrazený garbage collector k odstranění nepoužívaných uzlů z mezipaměti.
Kvůli tomu, že jsou navrženy pro zpracování obecně předvídatelných vzorců, fungují chaotická a výbušná pravidla v rámci Hashlife obecně mnohem horší než v jiných implementacích.
Viz také
- Čistě funkční datová struktura , z nichž jedním je hašovaný čtyřstrom
- Hash consing , což byla klíčová strategie použitá při původní implementaci Hashlife.
Reference
- Gosper, Bill (1984). "Využití pravidel ve velkých celulárních prostorech". Physica D . Elsevier. 10 (1–2): 75–80. doi : 10.1016 / 0167-2789 (84) 90251-3 .
