Re: Best Way To Lookup From a Huge Table
Re: Best Way To Lookup From a Huge Table
- Subject: Re: Best Way To Lookup From a Huge Table
- From: Scott Ribe <email@hidden>
- Date: Tue, 18 Mar 2008 18:22:18 -0600
- Thread-topic: Best Way To Lookup From a Huge Table
> 1) If I can load all the data into memory, using say a hash table,
> then the initial load time will be somewhat significant but the
> lookups will be near instantaneous.
Really shouldn't be too hard to load the OP's 41,000 very short strings
nearly instantaneously.
> I had a situation where I had about 170,000 unique strings that
> mapped to 170,000 other strings.
>
> My first implementation used Objective-C++ and a C++ STL map to do
> the lookup (solution 1). Depending on the machine, it took on the
> order of 2 to 7 seconds of time during the app launch to load the C++
> map.
Seems to me that would be either long strings, or inefficient use of STL.
Did you try to profile it and optimize it? For instance, if you used map<
string, string > the insertions would likely take up all the time in copying
strings, and map< string *, string * > would be an easy optimization. Not
quite so easy (but still not hard) is reading the whole file in one block,
replacing field/record delimiters with null chars, and initializing const
char * pointers into the single block, so you never even copy the strings
once, then you use map< char *, char *, comparefunc >.
Of course OP's "index" strings can all be represented as integers, which
would make the comparisons for inserts faster than string comparisons. In
fact, for 5-digit zip codes it's perfectly possible to just allocate an
array large enough to hold entries for all possible integers in the range 0
through 99,999. No comparisons while reading and building the array, and
just O(1) time to "find" an entry. Of course for 9-digit zip codes, this
wouldn't be such a great idea ;-)
--
Scott Ribe
email@hidden
http://www.killerbytes.com/
(303) 722-0567 voice
_______________________________________________
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