Hashlife es un algoritmo memorizado para calcular el destino a largo plazo de una configuración inicial dada en el Juego de la vida de Conway y los autómatas celulares relacionados , mucho más rápido de lo que sería posible usando algoritmos alternativos que simulan cada paso de tiempo de cada celda del autómata. El algoritmo fue descrito por primera vez por Bill Gosper a principios de la década de 1980 mientras realizaba una investigación en el Centro de Investigación Xerox Palo Alto . Hashlife se implementó originalmente en máquinas Symbolics Lisp con la ayuda de la extensión Flavours .
Hashlife
Hashlife está diseñado para explotar grandes cantidades de redundancia espacial y temporal en la mayoría de las reglas de Life. Por ejemplo, en Conway's Life , muchos patrones aparentemente aleatorios terminan como colecciones de simples bodegones y osciladores .
Representación
El campo se trata típicamente como una cuadrícula teóricamente infinita , con el patrón en cuestión centrado cerca del origen . Se utiliza un árbol cuádruple para representar el campo. Dado un cuadrado de 2 2 k celdas, 2 k en un lado, en el k- ésimo nivel del árbol, la tabla hash almacena el cuadrado de 2 k −1 por 2 k −1 de celdas en el centro, 2 k - 2 generaciones en el futuro. Por ejemplo, para un cuadrado de 4 × 4, almacena el centro de 2 × 2, una generación hacia adelante; y para un cuadrado de 8 × 8 almacena el centro de 4 × 4, dos generaciones adelante.
Hashing
Si bien un árbol cuádruple generalmente tiene mucha más sobrecarga que otras representaciones más simples (como el uso de una matriz de bits ), permite varias optimizaciones. Como sugiere el nombre, el algoritmo utiliza tablas hash para almacenar los nodos del quadtree. Muchos subpatrones del árbol suelen ser idénticos entre sí; por ejemplo, el patrón que se está estudiando puede contener muchas copias de la misma nave espacial , o incluso grandes franjas de espacio vacío. Todos estos subpatrones utilizarán el hash en la misma posición en la tabla hash y, por lo tanto, se pueden almacenar muchas copias del mismo subpatrón utilizando la misma entrada de la tabla hash. Además, estos subpatrones solo deben evaluarse una vez, no una vez por copia como en otros algoritmos de Life.
Esto en sí mismo conduce a mejoras significativas en los requisitos de recursos; por ejemplo, una generación de los diversos reproductores y rellenos espaciales , que crecen a velocidades polinomiales , se puede evaluar en Hashlife utilizando espacio y tiempo logarítmicos .
Supervelocidad y almacenamiento en caché
Se puede lograr una aceleración adicional para muchos patrones evolucionando diferentes nodos a diferentes velocidades. Por ejemplo, se podría calcular el doble del número de generaciones hacia adelante para un nodo en el nivel ( k + 1) -ésimo en comparación con uno en el k- ésimo. Para patrones dispersos o repetitivos, como el cañón de planeador clásico , esto puede resultar en tremendas aceleraciones, lo que permite calcular patrones más grandes en generaciones superiores más rápido , a veces exponencialmente . Para aprovechar al máximo esta función, también se deben guardar los subpatrones de generaciones pasadas .
Dado que se permite que diferentes patrones se ejecuten a diferentes velocidades, algunas implementaciones, como el propio hlife
programa de Gosper , no tienen una pantalla interactiva, sino que simplemente calculan un resultado final preestablecido para un patrón de inicio, generalmente se ejecuta desde la línea de comandos . Los programas más recientes como Golly , sin embargo, tienen una interfaz gráfica que puede impulsar un motor basado en Hashlife.
El comportamiento típico de un programa Hashlife en un patrón propicio es el siguiente: primero, el algoritmo se ejecuta más lento en comparación con otros algoritmos debido a la sobrecarga constante asociada con el hash y la construcción del árbol ; pero más tarde, se recopilarán suficientes datos y su velocidad aumentará enormemente; el rápido aumento de la velocidad a menudo se describe como " explosivo ".
Inconvenientes
Como muchos códigos memorizados , Hashlife puede consumir significativamente más memoria que otros algoritmos, especialmente en patrones de tamaño moderado con mucha entropía, o que contienen subpatrones mal alineados con los límites de los nodos de cuatro árboles (es decir, potencia de dos tamaños); la caché es un componente vulnerable. También puede consumir más tiempo que otros algoritmos en estos patrones. Golly , entre otros simuladores de Life, tiene opciones para alternar entre Hashlife y algoritmos convencionales.
Hashlife también es significativamente más complejo de implementar . Por ejemplo, necesita un recolector de basura dedicado para eliminar los nodos no utilizados de la caché.
Debido a que están diseñadas para procesar patrones generalmente predecibles, las reglas caóticas y explosivas generalmente operan mucho peor bajo Hashlife que bajo otras implementaciones. [1]
Ver también
- Estructura de datos puramente funcional , de los cuales el quadtree con hash es uno
- Consing de Hash , que fue la estrategia clave utilizada en la implementación original de Hashlife.
Referencias
- Gosper, Bill (1984). "Explotación de regularidades en grandes espacios celulares". Physica D . Elsevier. 10 (1–2): 75–80. doi : 10.1016 / 0167-2789 (84) 90251-3 .
enlaces externos
- HashLife de Eric Weisstein's Treasure Trove of Life
- Implementación de hashlife de Tomas Rokicki
- Entrada en el léxico de la vida
- Explicación del algoritmo del Dr. Dobb's Journal
- Explicación del algoritmo de Gosper (Hashlife)
- ^ Descripción del algoritmo HashLife en Golly: "Tenga en cuenta que HashLife funciona muy mal en patrones altamente caóticos, por lo que en esos casos es mejor que se cambie a QuickLife".