Comments 3
Вообще, стандартный 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) шагов.
Вроде как на этих картинках цветные квадраты отмечены:
Как у вас, надо будет всех внуков корня квадро-дерева выписать в квадрат 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.
Это сильно эффективнее вашего варианта со сторонами из степени 3.
Эффективность зависит только от количества разных узлов. Насколько я понимаю, ваши вычисления касаются случайной популяции, при которой количество узлов экспоненциально, и hashlife работает медленно. В реальности он хорошо работает на регулярных структурах, и там все зависит от того, как именно они регулярны. Если есть много структур с симметрией сдвига кратной степерям двойки, то стандартный hashlife будет лучше. Если кратной степеням тройки - то мой вариант.
Откуда вы вообще 3 взяли?
Я делал оба варианта hashlife для версии клеточного автомата (не “жизнь”, но не принципиально), в которой много структур, симметричных относительно сдвига на 3^k клеток, но не на 2^k. Моя версия действительно была быстрее (в пять раз), но что я не ожидал, что реализация будет проще, чем квадродерево. К тому же, мне идея эволюции квадрата 3x3 кажется более естесственной, чем 4x4 - собственно, я и хотел этим поделиться.
Была еще и другая конфигурация, в которой симметрия была фрактальной со сдвигом 2^k. Ожидаемо, там стандартный hashlife работал за логарифм, а мой вариант вырождался в линию.
У меня недостаточно данных, чтобы утверждать, какой из вариантов лучше на практике в среднем. Навскидку, вариант с квадродеревом требует меньше памяти, но вариант с 3x3-деревом легче написать и отладить.
Как у вас, надо будет всех внуков корня квадро-дерева выписать в квадрат 4x4
Я сделал аналогичный код для квадродерева, по сложности получается примерно таким же! Усложняется эволюция листа, но упрощается эволюция корня. На моем примере вариант с квадродеревом работает в три раза быстрее, но при этом количество обработанных узлов - в пять раз меньше (то есть, время обработки одного узла сильно хуже, по крайней мере, в данной реализации на питоне).
Но все равно мне вариант с 3x3 кажется интуитивно более понятным.
HashLife на питоне