2012-02-27 14:45:41 allKeys/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 )
  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.
  • Jeff (Thu, February 28th, 2013, 11:40am UTC)
    Perhaps interesting addenda. I wrote up the equivalent in straight Objective-C / Cocoa to see if F-Script had some differences from doing this more directly and I note some interesting results:

    On my i7 MacBook Pro Retina, The F-Script sees the exact ratios as above, getting gains between 2x-4x on the low end and just over 3200x at the high end. But the Objective-C version of the test, while showing the same 2x-4x at the low end, went up to a whopping 32,000x on the high end! It showed about 1000x on arrays of about 2500 elements. Crazy, huh? Here's the Objective-C code for the test:

    ( objc )
      1  #import <Foundation/Foundation.h>
    2 #include <time.h>
    3
    4 typedef BOOL (^existenceCheckBlock)();
    5
    6 int main() {
    7 unsigned int iseed = (unsigned int)time(NULL);
    8 srand (iseed);
    9
    10 int divs = 5;
    11 NSMutableDictionary *a = [NSMutableDictionary new];
    12
    13 existenceCheckBlock b = ^() {
    14 int test = (int)( 100000. * rand() / (double)(RAND_MAX+1) );
    15 return [[a allKeys] containsObject:@(test)];
    16 };
    17 existenceCheckBlock c = ^() {
    18 int test = (int)( 100000. * rand() / (double)(RAND_MAX+1) );
    19 return (BOOL)!![a objectForKey:@(test)];
    20 };
    21
    22 NSTimeInterval (^time)(existenceCheckBlock) = ^(existenceCheckBlock block) {
    23 NSDate *t1 = [NSDate date];
    24 for( int i=0; i<1000; i++ )
    25 block();
    26 return [[NSDate date] timeIntervalSinceDate:t1];
    27 };
    28
    29 double (^ave)(existenceCheckBlock) = ^(existenceCheckBlock block) {
    30 NSTimeInterval sum = 0;
    31 for (int i=0; i<5; i++)
    32 sum += time(block);
    33 return sum/5.;
    34 };
    35
    36 for (float N=.2; N<5; N+=.2) {
    37
    38 int size = (int)round( pow( 10., N ) );
    39 [a removeAllObjects];
    40 for (int i=1; i<size; i++)
    41 [a setObject:@(i+1) forKey:@(i)];
    42 NSTimeInterval timeB = ave(b), timeC = ave(c);
    43 NSLog(@"%6i, %8.6f, %8.6f, %8.6f", size, timeB, timeC, timeB/timeC);
    44 }
    45 }

  • Jeff (Thu, February 28th, 2013, 11:51am UTC)
    For the curious, the Objective-C version runs about twice the speed of the F-Script version on this hardware.

  • Jeff (Thu, February 28th, 2013, 1:54pm UTC)
    As my friend Rainer reminded me, NSSet's containsObject: is also O(1). So if you need heavy testing of an array, hit the set instead.

Leave a comment