Как эффективно хранить матрицу с сильно избыточными значениями

Ответ 1

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

Ответ 2

Теперь для моего предпочтительного метода.

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

В этом методе мы поддерживаем структуру столбцов строки *.

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

Теперь у нас есть список сжатых строк.

Мы используем метод энтропийного кодирования (например, Shannon-Fano, Huffman или арифметическое кодирование), но мы не сжимаем данные в строках с помощью этого, мы используем его для сжатия набора строк. Мы используем его для кодирования относительной частоты строк. То есть мы обрабатываем строку так же, как стандартная энтропийная кодировка будет обрабатывать символ/байт.

В этом примере RLE сжимает строку a, а Хаффман сжимает целые строки .

Так, например, учитывая следующую матрицу (с префиксом номера строк, Хаффман используется для удобства объяснения)

0 | 8 8 8 8 8 8 8 8 8 8 8 8 8 |
1 | 8 4 8 8 1 1 1 1 1 8 8 8 8 |
2 | 8 4 8 8 1 1 1 1 1 8 8 8 8 |
3 | 8 4 8 8 1 1 1 1 1 8 8 8 8 |
4 | 8 4 8 8 1 1 1 1 1 8 8 8 8 |
5 | 8 4 8 8 1 1 1 1 1 8 8 8 8 |
6 | 8 8 8 8 8 8 8 8 8 8 8 8 8 |
7 | 8 8 3 3 3 3 3 3 3 3 3 3 3 |

Заданная длина пробега

0 | 8{13}                    |
1 | 8{1} 4{1} 8{2} 1{5} 8{4} |
2 | 8{1} 4{1} 8{2} 1{5} 8{4} |
3 | 8{1} 4{1} 8{2} 1{5} 8{4} |
4 | 8{1} 4{1} 8{2} 1{5} 8{4} |
5 | 8{1} 4{1} 8{2} 1{5} 8{4} |
6 | 8{13}                    |
7 | 8{2} 3{11}               |

Итак, 0 и 6 появляются дважды, а 1 - 5 появляются 5 раз. 7 только один раз.

Таблица частот

A: 5 (1-5) | 8{1} 4{1} 8{2} 1{5} 8{4} |
B: 2 (0,6) | 8{13}                    |
C: 1    7  | 8{2} 3{11}               |

Дерево Хаффмана

    0|1
   /   \
  A    0|1
      /   \
     B     C

Итак, в этом случае для кодирования строк 1 - 5 и 2 бита требуется один бит (для каждой строки) для кодирования строк 0, 6 и 7.

(Если пробежки длиннее, чем несколько байт, то частота freq на хеше, которую вы создаете, как вы делаете RLE).

Вы храните дерево Хаффмана, уникальные строки и поток битов строки.

Хорошая вещь о Хаффмане заключается в том, что у него есть уникальное свойство префикса, поэтому вы всегда знаете, когда закончите. Таким образом, с учетом битовой строки 10000001011 вы можете перестроить матрицу A из сохраненных уникальных строк и дерева. Кодированный поток бит сообщает вам порядок, в котором появляются строки.

Возможно, вы захотите изучить адаптивную кодировку Хаффмана или ее арифметическую копию.

Увидев, что строки в с одинаковыми элементами столбца умножаются на один и тот же результат в AB над вектором B, вы можете кэшировать результат и использовать его вместо вычисления его снова (всегда полезно избегать умножения 100M * 100M, если можете).

Ссылки на дополнительную информацию:

Арифметическое кодирование + Статистическое моделирование = Сжатие данных

Приоритетные очереди и STL

Арифметическое кодирование

кодировка Хаффмана

Сравнение

несжатого

    0   1   2   3   4   5   6   7
  =================================
0 | 3   3   3   3   3   3   3   3 |
  |-------+               +-------|
1 | 4   4 | 3   3   3   3 | 4   4 |
  |       +-----------+---+       |
2 | 4   4 | 5   5   5 | 1 | 4   4 |
  |       |           |   |       |
3 | 4   4 | 5   5   5 | 1 | 4   4 |
  |---+---|           |   |       |
4 | 5 | 0 | 5   5   5 | 1 | 4   4 |
  |   |   +---+-------+---+-------|
5 | 5 | 0   0 | 2   2   2   2   2 |
  |   |       |                   |
6 | 5 | 0   0 | 2   2   2   2   2 |
  |   |       +-------------------|
7 | 5 | 0   0   0   0   0   0   0 |
  =================================

= 64 байта

квадрадерево

    0   1   2   3   4   5   6   7
  =================================
0 | 3 | 3 |       |       | 3 | 3 |
  |---+---|   3   |   3   |---+---|
1 | 4 | 4 |       |       | 4 | 4 |
  |-------+-------|-------+-------|
2 |       |       | 5 | 1 |       |
  |   4   |   5   |---+---|   4   |
3 |       |       | 5 | 1 |       |
  |---------------+---------------|
4 | 5 | 0 | 5 | 5 | 5 | 1 | 4 | 4 |
  |---+---|---+---|---+---|---+---|
5 | 5 | 0 | 0 | 2 | 2 | 2 | 2 | 2 |
  |-------+-------|-------+-------|
6 | 5 | 0 | 0 | 2 | 2 | 2 | 2 | 2 |
  |---+---+---+---|---+---+---+---|
7 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
  =================================

0 +- 0 +- 0 -> 3
  |    +- 1 -> 3
  |    +- 2 -> 4
  |    +- 3 -> 4
  +- 1      -> 3
  +- 2      -> 4
  +- 3      -> 5
1 +- 0      -> 3
  +- 1 +- 0 -> 3
  |    +- 1 -> 3
  |    +- 2 -> 4
  |    +- 3 -> 4
  +- 2 +- 0 -> 5
  |    +- 1 -> 1
  |    +- 2 -> 5
  |    +- 3 -> 1
  +- 3      -> 4
2 +- 0 +- 0 -> 5
  |    +- 1 -> 0
  |    +- 2 -> 5
  |    +- 3 -> 0
  +- 1 +- 0 -> 5
  |    +- 1 -> 5
  |    +- 2 -> 0
  |    +- 3 -> 2
  +- 2 +- 0 -> 5
  |    +- 1 -> 0
  |    +- 2 -> 5
  |    +- 3 -> 0
  +- 3 +- 0 -> 0
       +- 1 -> 2
       +- 2 -> 0
       +- 3 -> 0
3 +- 0 +- 0 -> 5
  |    +- 1 -> 1
  |    +- 2 -> 2
  |    +- 3 -> 2
  +- 1 +- 0 -> 4
  |    +- 1 -> 4
  |    +- 2 -> 2
  |    +- 3 -> 2
  +- 2 +- 0 -> 2
  |    +- 1 -> 2
  |    +- 2 -> 0
  |    +- 3 -> 0
  +- 3 +- 0 -> 2
       +- 1 -> 2
       +- 2 -> 0
       +- 3 -> 0

((1*4) + 3) + ((2*4) + 2) + (4 * 8) = 49 leaf nodes 
49 * (2 + 1) = 147 (2 * 8 bit indexer, 1 byte data)
+ 14 inner nodes -> 2 * 14 bytes (2 * 8 bit indexers)
= 175 Bytes

Регион Хеш

    0   1   2   3   4   5   6   7
  =================================
0 | 3   3   3   3   3   3   3   3 |
  |-------+---------------+-------|
1 | 4   4 | 3   3   3   3 | 4   4 |
  |       +-----------+---+       |
2 | 4   4 | 5   5   5 | 1 | 4   4 |
  |       |           |   |       |
3 | 4   4 | 5   5   5 | 1 | 4   4 |
  |---+---|           |   |       |
4 | 5 | 0 | 5   5   5 | 1 | 4   4 |
  |   + - +---+-------+---+-------|
5 | 5 | 0   0 | 2   2   2   2   2 |
  |   |       |                   |
6 | 5 | 0   0 | 2   2   2   2   2 |
  |   +-------+-------------------|
7 | 5 | 0   0   0   0   0   0   0 |
  =================================

0: (4,1; 4,1), (5,1; 6,2), (7,1; 7,7)         | 3
1: (2,5; 4,5)                                 | 1
2: (5,3; 6,7)                                 | 1
3: (0,0; 0,7), (1,2; 1,5)                     | 2
4: (1,0; 3,1), (1,6; 4,7)                     | 2
5: (2,2; 4,4), (4,0; 7,0)                     | 2

Регионы: (3 + 1 + 1 + 2 + 2 + 2) * 5   = 55 байтов {4 байта прямоугольника, 1 байт данных)

{tаблица поиска - это отсортированный массив, поэтому для него не требуется дополнительное хранилище}.

закодированный Huffman RLE

0   | 3 {8}                                 | 1
1   | 4 {2} | 3 {4} | 4 {2}                 | 2
2,3 | 4 {2} | 5 {3} | 1 {1} | 4 {2}         | 4
4   | 5 {1} | 0 {1} | 5 {3} | 1 {1} | 4 {2} | 5
5,6 | 5 {1} | 0 {2} | 2 {5}                 | 3
7   | 5 {1} | 0 {7}                         | 2


RLE Data:    (1 + 3+ 4 + 5 + 3 + 2) * 2 = 36
Bit Stream:   20 bits packed into 3 bytes = 3
Huffman Tree: 10 nodes * 3 = 30
= 69 Bytes

Один гигантский поток RLE

3{8};4{2};3{4};4{4};5{3};1{1};4{4};5{3};1{1};4{2};5{1};0{1};
5{3};1{1};4{2};5{1};0{2};2{5};5{1};0{2};2{5};5{1};0{7}

= 2 * 23 = 46 Bytes

Один гигантский поток RLE, закодированный с общим сгибанием префикса

3{8};
4{2};3{4};
4{4};5{3};1{1};
4{4};5{3};
1{1};4{2};5{1};0{1};5{3};
1{1};4{2};5{1};0{2};2{5};
5{1};0{2};2{5};
5{1};0{7}

0 + 0 -> 3{8};4{2};3{4};
  + 1 -> 4{4};5{3};1{1};

1 + 0 -> 4{2};5{1} + 0 -> 0{1};5{3};1{1};
  |                + 1 -> 0{2}
  |
  + 1 -> 2{5};5{1} + 0 -> 0{2};
                   + 1 -> 0{7}

3{8};4{2};3{4}           | 00
4{4};5{3};1{1}           | 01
4{4};5{3};1{1}           | 01
4{2};5{1};0{1};5{3};1{1} | 100
4{2};5{1};0{2}           | 101
2{5};5{1};0{2}           | 110
2{5};5{1};0{7}           | 111

Bit stream: 000101100101110111
RLE Data:  16 * 2 = 32
Tree:   : 5 * 2 = 10 
Bit stream: 18 bits in 3 bytes = 3
= 45 bytes

Ответ 3

Если ваши данные действительно регулярны, вам может быть полезно сохранить их в структурированном формате; например ваша примерная матрица может быть сохранена в виде следующего списка инструкций "fill-rectangle":

(0,0)-(13,7) = 8
(4,1)-(8,5)  = 1

(Затем, чтобы посмотреть значение конкретной ячейки, вы перебираете назад по списку, пока не найдете прямоугольник, содержащий эту ячейку)

Ответ 4

Как предложила Ира Бакстер, вы можете сохранить матрицу в виде квадранта с листами, содержащими одиночные значения.

Самый простой способ сделать это - для каждого node квадранта охватить область 2 ^ n x 2 ^ n, и каждый не-лист node указывает на его 4 детей размером 2 ^ (n-1) x 2 ^ (n-1).

Вы можете получить немного лучшее сжатие с адаптивной квадрантой, которая допускает нерегулярное подразделение. Затем каждый не-лист node сохраняет точку выреза (B, G) и указывает на ее 4 детей. Например, если некоторый нелистный node покрывает область из (A, F) в верхнем левом углу (C, H) в нижнем правом углу, затем его 4 ребенка охватывают районы (A, F) - (B-1, G-1) (A, G) - (B-1, H) (B, F) - (C, G-1) (B, G) - (C, H).

Вы попытались бы выбрать точку отсечения (B, G) для каждого нелистового node, чтобы она выровнялась с некоторым вещественным делением в ваших данных.

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

С простыми степенями двух квадрантов вы получите как минимум 21 узел: 5 нелистовых узлов, 4 листовых узла из девяти и 12 листовых узлов нулей. (Вы получите еще больше узлов, если центрированный малый квадрат не является точно некоторым расстоянием от двух сторон от левого и верхнего краев, а не может быть какой-то точной степенью двух).

С адаптивной квадрантой, если вы достаточно умны, чтобы выбрать точку отсечения для корня node в верхнем левом углу этого квадрата, то для корневого нижнего правого ребенка вы выбираете точку пересечения в в правом нижнем углу квадрата вы можете представить всю матрицу в 9 узлах: 2 нелистных узла, 1 лист node для девяток и 6 листовых узлов для нулей.

Ответ 5

Знаете ли вы о.... деревьях интервалов?

Интервальные деревья - это способ эффективного хранения интервалов, а затем их запрос. Обобщение - это Дерево диапазонов, которое может быть адаптировано к любому измерению.

Здесь вы можете эффективно описать свои прямоугольники и прикрепить к ним значение. Конечно, прямоугольники могут перекрываться, что сделает его эффективным.

0,0-n,n --> 8
4,4-7,7 --> 1
8,8-8,n --> 3

Затем при запросе значения в одном конкретном месте вам возвращается список из нескольких прямоугольников и нужно определить самую внутреннюю: это значение в этом месте.

Ответ 6

Самый простой способ - использовать кодировку во время выполнения в одном измерении и не беспокоиться о другом измерении.

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

Еще один простой подход - попробовать прямоугольную заливку заливки в верхнем правом пикселе и увеличить ее до самого большого прямоугольника, который вы можете (в ширину); затем отметьте все эти пиксели как "сделанные" и возьмите верхний правый самый оставшийся пиксель, повторите до конца. (Вероятно, вы захотите сохранить эти прямоугольники в виде BSP или quad-tree.)

Высокоэффективный метод - не оптимальный, но, вероятно, достаточно хороший, - это использование дерева разбиения двоичного пространства, где "пространство" измеряется не пространственно, а количеством изменений. Вы рекурсивно отрезаете так, чтобы у вас было равное количество изменений слева и справа (или сверху и снизу - предположительно, вы хотели бы сохранить вещи квадратными), и, поскольку ваши размеры уменьшились, так что вы сократили бы столько же как можно скорее. В конце концов вы в конечном итоге срезаете два прямоугольника друг от друга, каждый из которых имеет одинаковое число; затем остановитесь. (Кодирование по RLE в x и y быстро скажет вам, где находятся точки изменения.)

Ответ 7

Ваше описание пространства O (1) для матрицы размером 100M x 100M сбивает с толку. Когда у вас есть конечная матрица, ваш размер является константой (если только программа, которая генерирует матрицу, не изменяет ее). Таким образом, объем пространства, необходимый для хранения, также является постоянным, даже если вы умножаете его на скаляр. Определенно, время для чтения и записи матрицы не будет O (1).

Редкая матрица - это то, о чем я мог думать, чтобы уменьшить объем пространства, необходимого для хранения такой матрицы. Вы можете записать эту разреженную матрицу в файл и сохранить ее как tar.gz, которая будет дополнительно сжимать данные.

У меня есть вопрос, что означает M в 100M? Это означает Megabyte/million? Если да, размер этой матрицы будет 100 x 10 ^ 6 x 100 x 10 ^ 6 байтов = 10 ^ 16/10 ^ 6 MB = 10 ^ 10/10 ^ 6 TB = 10 ^ 4 TB!!! Какую машину вы используете?

Ответ 8

Я не уверен, почему этот вопрос был задан Community Wiki, но так оно и есть.

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

Пусть M - ваша матрица, v - вектор, который вы хотите умножить на M, и пусть A - специальная матрица

A = [1 -1  0  0  0]
    [0  1 -1  0  0]
    [0  0  1 -1  0]
    [0  0  0  1 -1]
    [0  0  0  0  1]

Вам также понадобится обратная матрица для A, которую я назову B:

B = [1 1 1 1 1]
    [0 1 1 1 1]
    [0 0 1 1 1]
    [0 0 0 1 1]
    [0 0 0 0 1]

Умножение вектора v на A выполняется быстро и просто: вы просто принимаете разницу в последовательных парах элементов v. Умножение вектора v на B также быстро и просто: записи Bv являются частичными суммами элементов v. Затем вы хотите использовать уравнение

Mv = B AMA B v

Матрица AMA разрежена: в середине каждая запись представляет собой переменную сумму из 4 записей M, которые составляют квадрат 2 x 2. Вы должны быть в углу одного из прямоугольников в M, чтобы эта переменная сумма была ненулевой. Поскольку AMA разрежен, вы можете хранить ненулевые записи в ассоциативном массиве и использовать разреженное умножение матрицы, чтобы применить его к вектору.

Ответ 9

У меня нет конкретного ответа на матрицу, которую вы показали. В анализе конечных элементов (FEA) у вас есть матрицы с избыточными данными. При реализации пакета FEA в моем проекте под градиентом я использовал метод хранения skyline.

Некоторые ссылки:

Страница Intel для разреженного хранения матриц

Ссылка Википедии

Ответ 10

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

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

Я бы начал с кодирования длины строки, посмотрим, как это работает в первую очередь. Когда это работает, попробуйте добавить некоторые трюки, такие как ссылки на разделы предыдущей строки. Таким образом, строка может быть закодирована как: 126 нулей, 8 единиц, 1000 записей, скопированных непосредственно из строки выше, 32 нулей. Кажется, что это может быть очень эффективно с вашим примером.

Ответ 11

Многие из вышеперечисленных решений в порядке.

Если вы работаете с файлом, рассмотрите файловую ориентацию инструменты сжатия, такие как сжатие, bzip, zip, bzip2 и друзья. Они работают очень хорошо, особенно если данные содержат избыточные Символы ASCII. Использование внешнего инструмента сжатия устраняет проблемы и проблемы внутри вашего кода и сжимать как двоичные, так и ASCII-данные.

В вашем примере вы показываете один номер символа. Числа 0-9 могут быть представлены меньшим четырьмя битами кодирование. Вы можете использовать дополнительные биты в байт как счет. Четыре бита дают вам дополнительные коды для бежать к дополнительным... Но есть осторожность, которая достигает назад к старым ошибкам Y2K, где использовались два символа в течение года. Байт-кодировка с определенного значения дала бы 255 лет и те же два байта охватывали все написанные историю, а затем некоторые.

Ответ 12

Вы можете взглянуть на GIF format и его алгоритм сжатия. Просто подумайте о своей матрице в виде растрового изображения...

Ответ 13

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

• Матрица сильно избыточна, не обязательно разрежена.
• Мы хотим минимизировать хранение (на диске и ОЗУ).
• Мы хотим иметь возможность умножить A [m * n] на вектор B [n * 1], чтобы добраться до AB [m * 1] без предварительного декомпрессии (по крайней мере, не более, чем требуется для выполнения вычислений).
• Нам не нужен случайный доступ к любой записи A [i * j] - все операции над матрицей.
• Умножение выполняется онлайн (по мере необходимости) и поэтому должно быть максимально эффективным.
• Матрица статическая.

Можно попробовать всевозможные умные схемы для обнаружения прямоугольников или собственного сходства и т.д., но это приведет к ухудшению производительности при выполнении умножения. Я предлагаю 2 относительно простых решения.

Мне придется немного поработать, поэтому, пожалуйста, будьте терпеливы со мной.

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

Подумайте о матрице, сплющенной в массив (это действительно так, как это все равно сохраняется в памяти). Например.

A
| w0 w1 w2 |
| x0 x1 x2 |
| y0 y1 y2 |
| z0 z1 z2 |

становится

A’
| w0 w1 w2 x0 x1 x2 y0 y1 y2 z0 z1 z2 |

Мы можем использовать тот факт, что любой индекс [i,j] = i * j.

Итак, когда мы выполняем умножение, мы перебираем матрицу А матрицы с k = [0..m * n-1] и индексируем в вектор B, используя (k mod n) и в вектор AB с ( k div n). "div" является целым делением.

Итак, например, A[10] = z1. 10 mod 3 = 1 и 10 div 3 = 3 A[3,1] = z1.

Теперь, к сжатию. Мы выполняем обычный запуск цикла Run Length Encoding (RLE), но против A, а не A. С плоским массивом будут более длинные последовательности повторения, следовательно, лучшее сжатие. Затем, после кодирования прогонов, мы выполняем другой процесс, в котором извлекаем общие подстроки. Мы можем либо выполнить сжатие слова, либо обрабатывать данные запуска в какой-то форме оптимизированного по пространству графа, например дерева дерева суффиксов или устройства собственного создания, которое объединяет вершины и хвосты. Граф должен иметь представление всех уникальных строк в данных. Вы можете выбрать любое количество методов, чтобы разбить поток на строки: сопоставить префиксы, длину или что-то еще (что лучше всего подходит для вашего графика), но сделать это на границе выполнения, а не в байтах, или ваше декодирование будет усложняться. График становится конечным автоматом при распаковке потока.

Я собираюсь использовать поток бит и Patricia trie в качестве примера, потому что он прост, но вы можете использовать что-то еще (подробнее биты на одно изменение состояния лучше слияния и т.д. Ищите документы Stefan Nilsson).

Чтобы сжать данные запуска, мы создаем хеш-таблицу против графика. Таблица отображает строку в последовательность бит. Вы можете сделать это, пройдя по графику и закодируя каждую левую ветвь как 0 и правую ветвь как 1 (произвольный выбор).

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

Если вы отмените процесс, используя поток битов, чтобы перейти к графику, пока не достигнете листа/терминала node, вы получите исходные данные запуска, которые вы можете декодировать "на лету", чтобы создать поток целых чисел, который вы умножьте на вектор B, чтобы получить AB. Каждый раз, когда вы заканчиваете работу, вы читаете следующий бит и просматриваете соответствующую строку. Мы не заботимся о том, чтобы у нас не было произвольного доступа к A, потому что нам нужно только это в B (B, который может быть ограниченным интервалом/интервалом, но не обязательно).

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

Я объясню другой метод в отдельном ответе, поскольку он слишком длинный, как есть, но этот метод может фактически ускорить вычисление из-за того, что повторяющиеся строки в матрице A умножаются на тот же результат в AB.

Ответ 14

ok вам нужен алгоритм сжатия try RLE (Run Length Encoding), его работа очень хороша, когда данные является сильно избыточный.