C# Dictionary: faster access but less memory footprint

Question

I want some advise on the best way to store and access with minimum memory footprint and maximum access performance.

Eg. for each vehicle make i want to store model and name.

i have some thoughts below:

Option 1:

Dictionary<string, Dictionary<string, string>> values = new Dictionary<string, Dictionary<string, string>>();
Dictionary<string, string> list = new Dictionary<string, string>();
list.Add("2001", "Jetta S");
list.Add("2002", "Jetta SE");
list.Add("2002", "Jetta LE");
values.Add("VolksWagen", list);

Option 2:

Dictionary<string, List<KeyValuePair<string, string>>> values2 = new Dictionary<string, List<KeyValuePair<string, string>>>();
<pre lang="xml">List<KeyValuePair<string, string>> list2 = new List<KeyValuePair<string, string>>();
list2.Add(new KeyValuePair<string, string>("2001", "Jetta S"));
list2.Add(new KeyValuePair<string, string>("2002", "Jetta SE"));
list2.Add(new KeyValuePair<string, string>("2002", "Jetta LE"));
values2.Add("VolksWagen", list2);

Option 3:

Dictionary<string, List<string>> values1 = new Dictionary<string, List<string>>();
List<string> list1 = new List<string>();
list1.Add("2001:Jetta S");
list1.Add("2002:Jetta SE");
list1.Add("2002:Jetta LE");
values1.Add("VolksWagen", list1);

• Option 1: faster access of make and name but most memory footprint
• Option 2: fast access of make and name but more memory footprint
• Option 3: slow access of make and name (would have to parse it) but less memory footprint

there would be more than 1500 dictionaries like above.

Any suggestions for fastest access but less memory footprint is appreciated?

Thanks.

Answer 1

SortedList<TKey,TValue> is a flat list (so no huge increase in memory footprint), that uses binary-search for access - so O(log(n)) - so not as fast as Dictionary<TKey,TValue> at O(1) - but much better than a List<T> (or other linear search) at O(n).

If you want fastest access, you need to use extra memory for a hash-table.

As a side-note, SortedList<TKey,TValue> also allows efficient access by int index, which is hard for SortedDictionary<TKey,TValue>, and virtually meaningless for Dictionary<TKey,TValue>.

Obviously in your scenario you may need to combine SortedList<,> with either nesting or a composite key - but IMO that is going to be your best route for getting a balance of memory and accessor-performance. You could use a dedicated composite key, i.e. an iummutable struct with the composite key members, overriding GetHashCode() and Equals, implementing IEquatable<T>, and for sorting: implementing IComparable and IComparable<T>.

Answer 2

You shouldn't choose your data structure primarily by memory "footprint" but by access pattern: What are the most frequent lookups you want to do, how often the structure will be updated and so on.

If you want to fill the structure once and then look up the cars by make and construction year, the first approach seems most reasonable (and readable/understandable).

Btw, given the fact that multiple models can be released in one year, you should probably use a Dictionary<string, Dictionary<string, List<string>>>. And if it's really years that you want to store, you shouldn't use strings as keys but Int16 instead.

Answer 3

You can use a Dictionary with NameValueCollection:

var values = new Dictionary<string, NameValueCollection>();
NameValueCollection list = new NameValueCollection();
list.Add("2001", "Jetta S");
list.Add("2002", "Jetta SE");
list.Add("2002", "Jetta LE");
values.Add("VolksWagen", list);

Or with collection Initializers:

var values = new Dictionary<string, NameValueCollection> 
    { 
        { "VolksWagen", new NameValueCollection 
            { 
                { "2001", "Jetta S" }, 
                { "2002", "Jetta SE" }, 
                { "2002", "Jetta LE" } 
            } 
        } 
    };

Although I am no expert on memory footprint, IMHO this will provide you the best access pattern in this particular scenario.