Want to improve Contains execution time? Use a Dictionary instead of a List

Most of you probably know that instead of using multiple string concatenation, using the StringBuilder class is better.

But did you know that the Contains method is more efficient with a Dictionary than with a list?

With the following sample,

int max = 23997907;
List<int> l = Enumerable.Range(1, max).ToList();
Stopwatch sw = new Stopwatch();
sw.Start();
bool b = l.Contains(-1);
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);
Dictionary<int, object> d = Enumerable.Range(1, max).ToDictionary(i => i, i => (object)null);
sw = new Stopwatch();
sw.Start();
b = d.ContainsKey(-1);
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);


The average result is 150 ms on my computer for the list and always less than 1 ms for the Dictionary.



However, be careful, a Dictionary uses more memory than a List. // In my sample, 23997907 is the maximum value before having a OutOfMemoryException for the Dictionary.



Update



The HashSet class is better than a Dictionnary in my sample because we don’t have the Key/Value notion.



HashSet<int> h = new HashSet<int>(Enumerable.Range(1, max));
sw = new Stopwatch();
sw.Start();
b = h.Contains(-1);
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);


However, we still have the same memory limit.

This entry was posted in 7672. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *


*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>