Alex Rivera | Logout

C# Dictionary: faster access but less memory footprint

Asked 2011-02-16T08:07:13.967
11

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.

c# performance dictionary
Edit
Report

1 Answer

23

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>.

answered 2011-02-16T08:19:33.713

Your Answer