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

Question

Я преподаю себе более продвинутую Java, оптимизируя программу Game of Life.

До сих пор я ускорил его, используя многопоточные и маркирующие части мира Dirty. Однако массив World в настоящее время представляет собой двумерный массив байтов, а создание мирового размера, намного превышающего 30000 * 30000, вызывает ошибку пространства кучи java. Какие еще существуют способы хранения очень большого 2D-массива булевых/битов?

Answer 1

Вы можете использовать один большой BitSet с 30 000 х 30000 бит.

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

См. Также SparseBitSet.

Answer 2

Рассмотрите алгоритм «Hashlife». Это реализует ваш 2D бит-массив как «квадратное дерево». Нелистные узлы указывают на 4 под-узла (Северо-Запад, Северо-Восток, Юго-Запад, Юго-Восток), которые имеют половину диапазона родительского узла. Это создает двумерный битовый массив и имеет очень умный «memoized» алгоритм для вычисления будущих поколений.

Вот прогулка, которая, к счастью для вас, демонстрируется в Java:

http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478