Take the 2-minute tour ×
Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems.. It's 100% free, no registration required.

I have FILE_A which has over 300K lines and FILE_B which has over 30M lines. I created a bash script that greps each line in FILE_A over in FILE_B and writes the result of the grep to a new file.

This whole process is taking over 5+ hours.

I'm looking for suggestions on whether you see any way of improving the performance of my script.

I'm using grep -F -m 1 as the grep command. FILE_A looks like this:

123456789 
123455321

and FILE_B is like this:

123456789,123456789,730025400149993,
123455321,123455321,730025400126097,

So with bash I have a while loop that picks the next line in FILE_A and greps it over in FILE_B. When the pattern is found in FILE_B i write it to result.txt.

while read -r line; do
   grep -F -m1 $line 30MFile
done < 300KFile

Thanks a lot in advance for your help.

share|improve this question
    
Are you really interested in matches in the third field? –  choroba May 29 '12 at 22:20
add comment

4 Answers

up vote 3 down vote accepted

The key to performance is reading the huge file only once.

You can pass multiple patterns to grep by putting them on separate lines. This is usually done by telling grep to read patterns from a file:

grep -F -f 300KFile 30MFile

This outputs the matches in the order of the large file, and prints lines that match multiple patterns only once. Furthermore, this looks for patterns anywhere in the line; for example, if the pattern file contains 1234, then lines such as 123456,345678,2348962342 and 478912,1211138,1234 will match.

You can restrict to exact column matches by preprocessing the pattern. For example, if the patterns do not contain any special character ()?*+\|[]{}:

<300KFile sed -e 's/^/(^|,)/' -e 's/$/($|,)/' |
grep -E -f - 30MFile

If retaining only the first match for each pattern is important, make a first pass to extract only the relevant lines as above, then do a second pass in awk or perl that tracks patterns that have already been seen.

<300KFile sed -e 's/^/(^|,)/' -e 's/$/($|,)/' |
grep -E -f - 30MFile |
perl -l -F, -ape '
    BEGIN {
        open P, "300KFile" or die;
        %patterns = map {chomp; $_=>1} <P>;
        close P;
    }
    foreach $c (@F) {
        if ($patterns{$c}) {
            print;
            delete $patterns{$c};
        }
    }
'
share|improve this answer
    
when i use grep -F -f 300KFile 30MFile > result.txt it basically recreated the 30MFile in result.txt. Am I doing something wrong? –  marcio_rogerio May 30 '12 at 2:18
    
@marcio_rogerio Do you have an empty line in 300KFile? That would match all lines in 30MFile. –  Gilles May 30 '12 at 8:11
    
right on spot! that fixed it! it ran in less than 30 seconds!!! thank you very much! –  marcio_rogerio May 30 '12 at 12:36
add comment

Can you run the following?

grep -Ff FILE_A FILE_B > FILE_C

Now you can run your script on files A and C only.

Update: Wait... Does it preserve the order?

Another update: Some more processing is needed to keep the order. This gives me the same results as your original script. Tested on 300K lines in FILE_A and only 300K lines in FILE_B, 125 minutes vs. 14 secs.

#! /bin/bash
grep -Ff FILE_A FILE_B > FILE_B_TMP
grep -oFf FILE_A FILE_B_TMP > FILE_A_SHUFF
grep -Ff FILE_A_SHUFF FILE_A > FILE_A_TMP

while read -r line; do
   grep -F -m1 "$line" FILE_B_TMP
done < FILE_A_TMP > result.txt
share|improve this answer
1  
I believe it should preserve the order of file b. –  Kevin May 29 '12 at 23:44
    
when i use grep -F -f 300KFile 30MFile > result.txt it basically recreated the 30MFile in result.txt. Am I doing something wrong? –  marcio_rogerio May 30 '12 at 2:18
    
@marcio_rogerio: It just means almost each line from the 300K file has a match somewhere in the 30M file. In such a case, my script will not help you. Can you give us more information about the data - i.e. is the length of fields constant etc.? –  choroba May 30 '12 at 6:42
add comment

I believe comm can make better performance:

comm -12 300KFile <(sed 's/,.*//' 30MFile)

ps. I'm not sure if string 123123 fromm 300KFile should match to string gdwyedg,123123,hfsjdkfh in 30M file. As in your script it matches, but in my script it doesn't.

share|improve this answer
add comment

I believe the grep based solutions still need to compare each record in FILE_A with each record in FILE_B. Since at least N-1 records in FILE_A will not match a specific record in FILE_B, there's a lot of redundancy in this approach. If, on the other hand, the files were sorted then it would be possible to discard a large number of the tests for each comparison. Hence, something like....

#!/bin/bash

# NB a faster solution would be to sort the smaller file in a seperate process
# you might also want to set a buffer size for large files
sort $1 > /tmp/$$.a
sort $2 > /tmp/$$.b

join -j1 -t',' /tmp/$$.a /tmp/$$.b

rm -f /tmp/$$.?

(not tested)

But note that the order of entries will be changed, this pre-supposes that you want to match on a specific column of data in FILE_B and also the sorting introduces an overhead - but the result should be faster for these file sizes.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.