Matching lines from one file to lines in another file

Question

I have a rather big list(1million or so) and another huge list(17gb), I need to match the lines in list1 with the first part of a delimited file 2 as such:

List1:

98433259@34
90345394@43
94335053@23

List2

54353456@35:nancy
98433259@34:jack
94335053@23:james
32409533@86:robert

Output:

98433259@34:jack
94335053@23:james

I have tried grep -Fwf list1 list2 but it is way too slow

Is there any faster way to do this?

Answer 1

Way too slow? What do you expect? You have about one million lines in that file, let's say 12 MB. Now for each line of the other file, you have to scan through that whole file. You may say that the comparison stops after the first byte in nine out of ten cases, but even then you'll have to go on scanning for the next newline, so really for each line of the second file each byte of the first file has to go through the CPU.

Now that second file may have one billion lines. So you need to scan one billion times 12 MB, that's 12 Exabyte! Now, if your desktop machine has 8 MB of L3 cache, those 12 MB do not fit in and have to be fetched from your RAM. Luckily, RAM is fast nowadays, maybe your machine has an effective throughput of 20 GB/s. If I calculate correctly, it takes 600.000 seconds to access 12 Exebyte with 20 GB/s. 10.000 minutes. 167 hours. 7 days. A week.

But this is not slow, it's really fast! It only takes very long as it is a huge task.

If you want it faster, you need a tool designed for that purpose. You will not find that ready to use, so go write it yourself.

How? Use a fast language like C and first organize your file1 data so you don't have to scan through all of it. Put each record in a tree. The root has ten pointers to subtrees, depending on the first digit. Each subtree has another ten pointers to subtrees, unless a null pointer indicates that there are no leaves here.

Now when scanning through file2, you take the first byte and get the pointer according to that digit, in that subtree pick the pointer for the second digit and so on. For eight digits and 64 bit pointers it's in the worst case (match found) only 64 bytes you have to load, plus the bytes stored in that leave with the name. Maybe 80 bytes per line, a billion time multiplies to 80 GB, fetched from memory in 4 seconds. Sounds better, doesn't it?

This is the faster way to do it, but this is not unix related. If you don't know how to write a program like this, StackOverflow should be the place to ask. You can refer to here.