☰

将一个文件中的行与另一文件中的行进行匹配

tag-icon • tag-icon linux awk sed grep gawk
将一个文件中的行与另一文件中的行进行匹配

我有一个相当大的列表（100 万左右）和另一个巨大的列表（17gb），我需要将 list1 中的行与分隔文件 2 的第一部分匹配，如下所示：

清单1：

98433259@34
90345394@43
94335053@23

列表2

54353456@35:nancy
98433259@34:jack
94335053@23:james
32409533@86:robert

输出：

98433259@34:jack
94335053@23:james

我尝试过 grep -Fwf list1 list2 但它太慢了

有没有更快的方法来做到这一点？

答案1

太慢了？你能指望什么？该文件中有大约 100 万行，假设有 12 MB。现在，对于另一个文件的每一行，您必须扫描整个文件。您可能会说，十分之九的情况下，比较会在第一个字节之后停止，但即使如此，您也必须继续扫描下一个换行符，因此实际上对于第二个文件的每一行，第一个文件的每个字节都有通过CPU。

现在第二个文件可能有十亿行。因此，您需要扫描 10 亿次 12 MB，即 12 艾字节！现在，如果您的台式机有 8 MB 的 L3 缓存，那么这 12 MB 就无法容纳，必须从 RAM 中获取。幸运的是，现在 RAM 很快，也许您的机器的有效吞吐量为 20 GB/s。如果我计算正确的话，以 20 GB/s 的速度访问 12 Exebyte 需要 600.000 秒。 10.000 分钟。 167 小时。 7天。一周。

但这不是慢，而是真的快！它只需要很长时间，因为这是一项艰巨的任务。

如果您想要更快，您需要为此目的设计的工具。你不会发现它可以使用，所以你自己写吧。

如何？使用快速语言，例如Cand 首先组织您的 file1 数据，这样您就不必扫描所有数据。将每条记录放入树中。根有十个指向子树的指针，具体取决于第一个数字。每个子树还有另外十个指向子树的指针，除非空指针表明这里没有叶子。

现在，当扫描 file2 时，您获取第一个字节并根据该数字获取指针，在该子树中选择第二个数字的指针，依此类推。对于 8 位数字和 64 位指针，在最坏的情况下（找到匹配）您只需加载 64 个字节，加上存储在该名称中的字节。也许每行 80 个字节，十亿倍就变成 80 GB，4 秒内从内存中获取。听起来更好，不是吗？

这是更快的方法，但这与 UNIX 无关。如果您不知道如何编写这样的程序，StackOverflow 应该是您询问的地方。你可以参考这里。

相关内容