Least memory-intensive Collection?

Question

Apart from rolling my own collection, I'm wondering which existing (.NET 3.5) Collection and IDictionary uses the least amount of memory.

I'm currently using a

• List<int>, where I only add items and later iterate over it.
• Dictionary<int,int>, where I only set and get key-value pairs.

NOTE: I'm doing mature optimization.

EDIT: I do not know the size in advance, but approximately, the dictionary will grow to about 789679 elements and the list will contain, in average, 10-20 elements.

Answer 1

You can save some memory at the cost of CPU cycles:

int[] data;
{
   List<int> temp = ....;
   // fill the list
   data = temp.ToArray();
}

When you know the number of elements beforehand you can eliminate a few steps.

A Dictionary is not so easy to replace.

Answer 2

Indexing is always a trade-off between space and performance. The least memory-intensive implementation of both a list and dictionary interface is always going to be a flat array. Of course, this means that your dictionary performance is going to be terrible, and insertion performance (for either) will be worse!

For a list of 10-20 elements, frankly: don't even investigate. Just use List<T>. For such an utterly trivial volume of data there is no sensible question to answer.

Even 789679 isn't huge. However, if your emphasis is on memory, then simply pre-sorting the data is probably your best bet. You could then use binary-search to find the items. Not quite as fast as a hash-table implementation, but much less memory: just 2 arrays (or a single array of tuples). Or in other words: use SortedList<TKey,TValue>