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

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

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

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

例如,原始文件是:

0.1
0.2
0.3
0.4
...

行号文件:

1
3
4

输出:

0.1
0.3
0.4

答案1

这里有一种替代方法和一些基准测试,除此之外在周伟军的回答中

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 内置函数执行的时间。

这里我考虑的是:

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

答案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 在这些事情上通常非常高效。

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

答案3

一个内衬,使用sed

sed -nf <(sed 's/$/p/' linenumberfile) contentfile

要保留原始顺序linenumberfile,您可以这样做

sed -nf <(sed 's/$/p/' linenumberfile) contentfile | paste <(nl linenumberfile | sort -n -k 2,2) - | sort -n -k 1,1 | cut -f 3-

解释:

sed 's/$/p/' linenumberfile

生成一个sed打印指定行的脚本。然后将脚本输入另一个脚本sed(以-n抑制模式空间的默认打印)以进行实际打印。由于sed逐行处理内容文件,因此输出的顺序将与内容文件中的顺序相同。请注意,这是一个一次通过过程所以我希望速度是可以接受的。

为了加速这一过程,可以更改p并在生成的脚本末尾{p;b}添加。qsed

要保留行号文件中的行顺序,nl用于将“行号”添加到行号文件中。所以一个行号文件

4
5
2

会成为

1 4
2 5
3 2

第一列记录行号文件中的原始顺序。

然后将带有“行号”的文件sorted 和pasted 输出到sed, 以使

3 2    content_of_line2
1 4    content_of_line4
2 5    content_of_line5

然后sort以第一列为key进行ed,最终得到

1 4    content_of_line4
2 5    content_of_line5
3 2    content_of_line2

最后,cut用于删除 2 个额外的列。

标杆管理

它似乎sed最适合几行,但这perl是问题中指定的 10000 行的方法。

$ cat /proc/cpuinfo | grep -A 4 -m 1 processor
processor   : 0
vendor_id   : GenuineIntel
cpu family  : 6
model       : 60
model name  : Intel(R) Core(TM) i5-4590 CPU @ 3.30GHz

$ wc -l linenumber
10 linenumber

$ wc -l content
8982457 content

$ file content
content: ASCII text

$ time bash -c "sed -nf <(sed 's/$/p/' linenumber) content > /dev/null"    
real    0m0.791s
user    0m0.661s
sys     0m0.133s

$ time bash -c "awk 'FNR==NR { seen[$0]++ }; FNR!=NR && FNR in seen' linenumber content > /dev/null"
real    0m3.061s
user    0m2.908s
sys     0m0.152s

$ time bash -c "./ln.pl linenumber content > /dev/null"
real    0m1.706s
user    0m1.582s
sys     0m0.124s

$ ./genlinenumber.py 100 > linenumber
$ wc -l linenumber
100 linenumber

$ time bash -c "sed -nf <(sed 's/$/p/' linenumber) content > /dev/null"
real    0m3.326s
user    0m3.164s
sys     0m0.164s

$ time bash -c "awk 'FNR==NR { seen[$0]++ }; FNR!=NR && FNR in seen' linenumber content > /dev/null"
real    0m3.055s
user    0m2.890s
sys     0m0.164s

$ time bash -c "./ln.pl linenumber content > /dev/null"
real    0m1.769s
user    0m1.604s
sys     0m0.165s

如果需要保留行的顺序,则|仍然可以使用第一行之后的命令,因为时间可以忽略不计。

$ ./genlinenumber.py 10000 > linenumber
$ wc -l linenumber
10000 linenumber

$ time bash -c "./ln.pl linenumber content > extract"
real    0m1.933s
user    0m1.791s
sys     0m0.141s

$ time bash -c "paste <(nl linenumber | sort -n -k 2,2) extract | sort -n -k 1,1 | cut -f 3- > /dev/null"
real    0m0.018s
user    0m0.012s
sys     0m0.005s

答案4

micha@linux-micha: /tmp
$ cat numbers.txt
1
2
4
5

micha@linux-micha: /tmp
$ cat sentences.txt
alpha
bravo
charlie
delta
echo
foxtrott

micha@linux-micha: /tmp
$ awk 'FNR==NR { seen[$0]++ }; FNR!=NR && FNR in seen' numbers.txt sentences.txt
alpha
bravo
delta
echo

相关内容