views:

2933

answers:

4

I can test for the presence of a key in an NSDictionary in two ways:

BOOL containsKey = [[dictionary allKeys] containsObject:foo];

BOOL containsKey = ([dictionary objectForKey:foo] != nil);

which method is faster? Please show your work.

+3  A: 

I don't see how asking for the allKeys array could possibly be faster, otherwise NSDictionary would at least do the equivalent internally.

EDIT: I suppose that you could construct a case where the allKeys method would be faster - by taking a long time in your key's hash method, but not in your isEqual: method, for example. And you could also swap in a crazy implementation for NSDictionary in which they are swapped, too (since NSDictionary is abstract.)

Jesse Rusak
Agreed. Asking for allKeys is going to give you an NSArray which containsObject must then iteratively search looking for foo. objectForKey, on the other hand, will use a hash to compute the location of foo in the dictionary so that foo's existence can be determined directly.
Jarret Hardie
+16  A: 

A hash lookup should be faster in general than going over all the dictionary keys, creating an array from them (memory allocation is relatively expensive) and then searching the array (which can't even be a binary search since the array is not sorted).

For the sake of science, though, I made two executables that just execute each style 1 million times and timed them.

With allKeys:

real    0m4.185s
user    0m3.890s
sys     0m0.252s

With objectForKey:

real    0m0.396s
user    0m0.189s
sys     0m0.029s

Obviously, various factors can influence this — size of the dictionary, caching the allKeys return value, etc. I wouldn't expect there to be a case in which the array search is faster than the dictionary lookup, though.

Chuck
+1 for stylishly producing chapter and verse
Jarret Hardie
Thanks for the timing data. How many keys where in your dictionary for these tests?
alfwatt
+2  A: 

When thinking about performance questions like this, keep in mind that the Foundation data classes swap out their underlying data structures depending on how many objects you store in them. For example, I think a small NSArray actually uses a hash table for storage until it reaches a certain size.

Marc Charbonneau
Isn't it more likely to be the other way round where a hash table becomes more beneficial? Testing 10 or so objects for equality is trivial. Have several thousand objects though, and a hash table becomes a clear win.
Mike Abdullah
You could very well be right, I remember someone wrote an article (along with benchmarks) about this some time ago, but I haven't given it much thought since then.
Marc Charbonneau
A: 

valueForKey should be even faster.

MattDiPasquale
@Matt according to the docs, `valueForKey` on an `NSDictionary` simply invokes `objectForKey` after doing some string processing: http://developer.apple.com/library/mac/#documentation/Cocoa/Reference/Foundation/Classes/NSDictionary_Class/Reference/Reference.html
Dave DeLong