Super User is a question and answer site for computer enthusiasts and power users. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose I have two files, File A:


And File B:


The output I'm looking for is:


So, basically, I want to select the rows from File A where the first column matches any value in File B using standard unix commands. A kind of awk {if (file_b contains $1} print $1,$2, but more efficient.

Expected number of rows in File A exceeds 20 million, and File B 1 million. It must run in O(n), so the contains step should probably rely on an Hash Table.

share|improve this question
That's what's known as a database. – Daniel R Hicks Jun 2 '13 at 12:17
@DanielRHicks: You might be right, but OTOH, I don't see the need for every post in stackexchange-related sites be preceded by a full explanation on why the author has restrictions --- no matter how absurd these restrictions may seem. – Hugo S Ferreira Jun 3 '13 at 14:33

There are many ways of doing this. Here are a few but use the Perl one it is orders of magnitude faster. I include the others for the sake of completeness:

  1. Perl and hashes, ridiculously fast

    perl -e 'open(A,"fileB"); while(<A>){chomp; $k{$_}++} 
     while(<>){@a=split(/,/); print if defined $k{$a[0]}}' fileA
  2. gawk and associative arrays, much slower

     gawk '{if(FILENAME==ARGV[1]){array[$1]=1}
      else{if($1 in array){print}}}' fileA fileB
  3. grep, ridiculously slow. You will need to modify your fileB slightly to make the patterns match only on the first line

    sed 's/\(.\)/^\1/' fileB > fileC
    grep -f fileC fileA  

I created a couple of test files and it turns out that the Perl solutions is much faster than the grep:

$ head -2 fileA
$ head -2 fileB
$ wc -l fileA fileB
  1500000 fileA
 20000000 fileB
$ time perl -e 'open(A,"fileB"); while(<A>){chomp; $k{$_}++} 
 while(<>){@a=split(/,/); print if defined $k{$a[0]}}' fileA > /dev/null 

real    0m41.354s
user    0m37.370s
sys     0m3.960s
$ time gawk '{if(FILENAME==ARGV[1]){array[$1]=1}
   else{if($1 in array){print}}}' fileA fileB

real    2m30.963s
user    1m23.857s
sys     0m9.385s
$ time (join -t, <(sort -n fileA) <(sort -n fileB) >/dev/null)

real    8m29.532s
user    13m52.576s
sys     1m22.029s

So, the Perl scriptlet can go through a 20 million line file looking for 1.5 million patterns and finish in ~40 seconds. Not bad. The other two are much slower, gawk took 2.5 minutes and the grep one has been running for more than 15. Perl wins hands down.

share|improve this answer
+1 for open(_A_,"file_B_"). How does split(//) work? I expected something like split(/,/). – mpy Jun 2 '13 at 14:20
@mpy split(//) splits at each character, so a line like abcd becomes an array @a=(a,b,c,d) so $a[0] is the first character. This assumes patterns of one character each as described in the question. – terdon Jun 2 '13 at 14:21

This should do the trick:

join -t, <(sort A) <(sort B)
share|improve this answer
+1 for join, good idea. I am afraid it will be very slow though since it has to sort both files first. – terdon Jun 2 '13 at 15:04
Sorting a 20 million lines file takes about 30s on my machine. – cYrus Jun 2 '13 at 15:11
See my updated answer, join and sort takes about 8min on my test files, compared to 40sec for Perl. Yes, each sort will take about half a minute but that adds at least a minute to the run time. Also why are you sorting numerically? That actually adds a few seconds to the run time. – terdon Jun 2 '13 at 15:19
Ahhh, yes, because I was testing with numbers... – cYrus Jun 2 '13 at 15:27

i still dont understand what you are trying to do .... you already have something up in a awk stmt.

grep is basic and is based on a preety efficient and fast algorithm based on index of possible matches .... awk does individual comparison and checks so this should be fast .... wrt awk , here

 for pat in `cat zfile2` ; do  grep -i "$pat," zfile1 ; done; 

this works fine ...

   $ for pat in `cat zfile2` ; do  grep -i "$pat," zfile1 ; done;

does this help ?

share|improve this answer
The problem with this approach is that it will have to grep through fileA N times for N lines in fileB. That will be slow... – terdon Jun 2 '13 at 14:14
yeah , that does add up to O(n2) ... he wants something like O(n) , maybe a O(nlogn) .... but what i didnt understand here is that these days the utilities are quite efficient and are evenly matched in most scenarios ..... i doubt there would be much off a difference in the run time if he did use what he already has in awk ..... You can never be sure unless you analyse the algorithm thats used in the code – n13 Jun 2 '13 at 14:22
hash in perl should be fast though +1 for that @terdon – n13 Jun 2 '13 at 14:24
Also this will retuen all lines that contain the patterns of fileA, not just those lines that start with the pattern. – terdon Jun 2 '13 at 15:06
he he ..... nope it wont , tested for that !! there is nothing in the output that like : c,fabcde – n13 Jun 2 '13 at 15:10

You must log in to answer this question.

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