CODEWITHSUNDEEP
csearch
J.Zil
J.Zil

Reputation: 2449

Searching a file and returning value - Super Fast

I have a set of data which has a name, some sub values and then a associative numeric value. For example:

James Value1 Value2 "1.232323/1.232334"
Jim   Value1 Value2 "1.245454/1.232999"
Dave  Value1 Value2 "1.267623/1.277777"

There will be around 100,000 entries like this stored in either a file or database. I would like to know, what is the quickest way of being able to return the results which match a search, along with their associated numeric value.

For example, a query of "J" would return both James and Jim results which the numeric values in the last column.

I've heard people mention binary tree searching, dictionary searching, indexed searching. I have no idea which is a good route to peruse.

Upvotes: 0

Views: 157

Answers (1)

Eric Postpischil
Eric Postpischil

Reputation: 222362

This is a poorly characterized problem. As with many optimization problems, there are trade-offs in resources. If you truly want the fastest response possible, then a likely approach is to compile all possible searches into a table of prepared results, so that, given a search key, you can look the search key up in the table and return the result.

Assuming your character set is limited to A-Z and a-z, a table with an entry for each search key from 0 to 4 characters will use a modest amount of memory by today’s standards. Each table entry merely needs to have two values in it: The start and end positions in a list of the numeric values. (Compile the list in this way: Sort the records by the name field. Extract just the numeric values from the records, maintaining the order, putting them in a list. Any search key must return a sublist of contiguous records from that list. This is because the search is for a prefix string of the name field, so any records that match the search key are adjacent, when sorted by the name field.)

Thus, to create a table to look up any key of 0 to 4 characters, you need fewer than 534 entries in a table of pairs, where each member of the pair contains a record number (32 bits or fewer). So 8•534 = 60.2 MiB suffices. (53 is because you have 52 characters plus one sentinel character to mark the end of the key. Alternate encodings could reduce this some.)

To support keys of more than 4 characters, you need to extend this. With typical data, 4 characters will have narrowed down the search greatly, so you can take the set of records indicated by the first 4 characters and prune it to get the final results. If the data has pathological cases where 4 characters does not reduce the search much, you can embellish this technique.

So, is that really what you want to do, make the speed as fast as possible, regardless of other resources (including engineering time) consumed? If not, what are your actual goals?

Upvotes: 1

Related Questions