lightln216 июл в 11:57

HashLife на питоне

8 мин

10K

Алгоритмы *

+12

Комментарии 12

wataru 16 июл в 20:33

Вообще, стандартный hashlife работает чуть-чуть по-другому. Там используется степень 2, а не 3. Откуда вы вообще 3 взяли?

Результат эволюции куска 2^n x 2^n через 2^(n-1) шагов однозначно определяется куском 2^(n+1) x 2^(n+1). Поэтому там сохраняются именно эти результаты: для куска 2^(n+1) сохраняется результат в центре размера 2^n через 2^(n-1) шагов При n >= 1. Т.е. самый маленький кусок, который вы считаете, это 4x4 через один шаг и сохраняете внутренний квадрат 2x2.

Потом, чтобы подсчитать ответ для n>1 вы отдельно считаете 9 квадратов для n-1 окаймляющих внутренний кусок, составив из них квадрат размера 2^n + 2^(n-2) через 2^(n-2) шага, потом через 4 квадрата для n-1 вы получаете ответ для внутреннего квадрата еще через 2^(n-2) шагов.

Вроде как на этих картинках цветные квадраты отмечены:

9 квадратов 4x4. Их центральные 2x2 блоки составляют квадрат 6x6

4 квадрата 4x4. Их внутренние 2x2 блоки составляют квадрат 4x4

Как у вас, надо будет всех внуков корня квадро-дерева выписать в квадрат 4x4, из них собирать куски 2x2. Потом результаты записать в матрицу 3x3, там опять составить блоки 2x2, результат даст блок 2x2 который надо взять в ответ, составив из них квадро-дерево.

Это сильно эффективнее вашего варианта со сторонами из степени 3. Тут надо всего 13=9+4 рекурсивных шагов, а не 83=49+25+9. Плюс нужно 2 последовательных шага эволюций, а не 3 как у вас, так что если параллелить, то там меньше зависимостей по вычислениям.

С другой стороны, тут экспоненциальный рост идет с основанием 2, а не 3, так что высота рекурсивного дерева для заданного количества шагов будет выше в log_2(3) раз. Но каждая вершина будет в 6 раз менее ветвиста. Так что в целом количество возможных вершин гораздо меньше, ибо 13^log_2(3) = 58.28.. < 83.

lightln2 16 июл в 21:41

Это сильно эффективнее вашего варианта со сторонами из степени 3.

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

Откуда вы вообще 3 взяли?

Я делал оба варианта hashlife для версии клеточного автомата (не “жизнь”, но не принципиально), в которой много структур, симметричных относительно сдвига на 3^k клеток, но не на 2^k. Моя версия действительно была быстрее (в пять раз), но что я не ожидал, что реализация будет проще, чем квадродерево. К тому же, мне идея эволюции квадрата 3x3 кажется более естесственной, чем 4x4 - собственно, я и хотел этим поделиться.

Была еще и другая конфигурация, в которой симметрия была фрактальной со сдвигом 2^k. Ожидаемо, там стандартный hashlife работал за логарифм, а мой вариант вырождался в линию.

У меня недостаточно данных, чтобы утверждать, какой из вариантов лучше на практике в среднем. Навскидку, вариант с квадродеревом требует меньше памяти, но вариант с 3x3-деревом легче написать и отладить.

wataru 17 июл в 07:20

К тому же, мне идея эволюции квадрата 3x3 кажется более естесственной, чем 4x4 - собственно, я и хотел этим поделиться.

В целом согласен. С листом особенно просто получается.

lightln2 18 июл в 11:01

Я поразмышлял на досуге, тут вообще получается интересно.

Рассмотрим обобщенный клеточный автомат, у которого состояние клетки зависит от целой окрестности $p \times p$ , p = 3,5,7,… нечётно (в частном случае, может быть обычный автомат, в котором мы ходим сразу на шагов). Тогда тот же подход позволяет использовать $p \times p$ -дерево, с листом $1 \times 1$ , и эволюцией поля в этапов

$p^2 \times p^2 \to (p^2 - (p-1)) \times (p^2 - (p-1)) \to (p^2 - 2(p-1)) \times (p^2 - 2(p-1)) \dots \to p \times p$

Тогда эволюция узла будет $p^k \times p^k \to p^{k-1} \times p^{k-1}$ за $p^{k-1}$ шагов.

Но также мы можем поменять размер листа $1 \times 1 \to d \times d$ , тогда база эволюции будет $(p-1+d) \times (p-1+d) \to d \times d$ . Если мы подберем d так, чтобы было маленькое и целое, то мы можем сделать эволюцию в $s \times s$ дереве, узла $s^kd \times s^kd \to s^{k-1}d \times s^{k-1}d$ за $s^{k-1}$ шагов. То есть, мы разменяли часло шагов на размер узла и сложность его эволюции.

Альтернативно, мы можем сделать s степенью маленького целого, тогда можно уменьшить размер узла. Например, вместо $4 \times 4$ -дерева можно взять квадродерево, но в эволюции раскрывать не два уровня вложенности, а четыре. То есть, мы разменяли число шагов и сложность эволюции на размер узла.

Например, возьмем - стандартную окрестность. Тогда стандартная эволюция в $3 \times 3$ -дереве с листом $1 \times 1$ - мой вариант, или, если возьмем , будет эволюция в квадродереве с листом $2 \times 2$ - классический hashlife!

Если взять , то есть варианты:

$5 \times 5$ -дерево, лист $1 \times 1$ ,
$3 \times 3$ -дерево, лист $2 \times 2$ ,
квадродерево, лист $3 \times 3$ .

Для варианты:

$7 \times 7$ -дерево, лист $1 \times 1$ ,
$4 \times 4$ -дерево, лист $2 \times 2$ (можно использовать квадродерево, и раскрывать 4 уровня),
$3 \times 3$ -дерево, лист $3 \times 3$ ,
квадродерево, лист $6 \times 6$ .

В общем, в этом подходе, вариант $3 \times 3$ (и $p \times p$ в общем случае) является “естессвенным”, а hashlife получается как размен скорости эволюции на размер дерева и сложности шага эволюции. Было бы интересно провести анализ, но мне кажется, если все учесть, то асимптотически все варианты будут одинаковы.

wataru 18 июл в 12:02

Асимптотически там везде K^n для n шагов. К зависит от того, как выбирать дерево. Чем больше промежуточных шагов, тем больше K. Все они экспоненциальны, но асимптотически различимы.

lightln2 17 июл в 06:40

Как у вас, надо будет всех внуков корня квадро-дерева выписать в квадрат 4x4

Я сделал аналогичный код для квадродерева, по сложности получается примерно таким же! Усложняется эволюция листа, но упрощается эволюция корня. На моем примере вариант с квадродеревом работает в три раза быстрее, но при этом количество обработанных узлов - в пять раз меньше (то есть, время обработки одного узла сильно хуже, по крайней мере, в данной реализации на питоне).

hashlife3x3

hashlife2x2

Но все равно мне вариант с 3x3 кажется интуитивно более понятным.

wataru 17 июл в 07:24

Быстро вы сделали, мое уважение.

при этом количество обработанных узлов - в пять раз меньше

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

wataru 18 июл в 12:22

А вот такой вопрос возник, что вы по этому поводу думаете?

Вот есть у нас поле, допустим оно все помещается в 3^k x 3^k. Допустим мы хотим получить все поле через 3^n шагов (n >> k). Вроде бы легко - расширяем поле с ранга k до ранга n+1 пустыми полями. Потом выполняем один шаг и получаем точный размер поля 3^n x 3^n.

Но, скорость света в игре жизнь - 1. Через 3^n шагов изначальное поле 3^k x 3^k может расползтись до (3^n+3^k) x (3^n + 3^k), что больше поля 3^n x 3^n. Т.е. чтобы получить все поле надо будет сделать шаг параллельно на нескольких полях, так? Это очень похоже на первый шаг во время эволюции состояния.

Похоже, у вас именно так и делается - вы там корень помещаете в центр массива 5x5. Это удобно делать когда дерево нечетное, с центром, как у вас 3x3.

Как это делается для дерева 2x2 вообще? В вашей реализации выше я такой обработки не нашел. Кажется, можно поместить состояние в центр массива 3x3 и сделать 4 эволюции блоков 2x2 и получить 4 квадранта ответа.

И оффтопик, я тут поэксперементировал и выяснил, что если добавить в мапу состояний 0: [0, 0, 0, ... 0] для обозначения пустого поля любого размера, то это упрощает код (не надо отдельного make_empty), и немного сокращает количество состояний. Только вместо проверки, что у вас лист 0 или 1 надо помнить какого размера текущее поле.

lightln2 18 июл в 13:27

Как это делается для дерева 2x2 вообще? В вашей реализации выше я такой обработки не нашел. Кажется, можно поместить состояние в центр массива 3x3 и сделать 4 эволюции блоков 2x2 и получить 4 квадранта ответа

Тут я, похоже, ошибся: я хотел упростить, и корень $s^k \times s^k$ увеличиваю дважды до $s^{k+2}$ , и делаю ему evolve, и проблема в вашем агрументе про скорость света. Тут оно работает, потому что живые клетки в стандартных правилах “жизни” не могут двигаться быстрее, чем на T/2 клеток за T шагов, поэтому в корне всегда достаточно пустого периметра. Но для произвольного автомата, вы правы, поле может разрастить быстрее.

Поэтому, видимо, в общем случае надо делать последний этап в эволюции:

Для 3x3: 9x9 -> 7x7 -> 5x5 -> 3x3, нужен один этап 5x5 -> 3x3
для 2x2: 4x4 -> 3x3 -> 2x2, нужен один этап 3x3 -> 2x2
для $p \times p$ : один этап $2p - 1 \times 2p - 1 \to p \times p$

то это упрощает код

Интересно, я в этом направлении не думал. А у вас есть код посмотреть? Я пытался делать мапу 0 -> 0, 1 -> 1, там немного упрощается база рекурсии, но не сильно.

wataru 18 июл в 13:38

Тут оно работает, потому что живые клетки в стандартных правилах “жизни” не могут двигаться быстрее, чем на T/2 клеток за T шагов,

Нет же. Берем длинную палку длинной L шириной 1. За один шаг она станет очень длинной O. За следующий шаг появятся 2 вертикальные полосы еще правее и еще левее. В итоге через L шагов родятся клетки отстоящие на L шагов вправо и влево от центра палки (и что-то еще по середине).

Скорость света - 1 клетка/шаг.

поэтому в корне всегда достаточно пустого периметра.

Да. Но только если каждый под-блок этого расширенного с периметром поля считать отдельно. Если бы скорость света действительно была 1/2 клеток/шаг, то не надо было бы и расширять. Вот в примере выше в поле уже по краям достаточно пустого места.

Кстати, если вот как вы там обобщаете на окрестность p x p, то там скорость света вообще может быть p/2 и, похоже, периметр надо будет делать еще больше.

Код я потом скину, еще не отдебажил.

lightln2 18 июл в 14:43

Берем длинную палку длинной L шириной 1

да, вы правы.

Кстати, если вот как вы там обобщаете на окрестность p x p, то там скорость света вообще может быть p/2 и, похоже, периметр надо будет делать еще больше.

вроде, не надо: для $p^{k+1} \times p^{k+1} \to p^k \times p^k$ за k шагов скорость света . Чтобы перейти $p^k \to p^{k+1}$ , у нас есть периметр шириной $(p^{k+1} - p^k) / 2$ клеток, то есть, мы можем сделать $\frac{ (p^{k+1} - p^k) / 2 } {(p-1)/2} = p^k$ шага, именно это и делается, если взять массив $(2p-1) \times (2p-1)$ , положить в центр узел $p^k \times p^k$ и сделать один этап эволюции.

wataru 18 июл в 14:46

вроде, не надо

Да, согласен.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий