AWK關聯數組生長快

Question

我已經指派號碼MD5SUMS喜歡一個文件如下：

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

另一個文件containts三個每一行MD5SUMS像如下：

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

我想什麼用第一個文件的整數替換第二個文件中的第一個和第三個md5sum。目前，我想以下awk腳本：

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

的問題是，該腳本需要更多的16克RAM儘管第一個文件是隻有在硬盤上5.7克。

Answer 1

這個問題可以解決，如下（file1.txt與整數和MD5SUMS的文件，而file2.txt是MD5SUMS的三列的文件）：

#!/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是的情況下，每一百萬行的長度，這個解決方案和Ed Morton的awk - 只需要在我的系統上花費大約相同的時間。無論使用何種方法，我的系統都需要很長時間才能解決1.4億行的問題，但我爲1000萬行文件運行了測試用例。

我曾經假設依賴於sort（在需要時自動使用臨時文件）的解決方案對於大量行應該更快，因爲它將是O（N log N）運行時，而重新讀取的解決方案如果兩個文件的大小相似，那麼每個輸入行的映射文件將爲O（N^2）。

時序結果

我對於兩個候選解決方案的性能關係的假設被證明是錯誤的，我試過測試用例。在我的系統中，僅基於sort的解決方案和僅基於awk的解決方案在每個100萬和1000萬行輸入文件中相互花費了相似的時間（不到30％），其中awk-僅在每個解決方案中速度更快案件。當然，當輸入文件大小增加10倍以上時，我不知道這種關係是否成立。

奇怪的是，1000萬行問題花費了大約10倍的時間來處理這兩種解決方案，因爲100萬行問題困擾着我，因爲我期望兩種解決方案都具有非線性關係和文件長度。

Answer 2

如果你沒有足夠的內存來存儲的第一個文件，那麼你需要寫這樣的事情來查找第一個文件，在第2個文件中的每個值：

awk 'BEGIN{OFS="\t"} 
{ 
    val1 = val3 = "" 
    while ((getline line < "mapping.txt") > 0) { 
     split(line,flds) 
     if (flds[2] == $1) { 
      val1 = flds[1] 
     } 
     if (flds[2] == $3) { 
      val3 = flds[1] 
     } 
     if ((val1 != "") && (val3 != "")) { 
      break 
     } 
    } 
    close("mapping.txt") 

    print val1,$2,val3 

}' relation.txt 

這將是慢。如果你喜歡，你可以添加一個N getline-d行的緩存來加速它。

Answer 3

如果文件的大小導致awk耗盡內存，則可以使用另一個工具或其他方法。

sed命令可能成功，但內存使用量會少得多。這個想法是讀取索引文件並創建一個執行重新映射的sed腳本，然後在生成的sedscript上調用sed。

下面的bash腳本是這個想法的實現。它包含一些STDERR輸出來幫助跟蹤進度。我喜歡爲大數據集或其他類型的耗時處理問題生成進度跟蹤輸出。

此腳本已經過一小組數據測試;它可能工作在您的數據。請試一試。

#!/bin/bash 

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

# md5-data.txt 
# 00000035552C6F8B9E7D70F1E4E8D500 276EC96E149571F8A27F4417D7C6BC20 9CFEFED8FB9497BAA5CD519D7D2BB5D7 
# 00000035552C6F8B9E7D70F1E4E8D500 44E48C092AADA3B171CE899FFC6943A8 1B757742E1BF2AA5DB6890E5E338F857 

# Goal replace field 1 and field 3 with indexes to md5 checksums from md5-indexes 

md5_indexes='md5-indexes.txt' 
md5_data='md5-data.txt' 

talk() { echo 1>&2 "$*" ; } 
talkf() { printf 1>&2 "$@" ; } 
track() { 
    local var="$1" interval="$2" 
    local val 
    eval "val=\$$var" 
    if ((interval == 0 || val % interval == 0)); then 
    shift 2 
    talkf "$@" 
    fi 
    eval "(($var++))" # increment the counter 
} 

# Build a sedscript to translate all occurances of the 1st & 3rd MD5 sums into their 
# corresponding indexes 

talk "Building the sedscript from the md5 indexes.." 

sedscript=/tmp/$$.sed 

linenum=0 
lines=`wc -l <$md5_indexes` 
interval=$((lines/100)) 

while read index md5sum ; do 
    track linenum $interval "..$linenum" 
    echo "s/^[[:space:]]*[[:<:]]$md5sum[[:>:]]/$index/" >>$sedscript 
    echo "s/[[:<:]]$md5sum[[:>:]]\$/$index/"   >>$sedscript 
done <$md5_indexes 
talk '' 

sedlength=`wc -l <$sedscript` 

talkf "The sedscript is %d lines\n" $sedlength 

cmd="sed -E -f $sedscript -i .bak $md5_data" 
talk "Invoking: $cmd" 

$cmd 

changes=`diff -U 0 $md5_data.bak $md5_data | tail +3 | grep -c '^+'` 

talkf "%d lines changed in $md5_data\n" $changes 

exit 

這裏有兩個文件：

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

cat md5-data.txt 
00000035552C6F8B9E7D70F1E4E8D500 276EC96E149571F8A27F4417D7C6BC20 9CFEFED8FB9497BAA5CD519D7D2BB5D7 
00000035552C6F8B9E7D70F1E4E8D500 44E48C092AADA3B171CE899FFC6943A8 1B757742E1BF2AA5DB6890E5E338F857 

這裏是樣品運行：

$ ./md5-reindex.sh 
Building the sedscript from the md5 indexes.. 
..0..1..2..3..4..5..6..7..8 
The sedscript is 18 lines 
Invoking: sed -E -f /tmp/83800.sed -i .bak md5-data.txt 
2 lines changed in md5-data.txt 

最後，生成的文件：

$ cat md5-data.txt 
1 276EC96E149571F8A27F4417D7C6BC20 9CFEFED8FB9497BAA5CD519D7D2BB5D7 
1 44E48C092AADA3B171CE899FFC6943A8 1B757742E1BF2AA5DB6890E5E338F857