Sparse Array in C! How accomplish it? Can I alloc only parts of an array?

Question

Hi guys!

The first question is: "How I do a simple sparse array in C (with one dimension only)?" {with my own hands, without libraries.}

And the last one: "Can I allocate only parts of an array?"

like *array;

then use malloc to allocate some mem for this; so, We free the index that we don't want.

Can I do it?

Thanks so much!

Answer 1

It is not uncommon to implement these in linked structures of one kind or another. In one dimension you can simple generate a linked list of occupied regions, and I've discussed a two dimensional implementation in another context before.

You do lose O(1) access time this way, but the win on space can be considerable if the structure really is sparse.

Answer 2

No, you can't do it.

What you can do is to allocate blocks, but you need to design it carefully.

Probably the best optimization is to use ranges of cell. So you can use a linked list (or a map) of available ranges:

struct SparseBlock
{
  void *blockData;
  int beginIndex;
  int endIndex;
  struct SparseBlock *next;
}

obviously if endIndex - beginIndex = 0 you have a single cell (that is isolated inside the array), otherwise you have got a block of cells, allowing you to allocate the right amount of memory for it.

This approach is simple for immutable sparse vectors, otherwise you should take care of

• restructuring the blocks whenever a hole is filled or generated
• just store single cells

In addition you have to decide how to index these blocks, you can keep them ordered in a linked list, or you can use a map to have a constant O(1) time to retrieve a n-th block (of course you will have to insert many equal keys for the same block if it's a range or reduce the index to the nearest lower index available).

Solutions are many, just express your creativity! :)

Answer 3

Have a look at sparsetable by Google: http://www.google.com/codesearch/p?hl=en#c4POQdJNHE8/trunk/vendor/sparsehash/current/src/google/sparsetable&q=sparse_hash_map&d=6

It does exactly that.