Fastest & most efficient way to remove lines containing strings (strings listed in another text file)

Question

I was wondering if fgrep is the fastest and most efficient way to remove lines from a file (file1) that contain a string found in another file (file2).

I have found the function fgrep that should do this as follows:

  fgrep -v -f file1  file2  > file_with_lines_containing_search_strings_removed

I don't know if this will work well with very large files.

I have two files with 100,000s of lines and I want to use the fastest method possible.

Thanks.

Happy July 4th to all those funny looking Americans.

Answer 1

If you want "lines that contain a string found in another file" (and not "lines that contain a string that match a regExp in another file"), try:

grep -vFf file1 file2 > file3

"grep -F" is not looking for regexp match but simple string match (much faster)

or even better

grep -vwFf file1 file2                 #respect word boundary

Just a quick time comparation test:

1) build a 100 000 random lines example file2

seq 1000000 | shuf -n 100000 > file2

2) build a 10 000 random lines example file1 (strings to remove)

 seq 1000000 | shuf -n 10000 > file1

31) Using grep -F --- time grep -vwFf file1 file2 > file31

real    0m0.111s
user    0m0.100s
sys 0m0.008s

32) Without -F --- time grep -vwf file1 file2 > file32

... hours!

if file1 has just 300 lines --    0.327s          very fast
....              600 lines --    8.326s
....              900 lines --   35.334s
....             1200 lines -- 1m31.433s      (quadratic with file1 len?)

....            10000 lines -- it is still calculating (several hours?)
UPDATED                     1h03m53.983s

Conclusion of the test:

• grep -vFf file1 file2is much faster than grep -vf

• grep -vFf file1 file2 has no problems with big file1 files

• grep -vf file1 file2 is evilly affected with the increase of the size of file1 file (this is only visible for sizes > 500 lines or > 4kbytes)

Answer 2

Yes it will be fine. The worst case is when the file with the strings to exclude is equal to the size of the file being processed, and of a size that doesn't fit into memory. If you have that case then split the exclusion file into chunks and run multiple passes.