Низкая производительность разреженной матрицы при использовании std :: vector
Я пытаюсь реализовать функциональность функции MATLAB sparse.
Вставьте значение в разреженную матрицу по определенному индексу так, чтобы:
Если значение с таким же индексом уже присутствует в матрице, то добавляются новые и старые значения.
В противном случае новое значение добавляется в матрицу.
Функция addNode работает правильно, но проблема в том, что это очень медленно. Я вызываю эту функцию в цикле около 100000 раз, и запуск программы занимает более 3 минут. В то время как MATLAB выполняет эту задачу в считанные секунды. Есть ли способ оптимизировать код или использовать алгоритмы STL вместо моей собственной функции для достижения того, что я хочу?
struct SparseMatNode
{
int x;
int y;
float value;
};
std::vector<SparseMatNode> SparseMatrix;
void addNode(int x, int y, float val)
{
SparseMatNode n;
n.x = x;
n.y = y;
n.value = val;
bool alreadyPresent = false;
int i = 0;
for(i=0; i<SparseMatrix.size(); i++)
{
if((SparseMatrix[i].x == x) && (SparseMatrix[i].y == y))
{
alreadyPresent = true;
break;
}
}
if(alreadyPresent)
{
SparseMatrix[i].value += val;
if(SparseMatrix[i].value == 0.0f)
SparseMatrix.erase(SparseMatrix.begin + i);
}
else
SparseMatrix.push_back(n);
}
Решение
Первое, что выделяется, это то, что вы реализуете свои собственные функции для поиска элемента: вот что std::find для. Итак, вместо:
bool alreadyPresent = false;
int i = 0;
for(i=0; i<SparseMatrix.size(); i++)
{
if((SparseMatrix[i].x == x) && (SparseMatrix[i].y == y))
{
alreadyPresent = true;
break;
}
}
Вы должны написать:
auto it = std::find(SparseMatrix.begin(), SparseMatrix().end(), Comparer);
где Comparer это функция, которая сравнивает два SparseMatNode объекты.
Но главное улучшение будет от использования соответствующего контейнера. Вместо std::vectorвам будет гораздо лучше использовать ассоциативный контейнер. Таким образом, поиск элемента будет иметь только O(logN) сложность вместо O(N), Вы можете немного изменить свой SparseMatNode Класс следующим образом:
typedef std::pair<int, int> Coords;
typedef std::pair<const Coords, float> SparseMatNode;
Вы можете покрыть эту typedef внутри класса, чтобы обеспечить лучший интерфейс, конечно.
А потом:
std::unordered_map<Coords, float> SparseMatrix;
Таким образом, вы можете использовать:
auto it = SparseMatrix.find(std::make_pair(x, y));
найти элементы гораздо эффективнее.
Другие решения
Разреженные матрицы обычно не хранятся в виде вектора триплетов, как вы пытаетесь.
MATLAB (как и многие другие библиотеки) использует структуру данных Compressed Sparse Column (CSC), которая очень эффективна для статических матриц. Функция MATLAB sparse также не построить матрицу по одной записи за раз (как вы пытаетесь) — это занимает массив триплетных записей и упаковывает всю последовательность в матрицу CSC. Если вы пытаетесь построить статическую разреженную матрицу, это путь.
Если вам нужен динамически разреженный матричный объект, который поддерживает эффективную вставку и удаление записей, вы можете посмотреть на различные структуры — возможно, std::map триплетов или массив списков столбцов — см. Вот для получения дополнительной информации о форматах данных.
Также есть много хороших библиотек. Если вы хотите выполнять разреженные матричные операции / факторизации и т. Д. — SuiteSparse хороший вариант, иначе собственный также имеет хорошую разреженную поддержку.
Разреженные матрицы обычно хранятся в формате сжатого разреженного ряда (CSR) или сжатого разреженного столбца (CSC, также называемого Harwell-Boeing). MATLAB по умолчанию использует CSC, IIRC, в то время как большинство пакетов разреженных матриц, как правило, используют CSR.
В любом случае, если это для производственного использования, а не для обучения, я бы рекомендовал использовать матричный пакет с поддержкой разреженных матриц. В мире C ++ мой любимый собственный.
Вы пробовали сортировать ваш вектор разреженных узлов? Выполнение линейного поиска становится дорогостоящим каждый раз, когда вы добавляете узел. Вы можете вставить на месте и всегда выполнять бинарный поиск.
Поскольку разреженная матрица может быть огромной и должна быть сжата, вы можете использовать std::unordered_map. Я предполагаю матричные индексы (x а также y) всегда позитивны.
#include <unordered_map>
const size_t MAX_X = 1000*1000*1000;
std::unordered_map <size_t, float> matrix;
void addNode (size_t x, size_t y, float val)
{
size_t index = x + y*MAX_X;
matrix[index] += val; //this function can be still faster
if (matrix[index] == 0) //using find() / insert() methods
matrix.erase(index);
}
Если std::unordered_map недоступно в вашей системе, вы можете попробовать std::tr1::unordered_map или же stdext::hash_map…
Если вы можете использовать больше памяти, то используйте double вместо float, это немного улучшит вашу скорость обработки.