Как эффективно хранить и манипулировать разреженными двоичными матрицами в Octave?

Я пытаюсь манипулировать разреженными двоичными матрицами в GNU Octave, и он использует намного больше памяти, чем я ожидал, и соответствующие функции разреженных матриц ведут себя не так, как я хочу. Я вижу этот вопрос о том, что в MATLAB хранилище разреженных матриц выше ожидаемого, что говорит о том, что эта матрица должна занимать еще больше памяти, но помогло объяснить (только) часть этой ситуации.

Для разреженной двоичной матрицы я не могу найти способ заставить Octave НЕ ХРАНИТЬ массив значений (они всегда неявно 1, так что не нужно хранить). Можно ли это сделать? Кажется, что Octave всегда потребляет память для массива значений.

Урезанный пример, демонстрирующий ситуацию: создайте случайную разреженную матрицу, превратите ее в "двоичный":

mys=spones(sprandn(1024,1024,.03)); nnz(mys), whos mys

Показывает ситуацию. Используемый размер соответствует механизму хранения, описанному в вышеупомянутом ответе SO и расширенном ниже, если spones() создает массив класса хранения double и если все индексы являются 32-битными (т.е.

 TotalStorageSize - rowIndices - columnIndices == NumNonZero * sizeof (double)
- излишне хранить эти значения (все 1 как double s) составляет более половины всей памяти, используемой этим 3%-ым разреженным объектом.

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

Как создать эффективно хранимую двоичную матрицу ("без / неявных значений") в Octave?

Дополнительный фон в формате хранения следует...

В документах Octave говорится, что формат хранения разреженных матриц использует формат Compressed Sparse Column (CSC). Похоже, это подразумевает сохранение следующих массивов (расширение вышеупомянутого ответа SO, с каноническим форматом Yale labels и твики для основного порядка столбцов):

  • значения (A), количество ненулевых (NNZ) записей размера класса хранения;
  • номера строк (IA), NNZ записи размера индекса (надеюсь, int64 но возможно int32);
  • начало каждого столбца (JA), количество столбцов плюс 1 записи размера индекса)

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

Источник

1 ответ

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

Чтобы получить двоичное значение из числового значения и уменьшить использование памяти в этом случае, используйте "логическое" хранилище, созданное logical(X), Например, здание сверху,

logicalmys = logical(mys);

создает sparse bool matrix, что занимает меньше памяти (1 байт logical а не 8 байт double для массива значений).

Добавление дополнительной информации в whos использование информации whos_line_format помогает осветить ситуацию: Строка по умолчанию включает 5 из 7 свойств ( подробнее см. в документации). Я использую строку формата

whos_line_format(" %a:4; %ln:6; %cs:16:6:1; %rb:12; %lc:8; %e:10; %t:20;\n")

добавить отображение "элементов" и "типа" (отличного от "класса").

С этим, whos mys logicalmys показывает что-то вроде

 Attr Name            Size      Bytes Class      Elements                 Type
 ==== ====            ====      ===== =====      ========                 ==== 
      mys          1024x1024   391100 double        32250        sparse matrix
      logicalmys   1024x1024   165350 logical       32250   sparse bool matrix

Так что это показывает различие между sparse matrix а также sparse bool matrix, Тем не менее, общая память потребляется logicalmys согласуется с фактическим хранением массива логических значений NNZ (1 байт) - то есть:

  • totalMemory минус rowIndices минус columnOffsets оставляет NNZ байтов слева;

в цифрах,

  • 165350 - 32250*4 - 1025*4 == 32250,

Таким образом, мы все еще храним 32250 элементов, все из которых 1, Далее, если вы установите один из 1-элементов до нуля, это уменьшает заявленное хранилище! Для хорошего времени попробуйте: выберите ненулевой элемент, например, (42,1)затем обнулите его: logicalmys(42,1) = 0; затем whos Это!

Я надеюсь, что это правильно, и это проясняет некоторые вещи для тех, кто может быть заинтересован. Комментарии, исправления или актуальные ответы приветствуются!

Источник
Другие вопросы по тегам