Hey guys, here is some code for a sparse matrix I wrote. This is a very general struct that many people may find useful.
A sparse matrix works like a regular matrix except that it does not waste memory by storing blank entries, so it is ideal if you want to be storing values over a large range of space but still want to be able to look up values quickly.
To store some values at [1,1] and [300,400] in a regular matrix would require a 300×400 matrix…and would store 120,000 values. A sparse matrix can store this using only 6 values.
The sparse matrix also allows you to store and retrieve elements pretty quickly. If your matrix is very sparse it will take O(1) time to get/set a value (same as regular matrix). If your matrix is very dense it can take up to O® time to get/set, where r is the number of values in the row you are looking at.
Example:
m = (sparseMatrix2d 0) –where 0 is default value for unassigned coordinates
m.setValue 200 300 4
m.getValue 200 300 –returns 4
m.getValue 200 299 –returns 0
m.erase
m.getValue 200 300 –returns 0
thank you.
I like it.
Georg
Haha, this is great. Only yesterday me and a collegue was discussing spare matrices and that they can be extremely useful at times
/Andreas
I have added two additional types of sparse matrices.
The first type, sparseMatrix2d, is for row/col indexing, starting at 1,1
Now I provide sparseMatrix3d which allows x/y/z indexing starting at 1,1,1
Also, sparseMatrix3dc, which allows x/y/z indexing from negative infinity to infinity
Usage is exactly the same as the first kind
eg,
m = (sparseMatrix3dc 0)
m.setValue -200 0 1 3
m.getValue -200 0 1 –returns 3