Slow performance of sparse matrix using std::vector

Question

I'm trying to implement the functionality of MATLAB function sparse.

Insert a value in sparse matrix at a specific index such that:

If a value with same index is already present in the matrix, then the new and old values are added.

Else the new value is appended to the matrix.

The function addNode performs correctly but the problem is that it is extremely slow. I call this function in a loop about 100000 times and the program takes more than 3 minutes to run. While MATLAB accomplishes this task in a matter of seconds. Is there any way to optimize the code or use stl algorithms instead of my own function to achieve what I want?

Code:

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);
}

Answer 1

The first thinks that stands out is that you are implementing your own functionality for finding an element: that's what std::find is for. So, instead of:

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;
  }
}

You should write:

auto it = std::find(SparseMatrix.begin(), SparseMatrix().end(), Comparer);

where Comparer is a function that compares two SparseMatNode objects.

But the main improvement will come from using the appropriate container. Instead of std::vector, you will be much better off using an associative container. This way, finding an element will have just a O(logN) complexity instead of O(N). You may slighly modify your SparseMatNode class as follows:

typedef std::pair<int, int> Coords;
typedef std::pair<const Coords, float> SparseMatNode;

You may cover this typedefs inside a class to provide a better interface, of course.

And then:

std::unordered_map<Coords, float> SparseMatrix;

This way you can use:

auto it = SparseMatrix.find(std::make_pair(x, y));

to find elements much more efficiently.