c - Compact array in C

Question

Suppose i have these pairs of nodes (ID):

• 0 1
• 0 8
• 500 4
• 8 300

I know the number of unique nodes: 6. How can i save them nto a matrix, without allocating a 500x500 matrix? Which kind of mapping can be used?

Thanks in advance!

Answer 1

What you might want is a sparse-matrix - you can imagine this as an array containing values that correspond to an x,y for indexing the matrix and the value stored there, so that matrices which are mostly zeros can be stored in a small amount of space. The memory overhead of this data structure is O(n) where n is the number of non-zero entries in the matrix.

In practice you can use something other than an actual array for performance benefits since searching through an array for an x,y is costly, particularly if it is not there (the most common case).

One option would be to use fast hash map type structure to store the values by hashing the x,y position to generate a key...

More information: http://en.wikipedia.org/wiki/Sparse_matrix

Answer 2

This is called a sparse matrix, and there are lots of representations you can use. Which one you want depends on what operations you need to be able to do quickly.

Check out the Wikipedia sparse matrix article for details.