Hashlife - Hashlife
Hashlife é um memoized algoritmo para calcular o destino de longo prazo de uma determinada configuração a partir de Jogo da Vida de Conway e relacionados autômatos celulares , muito mais rapidamente do que seria possível usando algoritmos alternativos que simulam cada passo de tempo de cada célula do autômato. O algoritmo foi descrito pela primeira vez por Bill Gosper no início dos anos 1980, quando ele estava envolvido em pesquisas no Centro de Pesquisas Xerox Palo Alto . Hashlife foi originalmente implementado em máquinas Symbolics Lisp com o auxílio da extensão Flavors .
Hashlife
O Hashlife é projetado para explorar grandes quantidades de redundância espacial e temporal na maioria das regras de vida. Por exemplo, em Vida de Conway , muitos padrões aparentemente aleatórios terminam como coleções de naturezas mortas simples e osciladores .
Representação
O campo é tipicamente tratado como uma grade teoricamente infinita , com o padrão em questão centralizado próximo à origem . Um quadtree é usado para representar o campo. Dado um quadrado de 2 2 k células, 2 k de um lado, no k ésimo nível da árvore, a tabela de hash armazena o quadrado 2 k −1 -by-2 k −1 de células no centro, 2 k - 2 gerações no futuro. Por exemplo, para um quadrado 4 × 4, ele armazena o centro 2 × 2, uma geração à frente; e para um quadrado 8 × 8, ele armazena o centro 4 × 4, duas gerações adiante.
Hashing
Embora uma quadtree normalmente tenha muito mais overhead do que outras representações mais simples (como o uso de uma matriz de bits ), ela permite várias otimizações. Como o nome sugere, o algoritmo usa tabelas hash para armazenar os nós do quadtree. Muitos subpadrões na árvore são geralmente idênticos entre si; por exemplo, o padrão que está sendo estudado pode conter muitas cópias da mesma espaçonave , ou mesmo grandes faixas de espaço vazio. Esses subpadrões serão todos hash para a mesma posição na tabela hash e, portanto, muitas cópias do mesmo subpadrão podem ser armazenadas usando a mesma entrada da tabela hash. Além disso, esses subpadrões só precisam ser avaliados uma vez, não uma vez por cópia, como em outros algoritmos Life.
Isso por si só leva a melhorias significativas nos requisitos de recursos; por exemplo, uma geração de vários criadores e preenchedores de espaço , que crescem em velocidades polinomiais , pode ser avaliada no Hashlife usando espaço e tempo logarítmicos .
Supervelocidade e cache
Uma aceleração adicional para muitos padrões pode ser alcançada através da evolução de nós diferentes em velocidades diferentes. Por exemplo, pode-se calcular duas vezes o número de gerações futuras para um nó no ( k +1) -ésimo nível em comparação com um no k- ésimo. Para padrões esparsos ou repetitivos, como o canhão planador clássico , isso pode resultar em enormes acelerações, permitindo computar padrões maiores em gerações superiores com mais rapidez , às vezes exponencialmente . Para aproveitar ao máximo esse recurso, os subpadrões das gerações anteriores também devem ser salvos .
Uma vez que diferentes padrões podem ser executados em diferentes velocidades, algumas implementações, como o próprio hlifeprograma de Gosper , não têm uma tela interativa, mas simplesmente calculam um resultado predefinido para um padrão inicial, geralmente executado a partir da linha de comando . Programas mais recentes, como Golly , no entanto, têm uma interface gráfica que pode acionar um mecanismo baseado em Hashlife.
O comportamento típico de um programa Hashlife em um padrão favorável é o seguinte: primeiro, o algoritmo é executado mais lentamente em comparação com outros algoritmos por causa da sobrecarga constante associada ao hash e à construção da árvore ; mas mais tarde, dados suficientes serão reunidos e sua velocidade aumentará tremendamente - o rápido aumento na velocidade é freqüentemente descrito como " explosão ".
Desvantagens
Como muitos memoized códigos, Hashlife pode consumir significativamente mais memória do que outros algoritmos, especialmente sobre os padrões de tamanho moderado com uma grande quantidade de entropia, ou que contêm subpadrões mal alinhados aos limites dos nodos Quadtree (isto é, poder-de-dois tamanhos); o cache é um componente vulnerável. Ele também pode consumir mais tempo do que outros algoritmos nesses padrões. Golly , entre outros simuladores Life, tem opções para alternar entre Hashlife e algoritmos convencionais.
O Hashlife também é significativamente mais complexo de implementar . Por exemplo, ele precisa de um coletor de lixo dedicado para remover nós não usados do cache.
Por serem projetadas para processar padrões geralmente previsíveis, as regras caóticas e explosivas geralmente funcionam muito mais mal no Hashlife do que em outras implementações.
Veja também
- Estrutura de dados puramente funcional , da qual o quadtree hash é um
- Hash consing , que foi a principal estratégia usada na implementação original do Hashlife.
Referências
- Gosper, Bill (1984). "Explorando regularidades em grandes espaços celulares". Physica D . Elsevier. 10 (1–2): 75–80. doi : 10.1016 / 0167-2789 (84) 90251-3 .
