4

我需要编写一个程序，将两个文件之间的差异写入文件。程序必须遍历一个超过 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 中提高效率有什么建议吗？

提前非常感谢！

4

7 回答 7

9

您可能正在查看列表而不是集合，从而导致 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|)（摊销的，由于Python 的set速度非常快）。内存需求为O(|B|)，但系数显着大于 1。

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

于 2012-05-29T15:07:02.047 回答
4

对每个输入文件进行排序。现在从每个中读取一行。如果一行比较小于另一行，则将其作为差异输出并从该文件中读取下一行。如果两行比较相等，则从两个文件中读取下一行。如果你读到一个文件的末尾，另一个文件中的所有行都是不同的。

这是一个 O(n log n) 算法，而不是您开始使用的 O(n^2) 算法。

于 2012-05-29T15:16:44.330 回答
2

grep如果适合您的需要，您可以通过在找到第一个匹配项时停止脚本来稍微加快脚本速度。

如果您grep支持它，请使用grep -m 1.

您的问题是您生成grep了近 300,000 次，并且每次读取超过 13,000,000 行。

在第一场比赛中停下grep来会有所帮助，但所有这些高管的开销也是一个重要因素。Python 中的实现将消除此问题。

至于选择脚本中的文件，请参阅BashFAQ/003和Parsingls。

于 2012-05-29T17:44:20.383 回答
2

您的实现似乎可以：

grep --fixed-strings --file=file_B file_A > result_file

但是@phihag 和@mark Ronsam 的答案都是更好的解决方案。

此外，如果您希望使用重型武器，您的解决方案非常适合使用 map-reduce 框架，例如 hadoop。

于 2012-05-29T15:22:10.277 回答
2

join 命令也可以执行您想要的操作。join 需要预先对两个文件进行排序。选项 -v 为每个不可配对的行打印一行。

所以你会想要类似的东西

加入 -v 1 sortedfile1 sortedfile2

（您需要根据您的文件格式设置连接选项，请参见连接手册页）

下面的示例使用第二个 resp 连接文件 test1.txt 和 test2.txt。连接的第一个字段。假设文件是​​使用 sort 命令预先排序的。-v 1 选项只输出 test1.txt 无法加入的行。

>猫 test1.txt
一个 1 2
乙 2 3

> 猫 test2.txt
1 个
4×

> 加入 -v 1 -1 2 -2 1 test1.txt test2.txt
2 b 3

> 加入 -v 1 -1 2 -2 1 -o 1.1 1.2 1.3 test1.txt test2.txt
乙 2 3

sort 和 join 都适用于大文件。

于 2012-05-29T16:28:40.903 回答
1

我会考虑 comm 命令。它应该比 grep 更快，因为它可以处理已排序的数据，而 grep 将始终进行线性搜索

comm -2 -3 <(sort file1) <(sort file2)
于 2012-05-29T16:32:53.870 回答
0

您还可以使用 awk：

awk 'NR==FNR { arrA[$0]; next } $0 in arrA' file_A file_B > result

命令行中文件的顺序（... file_A file_B）非常重要。

于 2012-05-29T23:57:06.677 回答