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" -- 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.
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 - 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|