从非常大的文件中按键提取行

乔伯特

我有一个4200万行的文本文件。每行的前九个字符是数字键。仅提取其密钥存在于另一个约150万个密钥列表中的行的最有效方法是什么?文件和键列表均已排序。

Maxschlepzig

使用awk应该足够有效-它提供了内置的关联数组,其中键查找时间与(您的查找表中的键的数目)对数成正比,在您的示例中相对较小。

您的输入是:

42M * log2(1.5M) -> 42M * 20 key comparisons 

(其中M表示10 ^ 6)

如果您的awk使用哈希表,则每次键查找仅花费固定的时间量。

一个有效的基于awk的解决方案的示例(使用默认字段分隔符):

$ awk 'ARGIND == 1 { a[$1] = 1; next } a[$1] { print $0 }' keys.dat largefile.dat

由于对两个输入都进行了排序,因此您可以编写效率更高的脚本(运行时随两个输入文件的大小线性缩放)。但这将花费更多的时间进行编程。

或者,您可以使用join期望的排序文件作为输入-限制是您的密钥需要按字母顺序排序-也许您必须调整输出格式。例如:

$ join -j1 keys.dat largefile.dat

使用-t配置域分隔和-o调整输出格式。

这应该在时间上与输入大小成线性关系。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章