Облегченная матрица логических значений

Question

Мне нужно реализовать очень большую матрицу, скажем, NxN в стандарте C. Матрица должна хранить таблицу истинности, то есть

matrix[i][j] = [true|false]

Я знаю, что могу просто использовать матрицу int, илиboolean type при использовании C99, но искал наиболее легкое решение с точки зрения памяти.

Answer 1

Наиболее легким решением с точки зрения памяти является сохранение восьми логических значений в символе:

unsigned char getBit(char byte, unsigned short bit){
    assert(bit < 8);
    return byte&(1<<bit);
}

Затем вы можете сохранить матрицу N x 8M, сохранив байты в каждой строке.Если многие из этих байтов пусты, вам следует использовать формат разреженной матрицы, например сжатую строку резервных копий.

Answer 2

Возможно, вы захотите использовать реализацию хэша или список списков, если матрица особенно разрежена.

Также, если i или j меньше наибольшего целого числа, которое может хранить ваша система, вы можете упаковать логический набор битов в одно целое число, каждый бит которого соответствует одному индексу. Затем вы можете получить к нему доступ или изменить его, используя побитовые операции.

Answer 3

если есть более эффективное решение

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

Сжатие будет работать только на неслучайных данных; И произвольный доступ к сжатым данным может быть медленным.

Самый простой способ - это RLE (сжимать каждую строку независимо). Немного сложнее хранить данные в разреженной матрице (только если у вас намного больше 0 значений, чем 1; этот метод может сжимать многомерные данные).

Здесь используется гораздо более сложное сжатие: http://crd -legacy.lbl.gov / ~ kewu / fastbit / index.html Оно называется "Гибридная схема сжатия с выравниванием по словам"

Answer 4

Разве не для этого используется std :: bitset?