2012-02-27 14:45:41allKeys/containsObject vs objectForKey, or The Power of O(1)
So, while I have read and thought interesting that dictionary key lookups are of order O(1), I haven't really used this fact in my everyday coding life. I have ignored the little NSDictionary method -objectForKey: because, well, I'm often not looking to make use of the object for that key, but rather just inquiring about the existence of the key. It's obvious now that I should've noted that getting said object's pointer is a very light weight operation and that this method can double as a simple query for a key's existence, something which is O(1). Checking thru an NSArray is O(N), so will scale terribly in comparison. It did make me wonder exactly how much better or worse the methods compare for arrays of various sizes.
To that end, I have whipped up the following F-Script that outputs such a comparison set of data for easy plotting. First the code, then the graph.
( fscript ) ✂
#!/usr/local/bin/fscript
divs := 5.
[ :N |
size := (10 raisedTo:N) intValue.
a := NSMutableDictionary new.
1 to:size do:[ :x | a addObject:x forKey:x ].
b := [ a allKeys containsObject:(size random) ].
c := [ a objectForKey:(size random) ].
time := [ :block |
t1 := NSDate date.
1 to:1000 do:block.
NSDate date timeIntervalSinceDate:t1
].
ave := [ :block |
sum := 0.
1 to:5 do:[ sum := sum + (time value:block) ].
sum/5.
].
timeB := ave value:b.
timeC := ave value:c.
sys out println:{ size, timeB, timeC, timeB/timeC }.
] value:@((5 * divs) iota +1 /divs).
1#!/usr/local/bin/fscript 2 3 divs := 5. 4[ :N | 5 size := (10 raisedTo:N) intValue. 6 a := NSMutableDictionary new. 7 1 to:size do:[ :x | a addObject:x forKey:x ]. 8 b := [ a allKeys containsObject:(size random)]. 9 c := [ a objectForKey:(size random)]. 10 time := [ :block | 11 t1 := NSDate date. 12 1 to:1000 do:block. 13 NSDate date timeIntervalSinceDate:t1 14]. 15 ave := [ :block | 16 sum := 0. 17 1 to:5 do:[ sum := sum + (time value:block)]. 18 sum/5. 19]. 20 timeB := ave value:b. 21 timeC := ave value:c. 22 sys out println:{ size, timeB, timeC, timeB/timeC }. 23 24 ] value:@((5 * divs) iota +1 /divs).
allKeys/containsObject in blue, objectForKey in yellowish-green
array size along the bottom, time to do the trials vertically.
For array sizes under 2500, the speed up is between 2x and 4x, so it proves its worth for any size array. After that point the benefits skyrocket, approaching 3200x for the 100k element array.
As it happens, I've only found one instance of my using the allKeys/containsObject combo in my last 3 iOS projects, so I don't feel like I've missed out much on this oversight, but it was interesting and another nice use for F-Script.