5

First off, I've seen this, but it doesn't quite seem to suit my needs.

I've got a situation where I need a sparse array. Some situations where I could have, say 3000 potential entries with only 20 allocated, other situations where I could have most or all of the 3000 allocated. Using an NSMutableDictionary (with NSString representations of the integer index values) would appear to work well for the first case, but would seemingly be inefficient for the second, both in storage and lookup speed. Using an NSMutableArray with NSNull objects for the empty entries would work fairly well for the second case, but it seems a bit wasteful (and it could produce an annoying delay at the UI) to insert most of 3000 NSNull entries for the first case.

The referenced article mentions using an NSMapTable, since it supposedly allows integer keys, but apparently that class is not available on iPhone (and I'm not sure I like having an object that doesn't retain, either).

So, is there another option?

Added 9/22

I've been looking at a custom class that embeds an NSMutableSet, with set entries consisting of a custom class with integer (ie, element#) and element pointer, and written to mimic an NSMutableArray in terms of adds/updates/finds (but not inserts/removals). This seems to be the most reasonable approach.

Improve this question
3
  • Performance-wise, how is NSMutableSet with a custom class any different from using a plain old NSMutableDictionary with NSNumber as the key? Commented Sep 22, 2011 at 21:27
  • Would probably be about the same, if wrappered with a custom class in the same way. The NSMutableSet approach gave me some extra "advertising space" that allowed the implementation of a LRU accounting mechanism that would have required more objects with a dictionary, though that was not a part of the original "problem description". Commented Sep 22, 2011 at 21:32
  • Who says NSMutableDictionary needs strings as keys? NSNumber works just fine, and is especially efficient on 64 bit systems. Commented May 26, 2014 at 21:55

4 Answers 4

Reset to default
1

A NSMutableDictionary probably will not be slow, dictionaries generally use hashing and are rather fast, bench mark.

Another option is a C array of pointers. Allocation a large array only allocates virtual memory until the real memory is accessed (cure calloc, not malloc, memset). The downside is that memory is allocated in 4KB pages which can be wasteful for small numbers of entries, for large numbers of entries many may fall in the same page.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

What about CFDictionary (or actually CFMutableDictionary)? In the documentation, it says that you can use any C data type as a key, so perhaps that would be closer to what you need?

Improve this answer

2 Comments

From Apple docs: The key for the value to add to the dictionary—a CFType object or a pointer value. The key is retained by the dictionary using the retain callback provided when the dictionary was created, so must be of the type expected by the callback.
Yes it does say that too, in the documentation for CFDictionaryAddValue. I was looking at the Overview section for CFDictionary where it says "Keys for a CFDictionary may be of any C type, however note that if you want to convert a CFPropertyList to XML, any dictionary’s keys must be CFString objects."
0

I've got the custom class going and it works pretty well so far. It's 322 lines of code in the h+m files, including the inner class stuff, a lot of blank lines, comments, description formatter (currently giving me more trouble than anything else) and some LRU management code unrelated to the basic concept. Performance-wise it seems to be working faster than another scheme I had that only allowed "sparseness" on the tail end, presumably because I was able to eliminate a lot of special-case logic.

One nice thing about the approach was that I could make much of the API identical to NSMutableArray, so I only needed to change maybe 25% of the lines that somehow reference the class.

Improve this answer

2 Comments

I also needed a sparse array and have put mine on git hub. If you need a sparse array feel free to grab github.com/LavaSlider/DSSparseArray
(For those wondering why I answered my own question with a not-particularly-satisfying answer, it's because of SO's stupid rules about accepting questions. In order to keep my %accepted rate up I have to provide my own answers to "difficult" questions and accept them. I didn't make the rules.)
0

I also needed a sparse array and have put mine on git hub. If you need a sparse array feel free to grab https://github.com/LavaSlider/DSSparseArray

Improve this answer

2 Comments

how to iterate through DSMutableSparseArray ?
The same ways as with DSSparseArray.... get the indices and step through them or use the block access methods.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.