Re: Fast dictionary with integer keys?
Re: Fast dictionary with integer keys?
- Subject: Re: Fast dictionary with integer keys?
- From: Tommy Nordgren <email@hidden>
- Date: Mon, 16 Mar 2009 02:45:28 +0100
On Mar 16, 2009, at 1:35 AM, Joseph Kelly wrote:
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>
You can also use std::hashmap<int,id> . It uses a hash table instead
of a balanced binary tree.
This is however dependent of a good hash function.
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
---------------------------------
How many National Democrats does it take to change a light bulb?
108: 8 who smashes the rest of the light bulbs, and 100 to blame a
zionist world conspiracy for the darkness
--------------------------
Tommy Nordgren
email@hidden
_______________________________________________
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