Оптимизация Конвей "Игра жизни"

Ответ 1

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

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

Ответ 2

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

Отъезд здесь:

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

Также XLife:

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

Ответ 3

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

Ответ 4

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

Ответ 5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-110

Ответ 6

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

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

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

Ответ 7

Две идеи:

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

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

Ответ 8

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

Ответ 9

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

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

Ответ 10

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

Ответ 11

Я реализовал это в С#: Все ячейки имеют местоположение, счетчик соседей, состояние и доступ к правилу. 1. Поместите все живые клетки в массив B в массив A. 2. У всех ячеек в массиве А добавить 1 к соседнему счету их  соседи. 3. Пусть все ячейки в массиве A поставят себя и своих соседей в массив B. 4. Все ячейки в массиве B Update в соответствии с правилом и их состоянием. 5. Все ячейки в массиве B задают своим соседям 0.

Плюсы: 1. Игнорирует ячейки, которые не нуждаются в обновлении.

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

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

Ответ 12

Одна из самых коротких реализаций в 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
}