I have a 42M line text file. Th first nine characters of each line are a numeric key. What is the most efficient way to extract only the lines whose key exists in another list of about 1.5M keys? Both the file and the list of keys are sorted.
For your input this would be:
(where M means 10^6)
In case your awk uses hash tables, every key lookup would only cost a constant amount of time.
An example of an efficient awk based solution (using the default field separator):
Since both inputs are sorted you could write a script that would be more efficient (with a runtime scaling linearly with both input file sizes). But it would cost more time programming it.
Or you could use
This should run in time linear to the input size.
Note that this method uses the length of a fixed-length key which begins at the first byte of the record.
Here are the results:
Assuming it's a line based file,
Note: heed the warning about false positives by PeterO in the comments below.
|show 2 more comments|