-
Notifications
You must be signed in to change notification settings - Fork 109
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Serial insertion into sparse matrices should be done in O(1) #227
Comments
@DWiechert, this might be interesting for you. |
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. |
Oh, sorry! I've forgot you start working on that issue. Please, go ahead with any issue you like! |
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. |
@vkostyukov, care to elaborate a little more about this issue? Or is it just adding a similar check to |
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 Small example on sparse vector. Initially everything is empty:
If we write the first element
In case of writing |
@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. |
No worries @DWiechert. I will handle this. |
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:The text was updated successfully, but these errors were encountered: