awk关联数组快速增长

#!/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-only解决方案在我的系统上花费的时间大致相同.我的系统将花费很长时间来解决1.4亿行的问题,无论使用何种方法,但我为1000万行的文件运行了一个测试用例.

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

计时结果

我对两个候选解决方案的性能关系的假设对于我尝试过的测试用例来说是错误的.在我的系统上,基于排序的解决方案和仅awk解决方案为100万和1000万行输入文件中的每一个采用了相似(在30％以内)的时间量,每个解决方案的解决方案速度更快案件.当然,当输入文件大小超过10倍时,我不知道这种关系是否会成立.

奇怪的是,1000万线路问题花了大约10倍的时间来运行这两个解决方案作为100万线路问题,这让我感到困惑,因为我预计两种解决方案都会出现与文件长度的非线性关系.