合并两个非常大的文本文件，逐行更新，且不使用内存

Question

假设我有两个文本文件，每个文件大约有200万行（每个文件大小在50到80MB之间）。这两个文件的结构是一样的：

Column1 Column2 Column3
...

第一列是固定不变的，第二列：相同的值可能在两个文件中都存在，但顺序不一定相同，第三列是一个数字，在每个文件中都会不同。

我需要把这两个文件合并成一个文件，依据第二列进行匹配。如果第二列在两个文件中都有，就把两个文件中第三列的值加起来更新到合并后的文件中。

如果文件没有这么大，我可以很简单地用PHP来做，方法是把每个文件的每一行读入数组，然后进行处理，但这样做会很容易让内存超负荷。

有没有办法在不把每一行都加载到内存中的情况下完成这个任务？我主要熟悉PHP，但如果Python、Java或者Shell脚本不太复杂，我也愿意尝试。

Answer 1

让你感到困惑的可能是你在看两个文件。其实没必要这样。用Mark的一个很好的例子来说明：

abc 12 34
abc 56 78
abc 90 12

文件2：

abc 90 87  
abc 12 67  
abc 23 1  

然后

sort file1 file2 > file3

得到的结果是：

abc 12 34
abc 12 67  
abc 23 1
abc 56 78
abc 90 12
abc 90 87  

这是计算机科学101课程的第二周，目的是把它简化到最终的形式。

Answer 2

好的，如果我理解得没错，你会有：

文件1：

abc 12 34
abc 56 78
abc 90 12

文件2：

abc 90 87  <-- common column 2
abc 12 67  <---common column 2
abc 23 1   <-- unique column 2

输出应该是：

abc 12 101
abc 90 99

如果是这样的话，可以试试这个（假设它们是.csv格式的）：

$f1 = fopen('file1.txt', 'rb');
$f2 = fopen('file2.txt', 'rb');
$fout = fopen('outputxt.');

$data = array();
while(1) {
    if (feof($line1) || feof($line2)) {
        break; // quit if we hit the end of either file
    }

    $line1 = fgetcsv($f1);
    if (isset($data[$line1[1]])) {
       // saw the col2 value earlier, so do the math for the output file:
       $col3 = $line1[2] + $data[$line1[1]];
       $output = array($line[0], $line1[1], $col3);
       fputcsv($fout, $output);
       unset($data[$line1[1]]);
    } else {
       $data[$line1[1]] = $line1; // cache the line, if the col2 value wasn't seen already
    }

    $line2 = fgetcsv($f2);
    if (isset($data[$line2[1]])) {
       $col3 = $data[$line2[1]] + $line2[2];
       $newdata = array($line2[0], $line2[1], $col3);
       fputcsv($fout, $newdata);
       unset($data[$line2[1]]); // remove line from cache
    } else {
       $data[$line2[1]] = $line2;
    }
}

fclose($f1);
fclose($f2);
fclose($fout);

这只是我随便想的，没测试过，可能不管用，你自己试试吧，等等……

如果你提前对这两个输入文件进行排序，会简单很多，这样第二列就可以作为排序的关键。这样可以减少缓存的大小，因为你会知道是否已经见过匹配的值，以及什么时候可以清理之前缓存的数据。

Answer 3

我建议使用命令行的 sort(1) 来合并和排序文件。之后，写一个简单的脚本来计算总和就可以了。我不太懂PHP，所以我用Python来举个例子：

sort -k2 <file1> <file2> | python -c "
  import itertools,sys
  allLines = (x.strip().split(' ') for x in sys.stdin)
  groups = itertools.groupby(allLines, lambda x:x[1])
  for k,lines in groups:
      firstLine = iter(g).next()
      print firstLine[0], firstline[1], sum(int(x[2]) for x in lines)
"