根据存储在另一个文件中的行号从大文件中提取行的快速方法

Question

我有一个包含 800 亿行的大文件。现在我想提取几行（大约 10000 行），我知道行号，处理它的最快方法是什么。

是否可以使用包含行号的另一个文件来提取这些行？行号文件中的行号并不总是连续的。

比如原文件是：

0.1
0.2
0.3
0.4
...

行号文件：

1
3
4

输出：

0.1
0.3
0.4

Answer 1

这里有一种替代方法和一些基准测试，并在 Weijun Zhou 的回答中进行了补充。

join

假设您有一个data要从中提取行的文件和一个列出line_numbers要提取的行数的文件，如果输出的排序顺序不重要，您可以使用：

join <(sort padded_line_numbers) <(nl -w 12 -n rz data) | cut -d ' ' -f 2-

这将对文件的行进行编号data，将其与padded_line_numbers第一个字段（默认）上的文件连接起来，并打印出公共行（不包括被切除的连接字段本身）。

join需要输入文件按字母顺序排序。上述padded_line_numbers文件必须通过左填充line_numbers文件的每一行来准备。例如：

while read rownum; do
    printf '%.12d\n' "$rownum"
done <line_numbers >padded_line_numbers

选项-w 12 -n rz和参数指示nl输出带前导零的 12 位长数字。

如果输出的排序顺序必须与line_numbers文件的排序顺序匹配，您可以使用：

join -1 2 -2 1 <(nl padded_line_numbers | sort -k 2,2) \
    <(nl -w 12 -n rz data) |
    sort -k 2,2n |
    cut -d ' ' -f 3-

我们对padded_line_numbers文件进行编号，按第二个字段的字母顺序对结果进行排序，将其与编号的data文件连接起来，并按 的原始排序顺序对结果进行数字排序padded_line_numbers。

为了方便起见，这里使用过程替换。如果您不能或不想依赖它，并且您可能不愿意浪费创建常规文件来保存中间结果所需的存储空间，则可以利用命名管道：

mkfifo padded_line_numbers
mkfifo numbered_data

while read rownum; do
    printf '%.12d\n' "$rownum"
done <line_numbers | nl | sort -k 2,2 >padded_line_numbers &

nl -w 12 -n rz data >numbered_data &

join -1 2 -2 1 padded_line_numbers numbered_data | sort -k 2,2n | cut -d ' ' -f 3-

标杆管理

由于您问题的特殊性是文件中的行数data，因此我认为使用相当数量的数据测试替代方法可能很有用。

在我的测试中，我使用了 32 亿行的数据文件。每行只是来自 的 2 个字节的垃圾openssl enc，使用 和 进行十六进制编码od -An -tx1 -w2，并使用 删除空格tr -d ' '：

$ head -n 3 data
c15d
061d
5787

$ wc -l data
3221254963 data

该line_numbers文件是通过使用shufGNU Coreutils 随机选择 1 到 3,221,254,963 之间的 10,000 个数字（不重复）创建的：

shuf -i 1-"$(wc -l <data)" -n 10000 >line_numbers

测试环境是一台笔记本电脑，配备 i7-2670QM Intel 四核处理器、16 GiB 内存、SSD 存储、GNU/Linux、bash5.0 和 GNU 工具。
我测量的唯一维度是通过timeshell 内置函数执行的时间。

这里我考虑的是：

• 解决方案sed来自周伟军的回答。
• Micha 的回答awk给出了解决方案。
• 解决方案perl来自wurtel 的回答。
• 解决方法join如上。

perl似乎是最快的：

$ time perl_script line_numbers data | wc -l
10000

real    14m51.597s
user    14m41.878s
sys     0m9.299s

awk的性能看起来相当：

$ time awk 'FNR==NR { seen[$0]++ }; FNR!=NR && FNR in seen' line_numbers data | wc -l
10000

real    29m3.808s
user    28m52.616s
sys     0m10.709s

join似乎也具有可比性：

$ time join <(sort padded_line_numbers) <(nl -w 12 -n rz data) | wc -l
10000

real    28m24.053s
user    27m52.857s
sys     0m28.958s

请注意，上面提到的排序版本与此版本相比几乎没有性能损失。

最后，sed似乎明显慢了：我在大约九小时后杀死了它：

$ time sed -nf <(sed 's/$/p/' line_numbers) data | wc -l
^C

real    551m12.747s
user    550m53.390s
sys     0m15.624s

Answer 2

我会为此使用 perl 脚本。我想出了这个：

#!/usr/bin/perl

# usage: thisscript linenumberslist.txt contentsfile

unless (open(IN, $ARGV[0])) {
        die "Can't open list of line numbers file '$ARGV[0]'\n";
}
my %linenumbers = ();
while (<IN>) {
        chomp;
        $linenumbers{$_} = 1;
}

unless (open(IN, $ARGV[1])) {
        die "Can't open contents file '$ARGV[1]'\n";
}
$. = 0;
while (<IN>) {
        print if defined $linenumbers{$.};
}

exit;

首先将我们感兴趣的行号列表读入关联数组，其中行号是键。chomp删除行尾的换行符，$_即行本身。

接下来打开数据文件，当行号是行号数组中的现有键时，则打印该行。

这$.是 perl 的行号计数器，每读取一行就会递增。由于这是跨文件计数的，因此在读取数据文件的任何行之前我将其重置为零。

这可能可以用“perl”风格写得更多，但我更喜欢让它更具可读性。

如果您要提取的行列表非常大，这可能不是最有效的方法，但我发现 perl 在这些事情上通常非常高效。

如果您需要按照列出的顺序（即不按顺序）提取行，那么它会变得更加复杂......