Home

Choosing the correct Data Structures

Following on from the article I posted up on Big-O Notation, with Objective-C it's important to understand what data structures to choose, in order to code with performance in mind. Among many of the lessons we have to learn, premature optimisation is one trap many programmers fall into:

Optimization can reduce readability and add code that is used only to improve the performance. This may complicate programs or systems, making them harder to maintain and debug. As a result, optimization or performance tuning is often performed at the end of the development stage. "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil"[2] -- Wikipedia

Another trap programmers tend to fall into is having redundant or unnecessary code, which not only makes readability harder but means resource is busy accounting for something that could be broken down better.

The Big-O again

Yes, the dreaded Big-O notation which is an expression of the worst case scenario.

 

Source: http://bigocheatsheet.com/

What Objective-C Data structures to choose from?

There are strengths and weaknesses, positives and caveats to each data structure, and importance on when and where to use it, allows you to enjoy the spoils of a scalable code-set.  Also, don't use mutables unless you need to, and you can also opt to make an immutable copy later on, such as [NSArray copy].

 

Description Faster At/Good Slower At/Bad
NSArray/NSMutableArray  - Ordered sequence - Indexed - Duplicates allowed  - Indexed access (i.e array[2] - Adding or removing at start or end of array - Searching array - Adding/removing at index
NSSet/NSMutableSet  - Unordered sequence - No Duplicates (Hash lookup)  - Add/remove elements - Searching - Good with math tests (i.e intersections)  - Cannot be stored in property list or JSON
NSCountedSet   - Unordered sequence - No Duplicates (Hash lookup)  - Subclass of NSMutableSet so same benefits - Tracks net insertion as a count, for each object - Cannot be stored in property list or JSON
NSDictionary/NSMutableD.  - Unordered sequence - Key/Value paring, unique keys - Hash lookup  - Add/remove elements - Searching - Property List file I/O - Must be NSCopying compliant - Can't mutate a key object
NSOrderedSet/NSMutable.  - Ordered sequence - No Duplicates - Hash lookup  - Cross between NSArray/NSSet - Increased memory usage - Property list support needs extra work
NSIndexedSet/NSMut.  - Collection of unique int values - Reference subset of objects in NSArray  - Avoids memory overhead of array copies - Efficient storage/coalescing.  - Tricky with indexes for mutable arrays