awk关联数组快速增长

Question

我有一个文件,将数字分配给md5sums,如下所示:

0   0000001732816557DE23435780915F75
1   00000035552C6F8B9E7D70F1E4E8D500
2   00000051D63FACEF571C09D98659DC55
3   0000006D7695939200D57D3FBC30D46C
4   0000006E501F5CBD4DB56CA48634A935
5   00000090B9750D99297911A0496B5134
6   000000B5AEA2C9EA7CC155F6EBCEF97F
7   00000100AD8A7F039E8F48425D9CB389
8   0000011ADE49679AEC057E07A53208C1

另一个文件在每行中包含三个md5sums,如下所示:

00000035552C6F8B9E7D70F1E4E8D500    276EC96E149571F8A27F4417D7C6BC20    9CFEFED8FB9497BAA5CD519D7D2BB5D7
00000035552C6F8B9E7D70F1E4E8D500    44E48C092AADA3B171CE899FFC6943A8    1B757742E1BF2AA5DB6890E5E338F857

我想要的是用第一个文件的整数替换第二个文件中的第一个和第三个md5sums.目前我正在尝试以下awk脚本:

awk '{OFS="\t"}FNR==NR{map[$2]=$1;next}
{print map[$1],$2,map[$3]}' mapping.txt relation.txt

问题是尽管第一个文件在硬盘驱动器上仅为5.7g,但脚本需要更多的16g内存.

Answer 1

这个问题可以解决，如下（file1.txt是包含整数和 md5sum 的文件，file2.txt是包含三列 md5sum 的文件）：

#!/bin/sh
# First sort each of file 1 and the first and third columns of file 2 by MD5
awk '{ print $2 "\t" $1}' file1.txt | sort >file1_n.txt
# Before we sort the file 2 columns, we number the rows so we can put them
# back into the original order later
cut -f1 file2.txt | cat -n - | awk '{ print $2 "\t" $1}' | sort >file2_1n.txt
cut -f3 file2.txt | cat -n - | awk '{ print $2 "\t" $1}' | sort >file2_3n.txt
# Now do a join between them, extract the two columns we want, and put them back in order
join -t'    ' file2_1n.txt file1_n.txt | awk '{ print $2 "\t" $3}' | sort -n | cut -f2 >file2_1.txt
join -t'    ' file2_3n.txt file1_n.txt | awk '{ print $2 "\t" $3}' | sort -n | cut -f2 >file2_3.txt
cut -f2 file2.txt | paste file2_1.txt - file2_3.txt >file2_new1.txt

file1.txt对于和file2.txt各有 100 万行长的情况，此解决方案和 Ed Morton 的awk唯一解决方案在我的系统上花费的时间大约相同。无论使用哪种方法，我的系统都需要很长时间才能解决 1.4 亿行的问题，但我针对 1000 万行的文件运行了一个测试用例。

我假设依赖的解决方案sort（在需要时自动使用临时文件）对于大量行来说应该更快，因为它将是 O(N log N) 运行时间，而为每个行重新读取映射文件的解决方案如果两个文件大小相似，输入的行将为 O(N^2)。

计时结果

对于我尝试过的测试用例，我对两个候选解决方案的性能关系的假设被证明是错误的。在我的系统上，对于 100 万行和 1000 万行输入文件，基于sort-based 的解决方案和-only 解决方案花费的时间相似（在 30% 以内），而-only 解决方案在每种情况下都更快。当然，我不知道当输入文件大小增加超过 10 倍时，这种关系是否成立。awkawk

奇怪的是，使用这两种解决方案运行 1000 万行问题所需的时间大约是 100 万行问题的 10 倍，这让我很困惑，因为我本以为这两种解决方案都与文件长度存在非线性关系。