[AWK] 巨大な行列の転置を行う

問題設定

下記のように文字列を転置することを考えます。

cat input.txt
AAA
BBB
CCC

cat output.txt
ABC
ABC
ABC

小さい行列の場合

まず手始めに小さい行列を転置します。
A-Cの3行で、それぞれ3文字を格納した行列を作製します。

seq_len=3
awk -v seq_len="${seq_len}" \
'BEGIN {A=65; C=A+3; for (i=A; i<C; i++){
    alphabet=sprintf("%c", i)
    s=sprintf("%"seq_len"s","")
    gsub(/ /,alphabet,s)
    print s}
    }' \
> input1.txt

cat input1.txt
AAA
BBB
CCC

それでは転置を行います。
Stack OverflowにAWKのコードがありました。
連想配列を巧みに扱ったエレガントなコードです。
拝借します。

awk -F "" '
{for (i=1; i<=NF; i++)  { a[NR,i] = $i }}
NF>p { p = NF }
END { for(j=1; j<=p; j++) {
        str=a[1,j]
        for(i=2; i<=NR; i++){ str=str""a[i,j] }
        print str}}' input1.txt \
> output1.txt

cat output1.txt
ABC
ABC
ABC

なにも問題ありませんね

大きい行列の場合：メモリ消費量が尋常ではない

それでは大きいサイズの行列を転置します。
A-Zの26行で、それぞれ1,000,000文字を格納した行列を作製します。

seq_len=1000000
awk -v seq_len="${seq_len}" \
'BEGIN {A=65; Z=A+26; for (i=A; i<Z; i++){
    alphabet=sprintf("%c", i)
    s=sprintf("%"seq_len"s","")
    gsub(/ /,alphabet,s)
    print s}
    }' \
> input2.txt

ファイルサイズは25Mです。

ls -lh input2.txt | cut -d " " -f 5
25M

それでは、これを上記のコードで計算します。

その前に、計算時間とメモリ消費量を記録するコマンドを作ります。

alias time_='/usr/bin/time -f "========\nreal %es\nuser %Us \nsys  %Ss \nmemory:%MKB \n========"'

では、実行します。

time_ awk -F "" '
{for (i=1; i<=NF; i++)  { a[NR,i] = $i }}
NF>p { p = NF }
END { for(j=1; j<=p; j++) {
        str=a[1,j]
        for(i=2; i<=NR; i++){ str=str""a[i,j] }
        print str}}' input2.txt \
> output2.txt

========
real 25.33s
user 23.87s 
sys  1.44s 
memory:7554988KB 
========

メモリをなんと7.6GBも消費しています！！

解決法

メモリ消費量が大きい理由は、連想配列に全データを格納しているからです。
なので、目的の計算が終わったら直ちにファイルに書き出すようにします。

nr=$(cat input2.txt | wc -l)

time_ awk -v nr="${nr}" -F "" \
'{for(i=1; i<=NF; i++){
        row[i]=row[i] $i
        if(NR==nr) print row[i]
    }
}' input2.txt \
> output3.txt

========
real 6.46s
user 6.36s 
sys  0.09s 
memory:240704KB 
========

メモリ消費量240MB！！

計算時間はおよそ1/4、メモリ消費量にいたっては約3/100になりました！

最後に、Stack Overflowのコードと今回のコードで出力結果が同じか確認します。

[ -z $(diff output2.txt output3.txt) ] &&
printf "同じ結果です\n"
同じ結果です

同じ結果が得られました。

学んだこと

大きなファイルを扱う場合、連想配列に格納したデータはENDまで保持せず、すぐに出力しましょう