Fastest way to determine if two sorted lists contain unique elements

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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.