std :: vector <std :: vector <type>> для разреженной структуры матрицы или что-то еще?

Question

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

Подходит ли это для реализации через векторы векторов или это как-то фрагментирует память?

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

Спасибо, что поделились своей мудростью! Dirk

Answer 1

Вы можете использовать существующие библиотеки, как, например, Boost разреженную матрицу (http://www.boost.org/doc/libs/1_43_0/libs/numeric/ublas/doc/matrix_sparse.htm)

Answer 2

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

Answer 3

Вы не получите «один большой кусок» с векторами векторов.Каждая строка будет смежным фрагментом, но данные каждой строки могут быть расположены в разных местах в куче.

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

Answer 4

Я реализовал сжатый формат столбца с 3 std::vector<int> (2 для индексов строк и столбцов и один для значения). Зачем тебе std::vector<std::vector<int>>?

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