I have two sorted files A and B where the size of A is much greater than B, e.g. A is 100GB while B is 50MB. I want to quickly determine if there are any lines in B that are contained in A, stopping once a match is made. I currently have a python script for this but it runs slowly when the process has to be repeated thousands of times for different B's.

  • 1
    Try comm -12 A B | wc -l and see how fast that is (0 = no match, nonzero is matched lines). I don't see a way to get it to stop after one match though.
    – Kevin
    Commented Nov 21, 2011 at 19:37
  • @ Kevin That's a useful command I didn't know about, but it still takes to long. In some cases it takes longer if the match is found at the beginning. Can the output be piped to another command that kills it at the first match?
    – Hooked
    Commented Nov 21, 2011 at 19:51
  • You could try adding |head -n1, not sure if that'll actually stop the comm and return early though. Or, if you're using it interactively you could just watch the raw output and kill it if it prints a line.
    – Kevin
    Commented Nov 21, 2011 at 19:53
  • And if you're using it in a script, you may be able to background the comm and use a fifo and head to kill it for you at the first line.
    – Kevin
    Commented Nov 21, 2011 at 19:57
  • That's interesting Kevin, can you provide an example with fifo and head as answer so I can test it, that makes two new commands for me in one question!
    – Hooked
    Commented Nov 21, 2011 at 20:17

4 Answers 4


Using comm, you can get a script to return at the first match using head and a fifo:

#!/bin/bash -e 

[ -p tmpfifo ] || mkfifo tmpfifo
comm -12 A B | head -n1 >tmpfifo &

# If this wc is zero, no matches.  Otherwise, a match was found. 
# You can use this directly in the script, echo it, 
# change the script exit value, or however else you need to use it.
wc -l tmpfifo 

At the moment, this will continue to execute the comm in the background, I'm having trouble finding the right PID to kill ($! is giving the head and not killing the comm). If you're certain this is the only comm running, you could use killall, but that's potentially dangerous in case others are running.


You can try AWK to parse the files. At first I was thinking to break up the larger file, or store A in mem and run through B comparing each line to the A in mem. However, I think AWK might be what you're looking for.

http://www.linuxjournal.com/article/8913 is a primer

http://forums.devshed.com/unix-help-35/compare-two-files-using-awk-or-sed-425150.html is talking about file compare. I'm not on a linux right now, or I'd try to test it out.

gawk http://www.gnu.org/software/gawk/manual/html_node/index.html


If the files are sorted you may be able to get join(1) or combine(1) to work reasonably efficiently. head -1 on the output will stop at the first line and should kill the rest of the command with a SIGPIPE when it exits.

Additionally, you may be able to cut down the problem size by using uniq(1) on the larger file A. This will boil it down to a set of distinct lines, which can then be compared against your list of B files.

Another possibility would be to adapt your python script to do something like the following.

For each B file:
    Read in each line
    Add the file name to a list of files keyed on a hash of the line 

Loop through the A file:
    Look up each line in the dictionary
    Output the file name when a match is found.

This will use up a large amount of memory if the number of distinct lines in your 'B' files is large, so it may or may not be practical. If you don't mind post-processing to eliminate false positives you could cut memory consumption at this stage by just storing the hash.

A third way would be to load the whole lot into a database and do the join, but that incurs the overhead of importing the data, which may be too great. With appropriate indexes the actual matching query would be quite fast and could check against all B files at once, i.e.

Create table A (
       TextLine varchar (100) -- or whatever length you need

Create table B (
       TextLine varchar (100)
      ,Filename varchar (20)

Alter table B
  add constraint PK_B
      primary key (TextLine, FileName)

select distinct B.FileName
  from A
  join B
    on a.TextLine = B.TextLine
grep -F -x -f B A | head -n 1

I guess this is not a well-known feature of grep, but you can pass multiple patterns through a single file by putting each on its own line. This is mostly useful in combination with -F to look for exact strings (with -E, the effect is the same as multiple patterns separated with |).

I haven't benchmarked this, but I'd expect it to be about as fast as it gets without doing preprocessing on A.

  • 1
    If the OP doesn't want to know which line is present but just that there is one, adding -l should makes grep quit as soon as a match is found without reading the rest of the big file Commented Nov 22, 2011 at 8:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .