Re: Fast dictionary with integer keys?
Re: Fast dictionary with integer keys?
- Subject: Re: Fast dictionary with integer keys?
- From: Jay Reynolds Freeman <email@hidden>
- Date: Sun, 15 Mar 2009 12:55:45 -0700
> The question is: is there this kind of fast int-keyed dictionary in
> Cocoa or elsewhere? Thanks!
There is a common trick that many of us know, forgive me if you already
do and it does not apply to your case for some reason not evident from
your posting.
If the number of objects in the dictionary is known in advance, and if
the keys have a range which is known in advance and not too large, then
you could do it with a plain-vanilla C++ array. Make an array whose
size
is one plus the difference between the largest and smallest keys and
initialize it with nulls. Add the smallest key value to whatever actual
key you are using whenever you reference the array. Put things in
at their key value, (so modified), and when you go to look for an
object,
first check that the modified key is in range for the array, and then
check that array position for null, before you decide the object is
really there.
It is not hard to arrange to switch to a new, larger array, if you
suddenly find yourself dealing with a new object whose key is outside
the assumed range.
This approach is wasteful of memory if keys are scarce in the allowed
range, but it is quite fast.
-- Jay Reynolds Freeman
---------------------
email@hidden
http://web.mac.com/jay_reynolds_freeman (personal web site)
_______________________________________________
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