Is Cocoa's NSMutableArray sparse?

问题:

If I create an NSMutableArray that might have up to 2^16 elements, but will mostly be empty, will I be wasting space or is NSMutableArray implemented as a sparse array?

回答1:

Elements in an NSArray can't be empty and there's no "default" value. To represent nil, you'd usually use the singleton [NSNull null], which is still a reference to an object so it consumes memory (the pointer). I'd consider using NSDictionary (or NSMutableDictionary) with numeric (NSNumber) keys instead.

回答2:

No neither NSArray nor NSMutableArray are sparse arrays. If you have an array with 5000 entries with everything except 4999 set to [NSNull null] it is still taking the space of 5000 entries.

Similarly, an NSPointerArray will have the space for 5000 entries with all the entries NULL except index 4999.

I developed a sparse array object using an NSMutableDictionary as described by OMZ. With this there is only space for the one entry. This space, however, holds both the index and object, and there is the overhead of converting the index values to NSNumbers. So although they can be used anyplace an NSArray or NSMutableArray can be there would be a performance penalty. This is a classic speed / space tradeoff.

See https://github.com/LavaSlider/DSSparseArray

回答3:

An NSArray object is static (or immutable) in the sense that it must be populated at the moment you create it, either by using -initWithObjects, +arrayWithObjects, or by using the contents of an already existing array with -initWithArray, etc. You cannot add objects later on.

There is a concrete mutable subclass (called NSMutableArray) which allows for adding and removing objects dynamically as needed. However when you initialize it in an empty state (either by -initWithCapacity: or +arrayWithCapacity:) what you specify as the initial length is just a hint (the array is created with enough memory to hold that number of objects), howerver it can be expanded as necessary. So yes, in this case, it'll be a sparse array.

Best,