Sparse matrixes - algorithms

Using Arduino Programming Questions
#1

Not a question, just a page containing info of interest to arduino programmers. We occasionally get the case where people are trying to do this:

int a[30][30][30];

And running out of memory. It's sometimes that case that almost all of the values in these matrixes are zero. In those cases, what is needed is a compact way to store a sparsely-populated matrix.

The broader issue is that back in the day, computers had very limited memory and storage, and as a result there is a rich literature of methods of getting the job done in those sorts of constraints. It's something that Arduino programmers should consider when they run up against memory limits. Rather than getting a mega straight away, maybe there's something already out there that solves the problem in code.

Array after a while showing 0
#2

Mega only gives 8K of SRAM tho - need a 1284P with 16K SRAM!
I offer boards in a few form factors:
http://www.crossroadsfencing.com/BobuinoRev17/

1094×458 70.8 KB

#3

He does not mention using a hash table to implement a spare array. I've found that to be a most excellent choice.

When the structure is fixed at compile-time a Minimal Perfect Hash should be at least as memory efficient as the proposed solutions with the potential bonus of needing a single function independent of the array for access.

#4