比较两个大文件

Question

我需要编写一个程序,将两个文件之间的差异写入文件.程序必须循环遍历超过13.464.448行的600 MB文件,检查grep是否在另一个文件上返回true然后将结果写入另一个文件.我写了一个大约1.000.000记录的快速测试,花了一个多小时,所以我猜这种方法可能需要9个多小时.

您对如何加快速度有任何建议吗？我应该使用的任何特定语言？我打算用bash或python来做这件事.

非常感谢提前.

[编辑1]:对不起,当我说两个文件之间的差异时,我并不意味着差异.结果文件采用不同的格式.

逻辑有点像这样:

文件A有297.599行文件B有超过1300万行

我选择从文件A读取的当前行,在文件B上grep它,如果文件B中存在该行,我将把它写入结果文件.顺便说一句,文件A和文件B具有不同的格式.结果文件的格式为文件A.

[编辑2]:我被要求在工作中理想地创建一个bash解决方案,这样我们就不必在必须运行的所有机器上安装python.

这是我的实施方法:

#!/bin/bash

LAST_TTP=`ls -ltr TTP_*.txt | tail -1 | awk '{ print $9 }'`
LAST_EXP=`ls -ltr *.SSMT | tail -1 | awk '{ print $9 }'`

while read -r line; do
   MATCH="$(grep $line $LAST_EXP)"
   echo "line: $line, match: $MATCH"

   # if not empty
   if [ ! -z "$MATCH" ]
   then
      echo $MATCH >> result
   fi

done < $LAST_TTP

这种bash方法需要10个多小时才能完成.您对如何在bash中提高效率有任何建议吗？

非常感谢提前!

Answer 1

您可能正在查找列表而不是集合,从而导致O(n²)性能.尝试:

with open('b') as b:
  blines = set(b)
with open('a') as a:
  with open('result', 'w') as result:
    for line in a:
      if line not in blines:
        result.write(line)

假设一致的长(而不是过长的行),这个实现的性能是O(|A| + |B|)(摊销,因为Pyton set非常快).内存需求在O(|B|),但有一个显着大于1的因素.

如果输出中的行顺序无关紧要,您还可以对两个文件进行排序,然后逐行进行比较.这将具有大约的性能O(|A| log |A| + B log |B|).内存需求将是O(|A|+|B|)或更准确地说是|A|+ |B|.