我有一个4200万行的文本文件。每行的前九个字符是数字键。仅提取其密钥存在于另一个约150万个密钥列表中的行的最有效方法是什么?文件和键列表均已排序。
使用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] 删除。
我来说两句