Re: Searching an NSArray for objects in NSDictionary
Re: Searching an NSArray for objects in NSDictionary
- Subject: Re: Searching an NSArray for objects in NSDictionary
- From: Scott Stevenson <email@hidden>
- Date: Tue, 5 Oct 2004 14:48:56 -0700
On Oct 5, 2004, at 8:31 AM, Nick Zitzmann wrote:
Right now I'm doing a brute force search for the matching
NSDictionary, but I realize this is inefficient and I'm looking for
methods of making this search process more efficient. Normally I would
try sorting the array and doing a binary search, but these
dictionaries have two different & incompatible identifiers. So the
only way I could get a binary search to work would be to create two
similar arrays that are sorted differently, and I'm not sure if that
would be an improvement, since it would take two sort operations and
consume more memory.
I've encountered a lot of stuff like in DataCrux. The area you talk
about is pretty broad, but here are a few ideas. The practicality of
these basically hinges on how frequently the data in the tree changes.
1. Construct a flat dictionary keyed by the memory address of each
object you want to track, with a value describing the object's location
in the tree. Each time an item enters the tree, update the cache.
2. Use class_createInstance() to allocate some additional bytes for
each object that you instantiate. In those extras bytes, store a struct
or object that describes where the object resides in the tree.
3. Get some ideas from this article which describes how hashing is used
to find objects in collections via buckets and such:
http://www.mulle-kybernetik.com/artikel/Optimization/opti-7.html
4. Another more out-there sort of a solution is to create an in-memory
SQLite database that you populate on the fly. The advantage is that you
get to leverage all the optimized searching that sqlite does, but this
may be overkill for your needs. Depending on the contents of the tree,
you may be able to just dump the description of the dictionaries into
the db.
- Scott
--
http://treehouseideas.com/
http://theobroma.treehouseideas.com/ [blog]
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Cocoa-dev mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden