按行号过滤文件

Question

给定每行一个非负整数的文件 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 工具。

---

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

Answer 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]数字和:冒号。
  • 出于这个原因，在 128 个可能的集合中找到这 11 个字符比在其他情况下涉及 UTF-8 更简单。
• grep -n ''
  • 这会将字符串LINENO:插入到 stdin - 或 中每一行的开头<./F。
• sort -t: -nmk1,1 ./L -
  • sort完全忽略对其输入文件进行排序，而是（正确地）假定它们已-m预先-numerically排序并按排序顺序进行处理，基本上忽略了任何可能出现的-k1,1st-t:冒号字符之外的任何内容。
  • 虽然这可能需要一些临时空间来做（取决于某些序列可能发生的距离），但与适当的排序相比，它不需要太多，并且它会非常快，因为它涉及零回溯。
  • sort将输出单个流，其中任何 lineno's in./L将立即位于./F. ./L的行总是排在最前面，因为它们较短。
• sed /:/d\;n
  • 如果当前行与/:/冒号匹配，d则将其从输出中删除。否则，自动打印当前n行和ext 行。
  • 因此，只sed修剪不匹配冒号和下一行的顺序行对sort的输出- 或者，只修剪一行，然后是下一行。./L
• cut -sd: -f2-
  • cut -s从输出中抑制那些不包含至少一个其-d:分隔符字符串的输入行- 因此./L's 的行被完全修剪。
  • 对于那些行，他们的第一个以:冒号分隔的字段-f已经cut消失了 - 所有grep插入的 lineno 也是如此。

小输入测试

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

更大的定时测试

我创建了几个非常大的文件：

==> 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

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

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

它打印：

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

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

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

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

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

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

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

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

然后我做了：

xsel -bo | cc -xc - -o cselect

……结果是……

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

Answer 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"

Answer 3

我会用awk：

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

更新：我已经完成了性能测量；似乎这个版本在处理非常大的数据集时甚至可以更好地扩展（正如所述要求的情况），因为比较非常快并且过度补偿了构建哈希表所需的工作。

Answer 4

随着C省略有意义的错误信息：

#include <stdio.h>
#include <stdlib.h>

int main (int argc, char *argv[]) {

    FILE *L;
    FILE *F;

    unsigned int to_print;
    unsigned int current = 0;
    char *line = NULL;
    size_t len = 0;

    if ((L = fopen(argv[1], "r")) == NULL) {
        return 1;
    } else if ((F = fopen(argv[2], "r")) == NULL) {
        fclose(L);
        return 1;
    } else {

        while (fscanf(L, "%u", &to_print) > 0) {
            while (getline(&line, &len, F) != -1 && ++current != to_print);
            if (current == to_print) {
                printf("%s", line);
            }
        }

        free(line);
        fclose(L);
        fclose(F);
        return 0;
    }
}