Paul Bruneau <mailto:paul_brun...@special-lite.com> wrote
(Thursday, January 7, 2010 11:00 AM -0500):
To help make this thread more Cocoa-y, I would like to ask: Do the NSSet and
NSArray methods like -containsObject perform in a fashion comparable to a
home-rolled binary search? I greatly prefer to use the Cocoa stuff rather than
try to remember/learn how to properly code such things.
NSSet (and NSDictionary) use hash tables to organize and look up
their objects/keys. Look up and insertion times are nearly
linear--assuming a well distributed hash function--regardless of
collection size.
NSArray does not impose an order on its contents. While arrays
can be sorted--and as others have pointed out, there are binary
search functions in Core Foundation--NSArray never assumes that
its contents are ordered and searches are always preformed using
a sequential, brute force, comparison of objects.
It's easy to demonstrate all of this by setting a breakpoint in
the -hash and -isEqual: methods of the objects added to a collection.
For ZIP code membership, an NSIndexSet makes a lot more sense.
--
James Bucanek
_______________________________________________
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com
This email sent to arch...@mail-archive.com
