Я реализую класс разреженной матрицы в формате сжатой строки. Это означает, что у меня есть фиксированное количество строк, и каждая строка состоит из нескольких элементов (это число может быть разным для разных строк, но не изменится после инициализации матрицы.
Подходит ли это для реализации через векторы векторов или это как-то фрагментирует память?
Как мне реализовать это распределение, чтобы у меня был один большой кусок памяти?
Спасибо, что поделились своей мудростью! Кортик
Общее правило с разреженными матрицами заключается в том, что вы выбираете структуру, которая лучше всего соответствует расположению ненулевых элементов в матрице; так что, может быть, вы могли бы написать немного больше о структуре матрицы, а также о том, какие (вроде) алгоритмы будут вызываться на ней.
О памяти - если эта матрица не слишком велика, лучше выделить ее как один большой кусок и сделать немного магии индекса; это может привести к лучшему использованию кэша. Если он большой, следует использовать фрагментированную версию, поскольку она лучше помещается в памяти.
Вы можете использовать существующие библиотеки, такие как разреженная матрица повышения (http://www.boost.org/doc/libs/1_43_0/libs/numeric/ublas/doc/matrix_sparse.htm)
Вы не получите «один большой кусок» с вектором векторов. Каждая строка будет непрерывным блоком, но данные каждой строки могут быть расположены в разных местах кучи.
Имейте в виду, что это может быть полезно, если вы собираетесь иметь дело с огромными матрицами. Чем больше матрица, тем меньше вероятность того, что вы сможете получить непрерывный фрагмент, чтобы уместить все это.
Я реализовал сжатый формат столбца с 3 std::vector<int> (2 для индексов строк и столбцов и один для значения). Зачем тебе std::vector<std::vector<int>>?
Вы уверены, что реализуете правильный формат? Описание формата сжатого столбца (и код для умножения матрицы на вектор) может можно найти здесь.
