Finding a value from dictionary list objects

Question

I have something that could potentially be a very large list of Dictionary objects that I need to find a specific value from a key. I can of course do something like

foreach(Dictionary<long, string> t in Foo) { if (t.TryGetValue(key, out name)) break; } 

and it will joyfully go through Foo until it finds the key or end of the foreach.

To speed this up, I would rather use a small amount of LINQ. If it were a regular list, I would be fine, but since this is an object of a dictionary list, I'm not too sure how to do it.

Help or advice appreciated.

Answer 1

I think you wrote the most effective version of what you want to do. Since Linq does not play well with the output parameters, it will take a little longer. But here is how you do it:

 var dict = Foo.FirstOrDefault(d => d.ContainsKey(key)); if (dict != null) { dict.TryGetValue(key, out name); } 

Answer 2

This code will be shorter, but will take a little longer:

 var dictWithKey = Foo.First(d => d.ContainsKey(key)); name = dictWithKey[key]; 

The real question, however, is why do you use a list of dictionaries for this, especially since you say you want to “speed it up”. This tells me, probably, something that your code will do more than once, right?

A more suitable approach would probably be to save a single dictionary containing all key / value pairs, so you can perform a single search rather than repeating multiple words.

Answer 3

Well, depending on the number of dictionaries in Foo may be an advantage when using Parallel LINQ (PLINQ):

 string name = null; Parallel.ForEach(foo, f => { if (name != null) return; if (f.ContainsKey(key)) name = f[key]; }); 

The implementation assumes that the given key is mapped to the same value or that the key is unique in all dictionaries. It is also assumed that the value is not equal to zero.

With 5,000,000 dictionaries containing one key and one value, this works about 150 ms faster than your original implementation.

Benchmarks (Intel Core i5 with a clock frequency of 2.4 GHz with two physical cores and two virtual cores):

• PLINQ: 89ms
• Initial Solution: 250 ms

However, I want to emphasize that PLINQ is not always the answer to getting things to work faster. In some cases, when you have code that uses parallel foreach loops to move multiple elements, the actual cost of starting threads in the background is actually much more expensive than just repeating using a simple for loop - so use it when there is a lot elements to iterate through :)

Answer 4

You have the key setting as long.

 long key = 1; Dictionary<long, string> name = foo.Where(d => d.ContainsKey(key)).First();