Оптимизация памяти Game of Life

Question

Привет, я написал простую игру с кодом жизни, в которой используются 2 массива: один поддерживает текущее состояние, а другой поддерживает следующее состояние. Может кто-нибудь подсказать, как оптимизировать эту программу для потребления памяти. В идеале, я бы хотел, чтобы сложность его пространства была меньше, чем у RC.

Answer 1

Зависит от того, насколько скудно ваше игровое поле. Если ваше игровое поле плотное, то сложность пространства любого алгоритма хранения будет иметь тенденцию к RC. (В частности, RC / 2, поскольку после того, как вы получите больше активных ячеек, чем неактивных ячеек, вы можете просто хранить неактивные ячейки вместо этого, если действительно заботитесь об оптимальном использовании пространства.)

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

Answer 2

Я не слишком много знаю о GOL, но, учитывая, что есть много пустых «квадратов», вы смотрели на Разреженные матрицы ?

Answer 3

Поздний ответ, но все же.

Проверьте исходный код для golly: http://golly.sourceforge.net/

Но прежде чем сделать это, перейдите к: http://www.ibiblio.org/lifepatterns/lifeapplet.html
Ипосмотрите на код там.Это на Java, но это очень и очень быстро.

Эта цитата с сайта Алана Хензеля должна ответить на ваш вопрос:

Как вы сделали это так быстро?Хорошо, случайный наблюдатель может не заметить, что мой апплет невероятно быстр.Возможно, вы не нашли кнопку «Скорость деформации», или вы ее не использовали, или она вас не впечатлила.Вы можете перейти к следующему разделу.

Тем не менее, некоторые из вас спрашивали, как, черт возьми, вы сделали это так быстро ?!Я объясню любопытным или тем, кто думает о написании своей собственной сверхбыстрой программы для клеточных автоматов.

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

Для блобных вселенных, вероятно, следует рассмотреть возможность разделения вселенной на блоки, примерно размером с капли.Для жизни 4x4 до 8x8 кажутся разумными.Из соображений удобства я выбрал верхнюю границу 8x8: в байте бывает 8 бит.Я решительно считал 4х4, но это не сработало ...

Вы должны поместить блоки в какой-то список, чтобы тратить ноль времени на пустые части вселенной.

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

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

Примечание. Программы CA обычно состоят из 2 основных циклов (плюс цикл отображения), поскольку правила CA работают с ячейками параллельно, а микропроцессор концептуально последовательный,Это означает, что фактически должно быть две копии вселенной, чтобы никакая важная информация не уничтожалась в процессе создания следующего поколения.Часто эти 2 копии не являются симметричными.Это была большая борьба для меня, так как почти каждый раз, когда я брал что-то из одного цикла, чтобы сделать это быстрее, мне приходилось добавлять что-то еще в другой цикл!Это почти каждый раз;исключения из этого правила приводят к лучшей оптимизации.В частности, есть хорошие компромиссы, которые следует учитывать при битовых манипуляциях: сдвиг, маскирование, рекомбинация для формирования адреса в таблице поиска ...

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

Осцилляторы периода-2 также могут быть не очень сложными для обнаружения и удаления из времени обработки.Это может быть полезным в жизни, потому что мигалка является наиболее распространенным видом случайного мусора.Осцилляторы более высокого периода встречаются гораздо реже.Также возможно, что планеры могут быть обнаружены и смоделированы.Вы получите убывающую отдачу от такого рода оптимизации, если не доведите ее до крайности (см. HashLife).

Кроме того, блок ячеек, который является полностью пустым, может не стоить отменять и удалять из хеш-таблицы на некоторое время. Это занимает некоторое время обработки, которое может быть значительным в случае многократного перемещения осциллятора в его пространство и из него. Только тогда, когда памяти становится мало, самые старые блоки из "морга" могут быть переработаны.

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

Тогда прочитайте этот кусок исходного кода: http://www.ibiblio.org/lifepatterns/src.41d/LifeCell.java
Он содержит структуры данных, которые содержат вселенную Алана.

Забудьте о хэш-жизни, она настолько сложна, что заставит вашу голову кружиться.

Answer 4

Я рекомендую разреженные матрицы, так как рекомендуются nonnb и Amber. Вы также можете изучить кодирование, если у вас есть мощность процессора для записи или вы хотите сериализовать на диск. Сжатие на основе RLE или токена может куда-то вас привести.

Answer 5

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

state curr, next;
[...]
for (;;) {
    next = advance(curr);
    curr = copy(next);
}

К этому:

state s1, s2;
state *curr, *next;
[...]
for (;;) {
    *next = advance(*curr);
    /* swap pointers */
    state *tmp = curr;
    curr = next;
    next = tmp;
}