Objective-C Collections

Episode #72 | 14 minutes | published on June 21, 2013
Subscribers Only
Choosing the appropriate collection for your use case is important, not only for ease of implementation but for performance. In this episode, we'll examine the performance characteristics of various collections such as NSSet, NSArray, NSOrderedSet, and NSDictionary.

Episode Links

Examples

        NSArray *names = @[@"Adam", @"Brittany", @"Charles", @"Diane", @"Eugene", @"Fannie", @"Gregory", @"Heather", @"Ishmael", @"Jennifer", @"Kenny", @"Lindsay", @"Marcus", @"Nina", @"Oscar", @"Paige"];

        NSMutableArray *people = [NSMutableArray arrayWithCapacity:[names count]];
        for (NSString *name in names) {
            Person *person = [[Person alloc] init];
            person.name = name;
            [people addObject:person];
        }

        NSMutableOrderedSet *set = [NSMutableOrderedSet orderedSetWithArray:people];

        Person *p1 = [[Person alloc] init];
        p1.name = @"Eugene";

        NSSet *namesToRemove = [NSSet setWithObjects:p1, nil];
        [set minusSet:namesToRemove];
        NSLog(@"Set: %@", set);

        NSCountedSet *countedSet = [NSCountedSet setWithArray:names];
        [countedSet addObject:@"Diane"];
        [countedSet addObject:@"Diane"];
        [countedSet addObject:@"Diane"];
        [countedSet addObject:@"Diane"];
        [countedSet addObject:@"Diane"];
        [countedSet addObject:@"Diane"];
        [countedSet addObject:@"Diane"];
        [countedSet addObject:@"Diane"];
        [countedSet addObject:@"Diane"];
        [countedSet addObject:@"Diane"];
        NSLog(@"Counts: %@", countedSet);

        NSDictionary *dict = @{@"people": people};

Making custom objects work well with Sets and Dictionaries

In order to efficiently store your own custom objects, you need to implement isEqual: and hash properly.

@interface Person : NSObject

@property (nonatomic, copy) NSString *name;

@end

@implementation Person

- (NSString *)description {
    return [NSString stringWithFormat:@"Person: %@", self.name];
}

- (BOOL)isEqual:(id)object {
    return [object isKindOfClass:[Person class]] && [self.name isEqual:[object name]];
}

- (NSUInteger)hash {
    return [self.name hash];
}

@end

Performance Characteristics

Performance is described with Big O Notation, which is an important metric when comparing algorithms against each other. I recommend reading it over, but here are some basics:

  • O(1) is constant time. It doesn't matter now many items are processed, the time is unaffected
  • O(N) is linear time. Performance degrades linearly with increased items.
  • O(N2) is quadratic time. Performance degrades drastically with more items.

There are a few others to consider. It's easiest to picture these on a graph:

Big O Notation Graph

You can see how awful some algorithms can be as the number of items increase.

  • NSArray is the best choice to use for a list of items if you're going to iterate over them in sequence, or access directly by index. They are also efficient to use as a queue or stack, as adding or removing items from either the beginning or is O(1). Checking to see if an object exists in the array using containsObject: is an O(N) operation, as it may take up to N comparisons to find the match.
  • NSSet is a great choice for checking containsObject: due to efficient hashing algorithms. Adding/removing items is always O(1). In addition, you have fast set arithmetic operations.
  • NSDictionary is a great choice if you have a natural key you can use to access objects. This has no inherent order, but if you know the key you can retrieve any object as O(1).
blog comments powered by Disqus