我有一个42M行的文本文件。每行的前九个字符是数字键。仅提取其键存在于另一个大约 150 万个键的列表中的行的最有效方法是什么？文件和键列表均已排序。
答案1
使用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调整输出格式。
这应该与输入大小成线性时间运行。
答案2
请注意，此方法使用固定长度的长度键从记录的第一个字节开始。
通过使用\x01（或任何唯一的单字节字符）作为临时字段分隔符，可以更轻松地操作记录。
join -t$'\x01' <(sed -r 's/.{9}/&\x01/' main) <(cut -b -9 keys) |sed -r 's/(.{9})./\1/'
马克斯施莱普齐格的 awk示例对于 45,000,000 条记录速度更快，但对于更大的文件则失败。您有多少可用内存？
结果如下：
45,000,000 unique records, 1,500,000 keys
=========================
awk
real 0m31.971s
user 0m28.782s
sys 0m2.972s
join
real 0m53.733s
user 0m54.255s
sys 0m0.708s
(2x45) 90,000,000 records, 1,500,000 keys
=========================
awk
awk: (FILENAME=main2 FNR=54334297) fatal: assoc_lookup: bucket->ahname_str: can't allocate 11 bytes of memory (Cannot allocate memory)
join
real 1m35.306s
user 1m34.754s
sys 0m1.344s
===================
答案3
假设它是一个基于行的文件，grep应该非常有效。将-f keyfile和-F用于固定字符串：
grep -F -f keys textfile
注意：请注意 PeterO 在下面的评论中关于误报的警告。