Как реализовать битовую матрицу оптимально по памяти?

Question

[Александр Лях]

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

Answer 1

[Wataru]

Максимально компактно - хранить одномерную матрицу в битах целочисленного массива - по 8 бит на байт.

Для матрицы NxM бит (i,j) будет лежать в (i*N+j)/8 ячейке массива. Номер бита - надо взять остаток от деления на 8.

Можно получить любой бит и можно что угодно делать с матрицей.

Answer 2

[rPman]

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

способ хранения, отличным от просто массива байт, фактически определяется индексами, которые будешь строить для ускорения и хранения сжатых данных

например можно хранить вектор в виде трех списков key-value словарей, один - список байт со смешанными значениями бит, список с только нули либо список с только единицы (достаточно хранить только один из этих двух, отсутствие значений в первом и втором списках покажут что элемент в третьем)

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