Re: Best way to look-up a string amongst 100 million of its peers

The simplest thing (assuming you are talking about ascii words) is to break up the 100 million list, into 24 (or whatever is suitable for size) smaller lists that all begin with the same 1 (or 2) letters. This would not take much more disk space, but searching them would be simpler and faster. All you need to do is regex the word for the first 1 (or 2) letters, then go loop thru the file containing those words. Of course, alot of speed improvements can be made by combining things like "Q,W,X,Y,Z" into one file, and breaking things like "C" into "CA..CL..CR" etc.; depending on the initial letter frequency of your 100 million list.

I'm not really a human, but I play one on earth. Cogito ergo sum a bum

Comment on Re: Best way to look-up a string amongst 100 million of its peers

Replies are listed 'Best First'.
Re^2: Best way to look-up a string amongst 100 million of its peers by samtregar (Abbot) on Mar 26, 2008 at 17:33 UTC
The simplest thing is to reinvent b-trees one step at a time? -sam	[reply]
Re^3: Best way to look-up a string amongst 100 million of its peers by zentara (Cardinal) on Mar 26, 2008 at 18:36 UTC
How is a b-tree simpler than breaking into smaller sorted files? I don't even know what a b-tree is.... they run me out of college before we got to that. :-) But I do know how to sort and split files. I'm not really a human, but I play one on earth. Cogito ergo sum a bum	[reply]
Re^4: Best way to look-up a string amongst 100 million of its peers by BrowserUk (Patriarch) on Mar 26, 2008 at 19:12 UTC
Pre-bucketing and splitting the data can have several advantages over an all-in-one-btree file. Notably, inserts can be faster because there is no rebalancing to be done. And if you split far enough to make the resultant files small, then there is no need to sort the individual files as a linear search is fast enough. In effect, using the first n chars to index into the appropriate bucket and then linear searching is exactly equivalent to hashing. Ie. You described the same process perl uses for its internal hashes and that CDB uses. Except the hashing part of the process is faster. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. "Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."	[reply]