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