linux - 在 Bash 中从另一个较大文件中查找文件行的最快方法

Question

我有两个文件，file1.txt和 file2.txt . file1.txt大约有 14K 行和 file2.txt有大约20亿。 file1.txt有一个字段 f1每行同时 file2.txt有 3 个字段，f1通过 f3 ，由 | 分隔.

我想从 file2.txt 中找到所有行哪里f1的 file1.txt匹配 f2的 file2.txt (或者，如果我们不想花费额外的时间来拆分 file2.txt 的值，则可以在该行的任何位置)。

file1.txt(大约 14K 行， 未排序 ):

foo1
foo2
...
bar1
bar2
...

file2.txt(大约 20 亿行， 未排序 ):

date1|foo1|number1
date2|foo2|number2
...
date1|bar1|number1
date2|bar2|number2
...

预期输出:

date1|foo1|number1
date2|foo2|number2
...
date1|bar1|number1
date2|bar2|number2
...

这是我尝试过的，似乎需要几个小时才能运行:

fgrep -F -f file1.txt file2.txt > file.matched

我想知道是否有更好更快的方法来使用常见的 Unix 命令或小脚本来执行此操作。

Answer 1

Perl 解决方案。 [见备注 以下。]

对第一个文件使用哈希。当您逐行阅读大文件时，通过正则表达式提取字段(捕获 || 之间的第一个模式)或 split (获取第二个单词)并打印如果是 exists .它们的速度可能略有不同(计时)。 defined正则表达式中不需要检查，而对于 split使用 // (定义或)短路。

use warnings;
use strict;

# If 'prog smallfile bigfile' is the preferred use
die "Usage: $0 smallfile bigfile\n"  if @ARGV != 2;
my ($smallfile, $bigfile) = @ARGV;

open my $fh, '<', $smallfile or die "Can't open $smallfile: $!";    
my %word = map { chomp; $_ => 1 } <$fh>;

open    $fh, '<', $bigfile or die "Can't open $bigfile: $!";       
while (<$fh>) 
{
    exists $word{ (/\|([^|]+)/)[0] } && print;  

    # Or
    #exists $word{ (split /\|/)[1] // '' } && print;
}
close $fh;

避免 if分支和使用短路更快，但只是很少。在数十亿条线路上，这些调整加起来但又不会太多。逐行读取小文件可能(也可能不会)快一点，而不是像上面那样在列表上下文中读取，但这不应该引起注意。

更新 写信给 STDOUT节省了两个操作，我反复计时，使其比写入文件快一点。这样的用法也和大多数UNIX工具一致，所以我改写成STDOUT .接下来，exists不需要测试，删除它可以节省操作。但是，我始终通过它获得更好的运行时间，同时它也更好地传达了目的。总之我把它留在里面。感谢 ikegami评论。

备注 注释掉的版本是 大约快 50% 比另一个，根据我下面的基准。给出这些是因为它们不同，一个找到第一个匹配项，另一个找到第二个字段。我保持这种方式作为一个更通用的选择，因为这个问题是模棱两可的。

一些比较(基准)[更新写入 STDOUT ，见上面的“更新”]

在 answer by HåkonHægland 中有广泛的分析，计时大多数解决方案的运行时间。这是另一种做法，对上述两个解决方案、OP 自己的答案以及发布的 fgrep 进行基准测试。一，预计会很快并在问题和许多答案中使用。

我按以下方式构建测试数据。对于两个文件，几行长度大致如图所示是由随机单词组成的，以便在第二个字段中匹配。然后我用不匹配的行填充数据样本的“种子”，以便模拟 OP 引用的大小和匹配之间的比率:对于小文件中的 14K 行，大文件中有 1.3M 行，产生 126K 匹配。然后重复写入这些样本以构建完整的数据文件作为 OP，shuffle -ed 每次使用 List::Util .

下面比较的所有运行产生 106_120匹配上述文件大小( diff -ed 用于检查)，因此匹配频率足够接近。
它们通过使用 my $res = timethese(60 ...) 调用完整程序来进行基准测试。 . cmpthese($res)的结果在 v5.16 上是

速率正则表达式 cfor split fgrep
正则表达式 1.05/s -- -23% -35% -44%
cfor 1.36/s 30% -- -16% -28%
split 1.62/s 54% 19% -- -14%
fgrep 1.89/s 80% 39% 17% --

优化 C 程序的事实 fgrep名列前茅并不奇怪。 “正则表达式”落后于“拆分”可能是由于多次启动小匹配引擎的开销。鉴于不断发展的正则表达式引擎优化，这可能因 Perl 版本而异。我包括了@codeforester ("cfor") 的答案，因为它声称是最快的，它的 20%落后于非常相似的“ split ”可能是由于分散的小效率低下(请参阅此答案下方的评论)。†

这并没有太大的不同，虽然硬件和软件以及数据细节肯定存在差异。我在不同的 Perls 和机器上运行它，显着的区别是在某些情况下 fgrep确实快了一个数量级。

OP很慢的体验fgrep令人惊讶。考虑到他们引用的运行时间比上面的慢了一个数量级，我猜想“归咎于”一个旧系统。

尽管这完全是基于 I/O 的，但是将它放在多个内核上还是有并发性的好处，我希望有一个很好的加速，最多可达几个因素。

† 唉，评论被删除了(？)。简而言之:不必要地使用 if 的标量(成本) defined 的分支, 的 printf而不是 print (减缓!)。这些对于 20 亿条线路的效率很重要。