Hashlife - Hashlife
Hashlife - это мемоизированный алгоритм для вычисления долгосрочной судьбы данной начальной конфигурации в «Игре жизни» Конвея и связанных с ней клеточных автоматах , намного быстрее, чем это было бы возможно при использовании альтернативных алгоритмов, которые имитируют каждый временной шаг каждой ячейки автомата. Алгоритм был впервые описан Биллом Госпером в начале 1980-х годов, когда он занимался исследованиями в Исследовательском центре Xerox в Пало-Альто . Изначально Hashlife был реализован на машинах Symbolics Lisp с помощью расширения Flavors .
Hashlife
Hashlife предназначен для использования большого количества пространственной и временной избыточности в большинстве правил Life. Например, в «Жизни Конвея» многие, казалось бы, случайные паттерны превращаются в коллекции простых натюрмортов и осцилляторов .
Представление
Поле обычно рассматривается как теоретически бесконечная сетка с центром рассматриваемого шаблона около начала координат . Дерева квадрантов используются для представления поля. Учитывая квадрат из 2 2 k ячеек, 2 k на стороне, на k- м уровне дерева, хеш-таблица хранит квадрат 2 k −1 на 2 k −1 ячеек в центре, 2 k - 2 поколения в будущем. Например, для квадрата 4 × 4 он хранит центр 2 × 2, на одно поколение вперед; а для квадрата 8 × 8 он хранит центр 4 × 4 на два поколения вперед.
Хеширование
В то время как квадранты обычно имеют гораздо больше накладные расходы по сравнению с другими более простыми представлениями (например, с использованием матрицы из бит ), она позволяет использовать различные оптимизации. Как следует из названия, алгоритм использует хеш-таблицы для хранения узлов квадродерева. Многие подшаблоны дерева обычно идентичны друг другу; например, изучаемый образец может содержать множество копий одного и того же космического корабля или даже большие участки пустого пространства. Все эти подшаблоны будут хешироваться в одну и ту же позицию в хеш-таблице, и, таким образом, многие копии одного и того же подшаблона могут быть сохранены с использованием одной и той же записи хеш-таблицы. Кроме того, эти подшаблоны нужно оценивать только один раз, а не один раз для каждой копии, как в других алгоритмах Life.
Это само по себе приводит к значительному улучшению требований к ресурсам; например, генерация различных животноводов и spacefillers , которые растут на полиномиальных скоростях, может быть оценена в Hashlife с использованием логарифмического пространства и времени.
Сверхскорость и кеширование
Дальнейшее ускорение для многих шаблонов может быть достигнуто за счет развития разных узлов с разной скоростью. Например, можно вычислить вдвое большее количество поколений вперед для узла на ( k +1) -м уровне по сравнению с одним на k- м уровне. Для редких или повторяющихся шаблонов, таких как классическая планерная пушка , это может привести к огромному ускорению, позволяя вычислять более крупные шаблоны в более высоких поколениях быстрее , иногда в геометрической прогрессии . Чтобы в полной мере воспользоваться этой функцией, необходимо также сохранить подшаблоны прошлых поколений .
Поскольку разные шаблоны могут выполняться с разной скоростью, некоторые реализации, такие как собственная hlifeпрограмма Госпера , не имеют интерактивного дисплея, а просто вычисляют предварительно заданный результат для начального шаблона, обычно запускаемого из командной строки . Однако более поздние программы, такие как Golly , имеют графический интерфейс, который может управлять движком на основе Hashlife.
Типичное поведение программы Hashlife по благоприятному шаблону следующее: во-первых, алгоритм работает медленнее по сравнению с другими алгоритмами из-за постоянных накладных расходов, связанных с хешированием и построением дерева ; но позже будет собрано достаточно данных, и его скорость значительно возрастет - быстрое увеличение скорости часто описывается как « взрывной ».
Недостатки
Как и многие мемоизированные коды, Hashlife может потреблять значительно больше памяти, чем другие алгоритмы, особенно на паттернах среднего размера с большой энтропией или которые содержат подшаблоны, плохо выровненные по границам узлов дерева квадрантов (т.е. размер степени двойки); кеш - уязвимый компонент. Он также может занять больше времени, чем другие алгоритмы по этим шаблонам. У Golly , среди других симуляторов жизни, есть варианты переключения между Hashlife и обычными алгоритмами.
Hashlife также значительно сложнее реализовать . Например, для удаления неиспользуемых узлов из кеша требуется специальный сборщик мусора .
Из-за того, что они предназначены для обработки обычно предсказуемых шаблонов, хаотические и взрывные правила обычно работают намного хуже в Hashlife, чем в других реализациях.
Смотрите также
- Чисто функциональная структура данных , одним из которых является хешированное дерево квадрантов.
- Хеширование , которое было ключевой стратегией, использованной в первоначальной реализации Hashlife.
Рекомендации
- Госпер, Билл (1984). «Использование закономерностей в больших сотовых пространствах». Physica D . Эльзевир. 10 (1–2): 75–80. DOI : 10.1016 / 0167-2789 (84) 90251-3 .
