Оптимизация «игры жизни» Конвея

Question

Чтобы экспериментировать, я (давно) реализовал Игру Жизни Конвея (и я знаю этот связанный вопрос!).

Моя реализация работала, сохраняя 2 массива логических значений, представляющих «последнее состояние» и «обновляемое состояние» (2 массива менялись на каждой итерации). Хотя это достаточно быстро, я часто задавался вопросом, как это оптимизировать.

Одна из идей, например, заключалась бы в предварительном вычислении на итерации N зон, которые могли бы быть модифицированы на итерации (N + 1) (чтобы ячейка не принадлежала такой зоне даже не будет рассматриваться для модификации на итерации (N + 1)). Я знаю, что это очень расплывчато, и я никогда не тратил время на детали ...

У вас есть идеи (или опыт!) О том, как оптимизировать (для скорости) итерации Game of Life?

Answer 1

Я собираюсь процитировать свой ответ на другой вопрос, потому что в главах, которые я упоминаю, есть несколько очень интересных и хорошо отлаженных решений. Некоторые детали реализации находятся в c и / или ассемблере, да, но по большей части алгоритмы могут работать на любом языке:

главы 17 и 18 из Графика Майкла Абраша Черная книга программиста является одним из самые интересные чтения у меня когда-либо имел. Это урок мышления нестандартно. Вся книга действительно здорово, но финал оптимизирован Решения для игры жизни невероятные биты программирования.

Answer 2

Существуют некоторые сверхбыстрые реализации, которые (из памяти) представляют ячейки из 8 или более смежных квадратов в качестве битовых комбинаций и используют их в качестве индекса в большом массиве предварительно рассчитанных значений, чтобы определить в одной машинной инструкции, является ли ячейка жив или мертв.

Проверьте здесь:

http://dotat.at/prog/life/life.html

Также XLife:

http://linux.maruhn.com/sec/xlife.html

Answer 3

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

Answer 4

то, что является наиболее эффективным алгоритмом, в основном зависит от исходного состояния.

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

По моему мнению, имеет смысл сначала проверить наличие полностью мертвых пространств, когда ваше начальное состояние напоминает «случайное, но с вероятностью жизни менее 5%».

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

поэтому, если у вас есть поле 10 000 * 10 000, вы сначала накапливаете состояния верхней левой четверти 5000 * 5000.

и если сумма состояний равна нулю в первом квартале, вы можете полностью проигнорировать этот первый квартал прямо сейчас и проверить в правом верхнем углу 5000 * 5000 на будущее.

если его сумма состояний> 0, вы теперь разделите второй квартал на 4 части снова - и повторите эту проверку на срок службы для каждого из этих подпространств.

теперь вы можете перейти к субкадрам 8 * 8 или 10 * 10 (не уверен, что здесь имеет наибольший смысл).

всякий раз, когда вы находите жизнь, вы отмечаете эти подпространства как "имеющие жизнь".

только пробелы, которые "имеют жизнь", должны быть разделены на меньшие подпространства - пустые могут быть пропущены.

Когда вы закончите присваивать атрибут «имеет жизнь» всем возможным подпространствам, вы получите список подпространств, который вы теперь просто расширяете на +1 для каждого направления - с пустыми ячейками - и выполняете обычные (или измененные) ) игра правил жизни им.

Вы можете подумать, что разделить 10 000 * 10 000 точек на подпространства 8 * 8 - это много задач, но накапливать значения их состояний на самом деле гораздо, гораздо меньше вычислительной работы, чем выполнение алгоритма GoL для каждой ячейки плюс их 8 соседей плюс сравнение числа и сохранение нового состояния для сетевой итерации где-то ...

но, как я сказал выше, для случайного состояния инициации с 30% населения это не имеет большого смысла, так как не будет много полностью мертвых 8 * 8 подпространств для поиска (оставьте в покое мертвые 256 * 256 подпространств)

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

-110

Answer 5

Сам алгоритм по своей сути распараллелен. Используя тот же метод двойной буферизации в неоптимизированном ядре CUDA, я получаю около 25 мс на поколение в мире с оболочкой 4096x4096.

Answer 6

Две идеи:

(1) Многие конфигурации в основном пустые. Сохраняйте связанный список (не обязательно по порядку, который бы занимал больше времени) живых ячеек, а во время обновления обновляйте только вокруг живых ячеек (это похоже на ваше смутное предложение, OysterD:)

(2) Сохраните дополнительный массив, в котором хранится количество живых клеток в каждом ряду из 3 позиций (слева-по центру-справа). Теперь, когда вы вычисляете новое мертвое / живое значение ячейки, вам нужно только 4 операции чтения (верхняя / нижняя строки и позиции на центральной стороне) и 4 операции записи (обновить 3 значения итоговых строк, подверженных воздействию, и мертвую / живое значение новой ячейки). Это небольшое улучшение по сравнению с 8 операциями чтения и 1 записи, если предположить, что запись выполняется не медленнее, чем чтение. Я предполагаю, что вы могли бы быть более умным с такими конфигурациями и достичь еще лучшего улучшения в этом направлении.

Answer 7

Как упоминалось в «Черной книге» Арбаша, один из самых простых и простых способов получить огромное ускорение - это сохранить список изменений.

Вместо того чтобы каждый раз повторять всю сетку ячеек, сохраняйте копию всех ячеек, которые вы меняете.

Это сузит работу, которую вы должны выполнять на каждой итерации.

Answer 8

Одна из самых коротких реализаций в Javascript:)

Демонстрация движка Game of Life в 126 байтах

/* The Game of Life function */
// @param s: current state of the grid
// @param d: size of the grid (d*d)
// @param n: placeholder
// @param k: placeholder
// @param m: placeholder
// @param i: placeholder
// @param j: placeholder
function(s, d, n, k, m, i, j){
  for(
    n = [],                           // Initialize next state
    m = [d + 1, d, d - 1, 1],         // Initialize the upper half of the neighbours indexes
    i = d * d;                        // For each cell
    i--;
    n[i] = k == 3 || s[i] && k == 2,  // Set next state (live if it has 3 neighbours or lives and has 2 neighbours)
    k = 0                             // Reset the count of living neighbours
  )
  for(j in m)                         // for each neighbour position
    k += s[i + m[j]] + s[i - m[j]]    // count the living neighbours
  return(n)                           // return the next state
}

Answer 9

Я реализовал это в C #:

Все ячейки имеют местоположение, число соседей, состояние и доступ к правилу.

1. Поместите все живые ячейки в массив B в массив A.
2. Сделайте так, чтобы все ячейки в массиве A добавили 1 к числу соседей их соседи.
3. Пусть все ячейки в массиве A поместят себя и своих соседей в массив B. B. 1010 *
4. Все ячейки в массиве B Обновляются в соответствии с правилом и их состоянием.
5. Все ячейки в массиве B устанавливают своих соседей на 0.

Плюсы:

1. Игнорирует ячейки, которые не нужно обновлять

Минусы:

1. 4 массива: 2d массив для сетки, массив для живых ячеек и массив для активных клеток.
2. Невозможно обработать правило B0.
3. Обрабатывает ячейки одну за другой.
4. Клетки не просто логические

Возможные улучшения:

1. Ячейки также имеют значение «Обновлено», они обновляются, только если они не имеют обновляется в текущем тике, устраняя необходимость в массиве B, как указано выше
2. Вместо массива B, являющегося таковым с живыми соседями, массив B может быть ячейки без, и те проверяют на правило B0.

Answer 10

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