Re: comparing a string with lots of other strings

A good hashing algorithm works a little like you're considering implementing by hand. Perl's hashing system uses "buckets". There may be a few or many items in each bucket. And each bucket itself is found quickly by the hashing algorithm. The result is a very efficient method where the correct bucket is quickly found, and then its contents are scanned for the particular item needed (this is a rough approximation of reality). Anyway, in the end, you get approximately O(1) lookups, which means constant time regardless of number of items in the lookup list.

The moral of this story is to use a hash to hold your 5000 strings. If they won't fit in memory that way, it's time to use a database solution and query for the needed string. But for maximum efficiency, just use the hash.

Dave

Comment on Re: comparing a string with lots of other strings

Replies are listed 'Best First'.
Re^2: comparing a string with lots of other strings by redhotpenguin (Deacon) on Jan 13, 2005 at 01:26 UTC
Or, if the 5,000 strings won't fit in memory use your hash to store the 300 table cells and loop over the 5,000 strings instead.	[reply]
Re^3: comparing a string with lots of other strings by thor (Priest) on Jan 13, 2005 at 02:05 UTC
...or using a tied hash. ;) thor `Feel the white light, the light within Be your own disciple, fan the sparks of will For all of us waiting, your kingdom will come`	[reply]