☰

按行号过滤文件

tag-icon • tag-icon text-processing filter high-performance
按行号过滤文件

给定一个每行一个非负整数的文件 L 和一个文本文件 F，有什么快速方法可以只保留 F 中那些行号出现在文件 L 中的行？

例子：

$ cat L.txt
1
3

$ cat F.txt
Hello World
Hallo Welt
Hola mundo

$ command-in-question -x L.txt F.txt
Hello World
Hola mundo

我正在寻找一个可以处理具有 5 亿或更多条目的文件 L 的命令；文件 L 按数字排序。

注意：我正在实现 a 的一半command-in-question，但我只是想知道是否也可以在这里使用一些 Unix 工具。

更新：感谢所有的答案，我今天学到了很多！我想接受多个答案，但这是不可能的。

我从当前答案中采取了最快的解决方案，并将它们放入一个独立的工具中：过滤线。

答案1

grep -n | sort | sed | cut

(   export LC_ALL=C
    grep -n ''   | sort -t:  -nmk1,1 ./L - |
    sed /:/d\;n  | cut  -sd: -f2-
)   <./F

那应该很快就能起作用（下面包括一些定时测试）输入任意大小。以下是一些注意事项：

  • export LC_ALL=C
    • 因为以下操作的目的是让整个文件./F与其./Llineno 的文件内联堆叠，所以我们真正需要担心的唯一字符是 ASCII[0-9]数字和:冒号。
    • 因此，与涉及 UTF-8 的情况相比，在 128 个可能的集合中查找这 11 个字符更容易。
  • grep -n ''
    • 这将插入字符串LINENO:进入 stdin - 或 中每一行的头部<./F。
  • sort -t: -nmk1,1 ./L -
    • sort根本忽略对其输入文件进行排序，而是（正确）假设它们已预先排序并按排序顺序-m对它们进行 erge -numerically，基本上忽略任何可能-k1,1出现的-t:冒号字符之外的任何内容。
    • 虽然这可能需要一些临时空间来完成（取决于某些序列可能发生的距离有多远），与正确的排序相比，它不需要太多，而且会非常快，因为它涉及零回溯。
    • sort将输出一个流，其中任何 lineno./L都将立即位于 中的相应行之前./F。./L的线路总是排在第一位，因为它们较短。
  • sed /:/d\;n
    • 如果当前行与冒号匹配，/:/则将d其从输出中删除。否则，自动打印当前行和n下一行。
    • 所以将输出sed修剪为sort仅有的与冒号和下一行不匹配的连续行对 - 或者，仅与./L下一行匹配。
  • cut -sd: -f2-
    • cut -s从输出中抑制那些不包含至少一个其-d:分隔符字符串的输入行 - 因此./L的行被完全修剪。
    • 对于那些这样做的行，它们的第一个:冒号分隔的-f字段消失了- 所有插入的 linenocut也消失了。grep

小输入测试

seq 5 | sed -ne'2,3!w /tmp/L
        s/.*/a-z &\& 0-9/p' >/tmp/F

...生成 5 行示例输入。然后...

(   export LC_ALL=C; </tmp/F \
    grep -n ''   | sort -t:  -nmk1,1 ./L - |
    sed /:/d\;n  | cut  -sd: -f2-
)|  head - /tmp[FL]

...印刷...

==> standard input <==
a-z 1& 0-9
a-z 4& 0-9
a-z 5& 0-9

==> /tmp/F <==
a-z 1& 0-9
a-z 2& 0-9
a-z 3& 0-9
a-z 4& 0-9
a-z 5& 0-9

==> /tmp/L <==
1
4
5

更大的定时测试

我创建了几个相当大的文件：

seq 5000000 | tee /tmp/F |
sort -R | head -n1500000 |
sort -n >/tmp/L

...将 500 万行放入其中/tmp/F，并将其中随机选择的 150 万行放入/tmp/L.然后我做了：

time \
(   export LC_ALL=C
    grep -n ''   | sort -t:  -nmk1,1 ./L - |
    sed /:/d\;n  | cut  -sd: -f2-
)   <./F |wc - l

它打印：

1500000
grep -n '' \
    0.82s user 0.05s system 73% cpu 1.185 total
sort -t: -nmk1,1 /tmp/L - \
    0.92s user 0.11s system 86% cpu 1.185 total
sed /:/d\;n \
    1.02s user 0.14s system 98% cpu 1.185 total
cut -sd: -f2- \
    0.79s user 0.17s system 80% cpu 1.184 total
wc -l \
    0.05s user 0.07s system 10% cpu 1.183 total

（我在那里添加了反斜杠）

在当前提供的解决方案中，这是所有解决方案中最快的，但与上面在我的计算机上生成的数据集进行比较时是最快的。在其他人中，只有一位接近争夺第二名，那就是 meuh 的perl 这里。

这绝不是最初提供的解决方案——由于其他人提供的建议/灵感，它减少了三分之一的执行时间。请参阅帖子历史记录以获取较慢的解决方案（但为什么？）。

另外，值得注意的是，如果不是我的系统的多 CPU 架构以及该管道中每个进程的并发执行，其他一些答案可能会更好。它们都同时工作——每个都在自己的处理器核心上——传递数据并完成整体的一小部分。它太酷了。

但最快的解决方案是...

但这不是最快的解决方案。毫无疑问，这里提供的最快的解决方案是C程序。我叫它cselect。将其复制到我的 X 剪贴板后，我将其编译为：

xsel -bo | cc -xc - -o cselect

然后我做了：

time \
    ./cselect /tmp/L /tmp/F |
wc -l

...结果是...

1500000
./cselect /tmp/L /tmp/F  \
    0.50s user 0.05s system 99% cpu 0.551 total
wc -l \
    0.05s user 0.05s system 19% cpu 0.551 total

答案2

我会使用awk，但不会将 的全部内容存储L.txt在内存中并进行不必要的哈希查找;-)。

list=L.txt file=F.txt
LIST="$list" awk '
  function nextline() {
    if ((getline n < list) <=0) exit
  }
  BEGIN{
    list = ENVIRON["LIST"]
    nextline()
  }
  NR == n {
    print
    nextline()
  }' < "$file"

答案3

我会用awk：

awk 'NR==FNR {a[$1]; next}; FNR in a' L.txt F.txt

更新：我已经完成了绩效衡量；似乎这个版本对于非常大的数据集（如规定的要求的情况）可以更好地扩展，因为比较非常快并且过度补偿了构建哈希表所需的工作。

答案4

只是为了完整性：我们可以合并 Stéphane Chazelas 答案中优秀的 awk 脚本和 kos 答案中的 perl 脚本，但不将整个列表保留在内存中，希望 perl 可能比 awk 更快。 （我更改了参数的顺序以匹配原始问题）。

#!/usr/bin/env perl
use strict;

die "Usage: $0 l f\n" if $#ARGV+1 != 2;
open(L,$ARGV[0]) or die "$ARGV[0]: $!";
open(F,$ARGV[1]) or die "$ARGV[1]: $!";

while(my $number = <L>){
    #chop $number;
    while (<F>) {
        if($. == $number){
            print;
            last;
        }
    }
}

相关内容