Take the 2-minute tour ×
Super User is a question and answer site for computer enthusiasts and power users. It's 100% free, no registration required.

Suppose I have two files, File A:

a,abcdef
b,bcdefa
c,cdefab
a,defabc
b,efabcd
c,fabcde

And File B:

a
b

The output I'm looking for is:

a,abcdef
b,bcdefa
a,defabc
b,efabcd

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
2  
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
add comment

3 Answers

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
GO:0032513_GO:0050129
GO:0050129_GO:0051712
$ head -2 fileB
GO:0032513_GO:0050129
GO:0050129_GO:0051712
$ 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
1  
@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
add comment

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
add comment

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;
   a,abcdef
   a,defabc
   b,bcdefa
   b,efabcd

does this help ?

share|improve this answer
1  
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 –  kabirz.domain Jun 2 '13 at 14:22
    
hash in perl should be fast though +1 for that @terdon –  kabirz.domain 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 –  kabirz.domain Jun 2 '13 at 15:10
show 1 more 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.