Re: Fast dictionary with integer keys?
Re: Fast dictionary with integer keys?
- Subject: Re: Fast dictionary with integer keys?
- From: Joseph Kelly <email@hidden>
- Date: Sun, 15 Mar 2009 17:35:02 -0700
On Mar 15, 2009, at 12:18 PM, Tommy Nordgren wrote:
You can write your implementation file in Objective C++ , and use
std::map<int,id>
That was my first case, but I just wanted to make sure: I've run some
tests, and std::map outperforms NSMutableDictionary as described,
until around n = 10^6, at which point, NSMutableDictionary becomes
much faster, both at inserting in-order, and looking up randomly. I
didn't test for random insertion, however.
Here's an interesting article about CFArray/NSArray behavior
characteristics -- as compared to a straight C array and an std::vector:
http://ridiculousfish.com/blog/archives/2005/12/23/array/
I think it's been mentioned already that if you've got a finite set of
keys, that if you use a fixed array with a hash function (if it's a
small and finite pre-determined set of keys, you could just do a 1:1
hash -- i.e. just index into the array using the key), that you'll get
best case O(1) inserts and lookups.
Fun stuff to think about.
Joe K.
_______________________________________________
Cocoa-dev mailing list (email@hidden)
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:
This email sent to email@hidden