How Space-Efficient Are Sparse Arrays?

In the implementation shown in sa.c, on the HP workstations (which use 4-byte integers and 4-byte pointers) the space requirements of an n by n sparse array containing m non-zero elements are:

• sizeof (sa_t) = 20 bytes.
• 2 * sizeof (sa_cell_t *) * n = 8n bytes (4m each for the rows and cols arrays).
• 2 * sizeof (sa_cell_t) * m = 24m bytes for the m values.
• The malloc library may need to allocate some extra space for its own use.

As we can see, this representation is not worthwhile unless the arrays are indeed fairly sparse: each element requires at least 6 times as much memory to represent as it would in an ordinary array. (If only row or column lists are maintained, then the requirements are cut in half, but this may have a profound effect on the running time of algorithms that access the array.)