Serial insertion into sparse matrices should be done in O(1)

[vkostyukov]

If we insert values into CSR matrix row-by-row or into CCS matrix column-by-column, in a serial order, it should take O(1) time. Here is the check that does if for sparse vector at searchForIndex routine:

if (cardinality == 0 || i > indices[cardinality - 1]) {
  return cardinality;
}

[vkostyukov]

@DWiechert, this might be interesting for you.

[DWiechert]

Would you rather me work on this one instead of #172? I currently have not started on that one so there would be no work lost at this point.

[vkostyukov]

Oh, sorry! I've forgot you start working on that issue. Please, go ahead with any issue you like!

[DWiechert]

I'll continue with that one (#172) and try to get it done in the next day or so. Then, if this is still open I can come back to it.

[DWiechert]

@vkostyukov, care to elaborate a little more about this issue? Or is it just adding a similar check to CSRMatrix and CCSMatrix?

[vkostyukov]

The idea is to not do binary search in the array[0...N-1] if we insert the value into the first empty spot in the array. The current version of Matrix.insert does binary search for every call. But we can do it in O(1) if we do serial insertions (indices are always growing).

Small example on sparse vector.

Initially everything is empty:

cardinality = 0 // non-zero elements
indices = [0, 0, 0, 0]
value = [0, 0, 0, 0]

If we write the first element a[5] = 42.0:

cardinality = 1
indices = [5, 0, 0, 0]
value = [42.0, 0, 0, 0]

In case of writing a[10] = 100. We don't need to binary search to find a proper place. Since both of the arrays are sorted between 0 and cardinality. We can check the right-most element's index, and if it's less the our index, we can just write our element right after the right-most element. No binary search here.

[DWiechert]

@vkostyukov, I won't be able to focus on this issue until the new year. I just thought I'd let you know in case you wanted to pass it off to someone else in the mean time.

[vkostyukov]

No worries @DWiechert. I will handle this.