Хэшлайф

6 366 548 773 467 669 985 195 496 000 (6 октиллионное ) поколение машины Тьюринга в Life вычислено менее чем за 30 секунд на процессоре Intel Core Duo 2 ГГц с использованием Hashlife in Golly . Вычисляется путем обнаружения повторяющегося цикла в шаблоне и перехода к любому запрошенному поколению.

Hashlife — это мемоизированный алгоритм для вычисления долгосрочной судьбы заданной стартовой конфигурации в «Игре жизни Конвея» и связанных с ней клеточных автоматах , гораздо быстрее, чем это было бы возможно с использованием альтернативных алгоритмов, моделирующих каждый временной шаг каждой ячейки автомата. Алгоритм был впервые описан Биллом Госпером в начале 1980-х годов, когда он занимался исследованиями в исследовательском центре Xerox в Пало-Альто . Hashlife изначально был реализован на с символикой машинах Lisp с помощью расширения Flavors .

Хэшлайф

Hashlife предназначен для использования большого количества пространственной и временной избыточности в большинстве правил Life. Например, в «Жизни Конвея» многие, казалось бы, случайные узоры в конечном итоге превращаются в коллекции простых натюрмортов и осцилляторов . Однако срок хеширования не зависит от того, остаются ли шаблоны в одном и том же положении; речь идет скорее об использовании того факта, что крупные шаблоны имеют тенденцию иметь подшаблоны, которые появляются в нескольких местах, возможно, в разное время.

Представительство

Поле обычно рассматривается как теоретически бесконечная сетка с структуры центром рассматриваемой вблизи начала координат . квадродерево общим (с доступом Для представления поля используется к узлам). Узел на k- м уровне дерева представляет собой квадрат из 2 ^{22 тыс.} клетки, 2 ^к на стороне, ссылаясь на четыре узла уровня k –1, которые представляют четыре $2^{k-1}\times 2^{k-1}$ квадранты этого уровня k квадрат. Например, узел уровня 3 представляет собой квадрат 8×8, который распадается на четыре квадрата 4×4. Явное содержимое ячеек хранится только на уровне 0. Корневой узел должен находиться на достаточно высоком уровне, чтобы все живые ячейки находились в пределах квадрата, который он представляет.

Хотя наивно кажется, что квадродерево требует гораздо больше накладных расходов , чем более простые представления (например, использование ) матрицы битовой , оно допускает различные оптимизации. Поскольку каждая ячейка либо жива, либо мертва, существует только две возможности для узла на уровне 0, поэтому, если узлы разрешены для совместного использования родительскими узлами, никогда не возникает необходимости иметь в общей сложности более двух узлов уровня 0. Аналогично, 4 клетки квадрата 2×2 могут содержать только $2^{4}=16$ различные комбинации, поэтому требуется не более этого количества узлов уровня 1. При переходе на более высокие уровни количество возможных клеток k- го уровня растет как $2^{2^{k}\cdot 2^{k}}=2^{2^{2k}}$, но количество различных квадратов k -го уровня, встречающихся в каждом отдельном проходе, намного меньше, и очень часто одно и то же содержимое квадрата появляется в нескольких местах. Для максимального совместного использования узлов в квадродереве (которое является не столько деревом , сколько ориентированным ациклическим графом ) мы хотим использовать только один узел для представления всех квадратов с одинаковым содержимым.

Хеширование

Хэш -таблица или, в более общем смысле, любой вид ассоциативного массива может использоваться для сопоставления квадратного содержимого с уже существующим узлом, представляющим это содержимое, так что с помощью метода хэш-консинга можно избежать создания дублирующего узла, представляющего это содержимое. Если это применяется последовательно, то достаточно хешировать четыре указателя на узлы компонентов, поскольку хеширование содержимого квадрата снизу вверх всегда будет находить эти четыре узла на уровне ниже. Оказывается, некоторые операции над узлами более высокого уровня можно выполнять без явного создания содержимого этих узлов, вместо этого достаточно работать с указателями на узлы, расположенные на фиксированное количество уровней ниже.

Кэширование и сверхскорость

Квадродерево может быть дополнено в узле, а также кэшировать результат обновления содержимого этого узла. Недостаточно информации в $2^{k}\times 2^{k}$ квадрат, чтобы определить содержимое следующего временного шага для всего этого квадрата, но содержимое $2^{k+1}\times 2^{k+1}$ квадрат с центром в той же точке определяет содержимое следующего временного шага $2^{k}\times 2^{k}$ квадрат. Этот узел уровня k для следующего временного шага смещен на $2^{k-1}$ ячеек как в горизонтальном, так и в вертикальном направлениях, поэтому даже в случае натюрморта он, скорее всего, не будет среди узлов уровня k , которые объединяются в $2^{k+1}\times 2^{k+1}$ квадрат, но на уровне k –1 квадраты снова занимают те же позиции и будут разделены, если они не изменятся.

Практически вычисление содержимого следующего временного шага представляет собой рекурсивную операцию, которая снизу вверх заполняет поле кэша каждого узла уровня k узлом уровня k –1, представляющим содержимое обновленного центра. $2^{k-1}\times 2^{k-1}$ квадрат. Совместное использование узлов может значительно ускорить эту операцию, поскольку требуемая работа пропорциональна количеству узлов, а не количеству ячеек, как в более простом представлении. Если узлы распределяются между квадродеревьями, представляющими разные временные шаги, то только те узлы, которые были вновь созданы в течение предыдущего временного шага, вообще должны будут иметь вычисленное кэшированное значение.

Superspeed идет еще дальше, используя наблюдение о том, что содержимое $2^{k+1}\times 2^{k+1}$ квадрат фактически определяет содержимое его центрального $2^{k}\times 2^{k}$ квадрат для следующего $2^{k-1}$ временные шаги. Вместо того, чтобы узел уровня k кэшировал узел уровня k –1 для содержимого на 1 шаг вперед, мы можем кэшировать один узел для содержимого. $2^{k-2}$ шаги вперед. Поскольку обновления на уровне k вычисляются из обновлений на уровне k -1, а поскольку на уровне k -1 кэшируются результаты для продвижения $2^{k-3}$ временных шагов, всего двух раундов продвижения на уровне k –1 достаточно для продвижения на $2^{k-2}$ шаги на уровне k .

В худшем случае для 2 раундов на уровне k -1 может потребоваться выполнить 4 полных раунда на уровне k -2, что, в свою очередь, потребует 8 полных раундов на уровне k -3 и т. д., но на практике многие подшаблоны в дереве идентичны. друг к другу, и большинство ветвей рекурсии короткие. Например, изучаемый образец может содержать множество копий одного и того же космического корабля и часто большие участки пустого пространства. Каждый экземпляр этих подшаблонов будет хэшироваться с одним и тем же узлом дерева квадрантов, поэтому его нужно сохранить только один раз. Кроме того, эти подшаблоны необходимо оценивать только один раз, а не один раз для каждой копии, как в других алгоритмах Life.

Для разреженных или повторяющихся шаблонов, таких как классическая планерная пушка , это может привести к огромному ускорению, позволяя вычислять более крупные шаблоны на более высоких поколениях быстрее , иногда экспоненциально . Поколение различных заводчиков и заполнителей пространства , которые растут с полиномиальной скоростью, можно оценить в Hashlife, используя логарифмическое пространство и время.

Поскольку подшаблоны разных размеров эффективно выполняются с разной скоростью, некоторые реализации, такие как собственная программа Госпера hlife, не имеют интерактивного дисплея; они просто продвигают начальный шаблон на заданное количество шагов и обычно запускаются из командной строки . Однако более поздние программы, такие как Golly , имеют графический интерфейс, который может управлять движком на основе Hashlife.

Типичное поведение программы Hashlife при благоприятном шаблоне следующее: во-первых, алгоритм работает медленнее по сравнению с другими алгоритмами из-за постоянных накладных расходов, связанных с хешированием и построением дерева ; но позже будет собрано достаточно данных, и его скорость значительно увеличится – быстрое увеличение скорости часто называют « взрывным ».

Недостатки

Как и многие мемоизированные коды, Hashlife может потреблять значительно больше памяти , чем другие алгоритмы, особенно для шаблонов среднего размера с большой энтропией или которые содержат подшаблоны, плохо выровненные по границам узлов квадродерева (т. е. размеры степени двойки); кэш является уязвимым компонентом. Он также может потребовать больше времени, чем другие алгоритмы на этих шаблонах. Golly , среди других симуляторов Life, имеет возможность переключения между Hashlife и обычными алгоритмами.

Hashlife также значительно сложнее реализовать . Например, ему нужен специальный сборщик мусора для удаления неиспользуемых узлов из кэша.

Поскольку хаотичные и взрывоопасные правила предназначены для обработки в целом предсказуемых шаблонов, они обычно работают гораздо хуже в Hashlife, чем в других реализациях.

См. также

• Чисто функциональная структура данных , одной из которых является хешированное квадродерево.
• Hash consing — ключевая стратегия, использованная в первоначальной реализации Hashlife.

Ссылки

• Госпер, Билл (1984). «Использование закономерностей в больших сотовых пространствах». Физика Д. 10 (1–2). Эльзевир: 75–80. дои : 10.1016/0167-2789(84)90251-3 .

Внешние ссылки

• HashLife из «Сокровищницы жизни» Эрика Вайсштейна
• Реализация hashlife Томаса Рокицки
• Запись в Жизненном лексиконе
• Объяснение алгоритма из журнала доктора Добба.
• Объяснение алгоритма Госпера (Hashlife). Архивировано из оригинала.