[RESOLVED] Given a value, find all keys with that value in a dictionary(of key, value)

Hi guys,

I have a dictionary(of someType, someOtherType) (the types are immaterial). With a given value, I need to find all the keys that have that value in the dictionary. What I am currently doing is this:

Code:

---

Dim foundList as New List(of someType)
For each key as someType in myDictionary.Keys
    If myDictionary(key) = givenValue Then
      foundList.Add(key)
    End If
Next

---

Although it works, I have a strong feeling that it's not optimized (I have to loop thru the whole dictionary.keys collection).
Is there a better way doing it (because I'm targeting .Net 2.0, no LINQ please...)?

Thanks for reading,
Stanav.

I can tell you that LINQ would be slower, so that's another reason to avoid it if you want optimization.

Furthermore, if you think about it, there really can't be a better solution if taken at face value. After all, how could the collection know whether it has seen all of the conforming values until it has visited each one? If the collection has some kind of index built on the value field, then it might be able to perform a superior search, but that would be an unwise feature to add to the Dictionary class, since it would cause an unnecessary overhead for the vast majority of cases.

In cases similar to this, where speed was of the essence, I have occasionally maintained a second dictionary that acted as a key for the first dictionary. This can take on several forms, such as a Dictionary (of <value from other dictionary>, List (of <keys from the other dictionary)). This would add a bit of overhead for adding values, since they would be added to two collections rather than one, but it would speed up a search.

That's pretty much all you can do without LINQ, and I'm not certain LINQ would be much more efficient anyway. If this is a frequent case and you're worried about performance (*and* there are many keys) you should probably create a secondary lookup that keeps track of these special keys for you.

*edit*
Ahhhh it's like I was reading SH's mind!

Snuck one in just ahead of Sitten, which is pretty darn good, since I took MANY more words to say the exact same thing. I'm not often first out of the gate, but sometimes I get a good start.

Could you use a data table with a primary key on the first column, for optimised searching, then when you need to search by value, you could use datatable.select ?

I would 'third' the second dictionary (Of List?) as a means of optimization for speed of lookup.

with out any further info on the issue, I'd say the code in post #1 is best... using LINQ would provide an alternative, how ever depending on the size of the data being looped through, performance would probably be a wash...

On a related note, I'd like to clarify something SH said about LINQ being slower... it's not always the case, and should be evaluated on a case by case basis. I happen to know of at least one situation where I got HUGE performance increase by switching a For Each into a LINQ query and then rummaged through the results. It seems counter intuitive, but point is, do your research and testing. In our case we were looking for hundreds (to thousands) of records out of thousands (to tens or hundreds of thousands) of records in datatables... so, yeah, LINQ was phenominally better than looping through the rows (or even doing a datatable.Select... which... does a loop on the back end, testing each row to see if it matches the criteria)....

Creating some kind of lookup list (I was thinking some how a hashtable might be beneficial, but I'm not sure how) ... would work... but only if the list is fairly stable and isn't going to change much (each time the list changes, the lookup would also need to be updated)... and it's something that's going to be used over and over and over... if you're only looking up the keys a couple of times, it may not be worth the effort.

I'd suggest creating an extension... but I don't think those were available in VS2005... that came later.

Other than the looping, nothing else is really coming to mind that hasn't been already suggested.

-tg

Right, there are situations where LINQ is going to be superior, but in my understanding of LINQ, this is not going to be one of them. Where LINQ shines is when you are doing a complex operation, but it appears to always be slower if all it is doing is finding item X in a simple collection. There is a chance that it might do as well or better in some cases where you are finding the set of X in a simple collection, but I think not. The only way it would do better in that case is if it has a superior means of creating the List (of T) that it returns. On the other hand, LINQ will do considerably better if there are JOINS or any other complex operation.

I appreciate you all for your inputs. My actual situation is, I have a collection of integer pairs where the first integer of the pairs are unique. Additionally, I need to find the max value of the 2nd integer in the pair in the collection so a dictionary(of integer, integer) would make perfect sense. Once those integer pairs are put into a dictionary, I can find the max value by simply calling dictionary.values.max function. Now that I have the max value, I need to link it back to the 1st integer of the pair and since there may be more than entry with the max value, running a loop is the 1st approach that came to my mind. However, as I said in the original post, this approach always requires the full dictionary to be looped through even though there is just 1 entry that has the max value.
Since you all suggested that the looping approach is already the best one, I guess I'll stick with it for now. I'll mark the thread as resolved.
Again, thanks everyone for your valuable inputs.

This is what I heard shaggy say

Code:

---

Public Class Form1

    Class intpairs
        Private uip As New Dictionary(Of Integer, Integer)
        Private maxP As New Dictionary(Of Integer, List(Of Integer))

        Public Sub addPair(key As Integer, value As Integer)
            Me.uip.Add(key, value)
            If Not Me.maxP.ContainsKey(value) Then
                Me.maxP.Add(value, New List(Of Integer))
            End If
            Me.maxP(value).Add(key)
        End Sub

        Public Function keysWithVal(value As Integer) As List(Of Integer)
            If Me.maxP.ContainsKey(value) Then
                Return Me.maxP(value)
            Else
                Return New List(Of Integer)
            End If
        End Function
    End Class

    Dim prng As New Random

    Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
        Dim foo As New intpairs
        For x As Integer = 1 To 1000
            foo.addPair(x, prng.Next(1, 43))
        Next

        Dim keysWval As List(Of Integer) = foo.keysWithVal(42)

        For Each k As Integer In keysWval
            Debug.WriteLine(k)
        Next
        Stop
    End Sub
End Class

---

and it seems to work. So I must be missing what the question is.

RE: when LINQ is slower.

LINQ always ends up boiling down to state machines and delegate calls. Delegate calls are more expensive than normal function calls, but not enough to worry about when n is small. LINQ is at its best when it can iterate over a collection on the fly and skip complex processing for many items. There are some operations like Count() and Reverse() that have to iterate the entire collection; if combined with delegate calls it's easy to see how LINQ going through an enumerator and making delegate calls would be slower than an indexed loop. How much so? Probably handfuls of cycles per iteration. For n < 1000 simple cases are probably not noticeable.

In this case, you want each key where the key has some value:

Code:

---

Dim keys = _dictionary.Keys.Where(
    Function(ByVal key) _dictionary(key) = targetValue)

---

The delegate call's not the worst thing here. There's no way to get the right values without iterating over every key in the dictionary. It's exactly equivalent to your For loop. So the fastest this can get is one iteration over the keys, O(N).

If you've got a secondary dictionary, you can do it faster:

Code:

---

' Assuming Dictionary(Of Value, List(Of Key))
Dim keys = _secondaryDictionary(targetValue)

---

That's O(1), and it only adds a small overhead to adding. The more items you're working with, the more that O(1) pays for the memory overhead, which is likely to be quite trivial.