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 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.

share|improve this question
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 Nov 21 '11 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 Nov 21 '11 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 Nov 21 '11 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 Nov 21 '11 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 Nov 21 '11 at 20:17
show 1 more comment

4 Answers

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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
share|improve this answer
add comment
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.

share|improve this answer
    
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 –  AProgrammer Nov 22 '11 at 8:54
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.