Enumerate and modify a dictionary

[Bob Altman]

Hi all,

I'm trying to do something that should be really easy, but I can't think of an
obvious way to do it. I have a dictionary whose value is a "value type" (as
opposed to a reference type -- in this case, a Boolean):

Dim dic As New Dictionary(Of Int32, Boolean)
dic(123) = True

I want to set all of the existing entries in the dictionary to False. The
obvious solution:

For Each value As Boolean In dic.Values
value = False
Next

does not set the dictionary values to False as one would expect. Rather, this
code gets a temp variable named value and sets that temp variable to false,
leaving the dictionary value unchanged.

Ok, so I try this code:

For Each key As Int32 In dic.Keys
dic(key) = False
Next

That gets me the dreaded "Collection was modified; enumeration operation may not
execute."

So, how can I set all of the Boolean values in this dictionary to False?

TIA - Bob

 

[Armin Zingler]

So, how can I set all of the Boolean values in this dictionary to
False?

For Each key In dic.Keys.ToArray
dic(key) = False
Next



Armin

 

[Family Tree Mike]

It seems to me that you should just check if the dictionary does not contain
the key, assume false. You should not need to fill the dictionary with
every possibility.

dict.ContainsKey(123), for example.

 

[Kerry Moorman]

Bob,

While we're wating for the elegant solution, here's abrute force solution:

Dim myKeysArray(dic.Keys.Count - 1) As Integer
dic.Keys.CopyTo(myKeysArray, 0)

For Each key As Integer In myKeysArray
dic(key) = False
Next

Kerry Moorman

 

[Bob Altman]

While we're waiting for the elegant solution, here's a brute force solution:

Dim myKeysArray(dic.Keys.Count - 1) As Integer
dic.Keys.CopyTo(myKeysArray, 0)

For Each key As Integer In myKeysArray
dic(key) = False
Next

Kerry Moorman

Thanks Kerry. I didn't notice that the KeyCollection had a CopyTo function.

I wrote a little app to test the performance of your solution vs. creating a new
Dictionary and populating it with the keys from the old dictionary and values of
False, like this:

' Fabricate a new Dictionary with keys
' from the old Dictionary
Dim newDic As New Dictionary(Of Int32, Boolean)
For Each kvp As KeyValuePair(Of Int32, Boolean) In dic
newDic(kvp.Key) = False
Next

' Replace the old Dictionary with the new one
dic = newDic

It turns out that creating a new dictionary is *much* faster. In my test app
(shown below) I repeat the code that sets the Dictionary entries to False 10,000
times. The algorithm that copies the keys array takes around 700 ms, which the
algorithm that creates a new dictionary only takes about 100 ms. Both
algorithms leave some garbage behind for the GC to collect, and I can't think of
an easy way to measure that part of the performance.

Bob

--- Code ---

Public Class Form1

Private Sub Button1_Click( _
ByVal sender As System.Object, _
ByVal e As System.EventArgs) Handles Button1.Click
' Initialize the Dictionary
Dim dic As New Dictionary(Of Int32, Boolean)

For i As Int32 = 1 To 1000
dic(CInt(Rnd() * 10000)) = True
Next

Dim t1 As DateTime = Now

For i As Int32 = 1 To 10000

' Kerry's algorithm
Dim keys(dic.Count - 1) As Int32
dic.Keys.CopyTo(keys, 0)
For Each key As Int32 In keys
dic(key) = False
Next
Next

Dim t2 As Date = Now
Label1.Text = (t2 - t1).Milliseconds.ToString
End Sub

Private Sub Button2_Click( _
ByVal sender As System.Object, _
ByVal e As System.EventArgs) Handles Button2.Click
' Initialize the Dictionary
Dim dic As New Dictionary(Of Int32, Boolean)

For i As Int32 = 1 To 1000
dic(CInt(Rnd() * 10000)) = True
Next

Dim t1 As DateTime = Now

For i As Int32 = 1 To 10000
' Bob's algorithm
Dim newDic As New Dictionary(Of Int32, Boolean)
For Each kvp As KeyValuePair(Of Int32, Boolean) In dic
newDic(kvp.Key) = False
Next

dic = newDic
Next

Dim t2 As Date = Now
Label1.Text = (t2 - t1).Milliseconds.ToString

End Sub
End Class

 

[Bob Altman]

Label1.Text = (t2 - t1).Milliseconds.ToString

Whoops! Better make that TotalMilliseconds, if you want the actual times,
not just the fractional part of a second.

Ouch! It's amazing how many ways there are to write subtly wrong code. The
funny part is that it sure seemed to me that it took a lot longer than 1
second to complete (uh, more like 3 seconds)...

On my machine, "Bob's Algorithm" takes about 4 times longer, just over 3
seconds, to complete.

You might be interested in seeing what happens if you create a class to
hold your Boolean, and use objects in the dictionary instead of value
types.

That was actually the first thing I tried, since intuition tells me that it
would be a lot faster to just write to a Boolean field rather than replacing
the entire Dictionary entry. But I gave up when I discovered that I use the
ContainsValue method on the dictionary

If dic.ContainsValue(False) Then <do something>

and I didn't want to figure out how to either implement some arcane
interface or write my own "search through the darned thing" routine to get
that to work. But as long as I'm actually doing some performance testing, I
guess I really should try that and see how it compares. (Maybe if I'm lucky
I'll come back tomorrow morning -- it's 10:40 PM in Southern California
right now -- and someone will run that test and post the results.)

Bob

 

[Steven Cheng [MSFT]]

Hi Bob,

Regarding on the performance of the two methods you've considered so far:

1. copy keys to array and modify the original collection

2. not copy keys but directly create a new dictionary

Here are some of my understanding and suggetion:

** For the performance, it depend on what's the critical point of the
execution. For the two approaches here:

1. copy keys approach's critical point is copying all the keys from
dictionary to an key array

2. creating new dictionary's critical point is creating the new dictonary
and also all the objects in it.

Here in your case, the object is simply a boolean value, therefore, I
think the overhead of copying keys into array (in #1 ) will contribute to
the most performance overhead. However, if the stored objects are large
complex class object, I think the creating new dictionary approach will be
overkilled by creating every new objects in the original dictionary.

Therefore, you can decide which approach to use depend on the actual
screnario.

Sincerely,

Steven Cheng

Microsoft MSDN Online Support Lead


Delighting our customers is our #1 priority. We welcome your comments and
suggestions about how we can improve the support we provide to you. Please
feel free to let my manager know what you think of the level of service
provided. You can send feedback directly to my manager at:
(e-mail address removed).

==================================================
Get notification to my posts through email? Please refer to
http://msdn.microsoft.com/subscriptions/managednewsgroups/default.aspx#notif
ications.

==================================================
This posting is provided "AS IS" with no warranties, and confers no rights.

--------------------

 

[Bob Altman]

You might be interested in seeing what happens if you create a class to

That was actually the first thing I tried,
but I gave up when I discovered that I use the ContainsValue method on the
dictionary

If dic.ContainsValue(False) Then <do something>

and I didn't want to figure out how to either implement some arcane
interface or write my own "search through the darned thing" routine to get
that to work.

Ok, I knew digging this simple bit of knowledge out of the documentation was
going to be a pain, and I was right. You'd think that now that VS is fully
mature the documentation would contain more and better examples baked right
into the topics that F1 help most easily gets you to. Anyway, after a
little spelunking I fgured out that a class T needs to implement the
IEquatable(Of T) interface in order to get Dictionary(Of T).ContainsValue to
work. Why the documentation for Dictionary(Of T).ContainsValue doesn't say
that in so many words is beyond me!

After all that, it turns out that executing ContainsValue on a Dictionary(Of
Int32, Boolean) is about 3 times faster than doing the same thing on a
Dictionary(Of Int32, MyWrapperClass).

So, to summarize:

1. Modifying all of the values in a Dictionary whose values are value types
is surprising difficult.
2. The fastest way to do it seems to be to make a copy of the keys, and use
that copy to iterate through the Dictionary.
3. Performing the same operation on a Dictionary whose values are reference
types is straightforward and much faster, but requires extra claptrap to
declare the reference type.
4. In order to get Dictinoary(T).ContainsValue to work with values that are
reference types requires that the reference type implement IEquatable. As
one would expect, ContainsValue is much faster operating on Boolean values
compared with objects that wrap Boolean values.

----- Code (requires 5 buttons and one label) -----

Public Class Form1

Dim m_booleanDictionary As New Dictionary(Of Int32, Boolean)

Private Class BoolWrapper
Implements IEquatable(Of BoolWrapper)

Public Value As Boolean

Public Sub New(ByVal value As Boolean)
Me.Value = value
End Sub

Public Function Equals1( _
ByVal other As BoolWrapper) As Boolean Implements System.IEquatable(Of
BoolWrapper).Equals
Return Me.Value = other.Value
End Function
End Class

Dim m_classDictionary As New Dictionary(Of Int32, BoolWrapper)

Private Sub Form1_Load( _
ByVal sender As System.Object, _
ByVal e As System.EventArgs) Handles MyBase.Load
For i As Int32 = 1 To 1000
Dim key As Int32 = CInt(Rnd() * 10000)
m_booleanDictionary(key) = True
m_classDictionary(key) = New BoolWrapper(True)
Next
End Sub

Private Sub Button1_Click( _
ByVal sender As System.Object, _
ByVal e As System.EventArgs) Handles Button1.Click
Dim t1 As DateTime = Now

For i As Int32 = 1 To 10000

' Kerry's algorithm
Dim keys(m_booleanDictionary.Count - 1) As Int32
m_booleanDictionary.Keys.CopyTo(keys, 0)
For Each key As Int32 In keys
m_booleanDictionary(key) = False
Next
Next

Dim t2 As Date = Now
Label1.Text = (t2 - t1).TotalMilliseconds.ToString
End Sub

Private Sub Button2_Click( _
ByVal sender As System.Object, _
ByVal e As System.EventArgs) Handles Button2.Click
Dim t1 As DateTime = Now

For i As Int32 = 1 To 10000
' Bob's algorithm
Dim newDic As New Dictionary(Of Int32, Boolean)
For Each kvp As KeyValuePair(Of Int32, Boolean) In m_booleanDictionary
newDic(kvp.Key) = False
Next

m_booleanDictionary = newDic
Next

Dim t2 As Date = Now
Label1.Text = (t2 - t1).TotalMilliseconds.ToString
End Sub

Private Sub Button3_Click( _
ByVal sender As System.Object, _
ByVal e As System.EventArgs) Handles Button3.Click
Dim t1 As DateTime = Now

For i As Int32 = 1 To 10000
For Each t As BoolWrapper In m_classDictionary.Values
t.Value = False
Next
Next

Dim t2 As Date = Now
Label1.Text = (t2 - t1).TotalMilliseconds.ToString
End Sub

Private Sub Button4_Click( _
ByVal sender As System.Object, _
ByVal e As System.EventArgs) Handles Button4.Click
' Button 4 tests ContainsValue time for Dictionary of Booleans
Dim t1 As DateTime = Now

For i As Int32 = 1 To 10000
m_booleanDictionary.ContainsValue(True)
m_booleanDictionary.ContainsValue(False)
Next

Dim t2 As Date = Now
Label1.Text = (t2 - t1).TotalMilliseconds.ToString
End Sub

Private Sub Button5_Click( _
ByVal sender As System.Object, _
ByVal e As System.EventArgs) Handles Button5.Click
' Button 5 tests ContainsValue time for Dictionary of objects
' that implement IEquatable
Dim t1 As DateTime = Now

Dim falseWrapper As New BoolWrapper(False)
Dim trueWrapper As New BoolWrapper(True)

For i As Int32 = 1 To 10000
m_classDictionary.ContainsValue(trueWrapper)
m_classDictionary.ContainsValue(falseWrapper)
Next

Dim t2 As Date = Now
Label1.Text = (t2 - t1).TotalMilliseconds.ToString
End Sub
End Class