stuh505

03-16-2006, 12:03 AM

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 300x400 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(r) 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

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 300x400 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(r) 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