Является ли хэширование хорошим способом для сравнения двух 32x64 двухмерных массивов?

Question

Я пытаюсь реализовать игру жизни Конвея на встроенном устройстве. У меня есть только 1 КБ оперативной памяти, и всего 2048 ячеек, что равняется 512 байтам. Я собираюсь вычислять ячейки следующего поколения 8x8 за раз, чтобы мне не приходилось хранить два поколения в оперативной памяти в какой-либо одной точке.

Однако я также хотел бы обнаружить, когда GoL застрял в цикле / статическом состоянии. Когда я создавал макет на ПК, я просто сохранял последние сто тысячного поколения и сравнивал с ним текущее поколение. Я не могу сделать это с 1 КБ ОЗУ, и я думаю о том, чтобы просто вычислить хэш последнего поколения x и сравнить его с хэшом текущего поколения.

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

Спасибо

Джо

РЕДАКТИРОВАТЬ: Просто подумав, я мог бы фактически посчитать количество совпадений, и если он достигнет определенного порога, то предположить, что он находится в цикле, что не очень хорошо будет работать для шаблонов, которые повторяются каждые тысячи поколений или около того.

Answer 1

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

Answer 2

Я решил просто получить устройство с большим объемом оперативной памяти, но я заметил одну вещь: если шаблон существует, то один и тот же шаблон будет сопоставляться каждые x поколений, в то время как случайное столкновение хешей не будет , Так что, если у нас есть следующие поколения:

123*
231
312
123*
231
312
123*

123 подбирается каждые 3 поколения. Этого не произойдет при столкновении хэшей.

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

Спасибо

Джо

Answer 3

Хеширование - это хорошо, когда можно сказать, когда вещи не равны. Если хэши равны, то вам все равно нужно (ну должно ) провести индивидуальное сравнение.