‪データの集計ではsort | uniq -c をシェル芸で良く使うけど大量データには向かないのでawkでもっと高速な処理を書く‬

sort | uniq -c という操作は、データの集合から件数を数えるのによく使いますね。

uniq はデータから重複データを取り除いたり、重複したデータだけを取り出したり、あるいは件数を数える、という処理ができるコマンドですが、実行時の前提条件として予めソートされたデータが必要です。だから先に sort しています。

しかしデータの母集団が大きいと sort の処理時間がボトルネックとなって、数分単位のオーダーで処理待ちが起きることがあります。そのような場合に sort | uniq -c とは違う方法で集計を行えば、処理速度を大幅に改善できる可能性があります。

例：1から1000までのランダムな値の集合1億件について、値ごとの件数を集計してみる

例えば1から1000までのランダムな値の集合1億件のデータを以下のように作成したとして……

# 試験データの作成（1～1000のランダムな数値の集合を１億件作る）
kinoue@ubuntu1604LTS:~$ seq 100000000 | awk 'BEGIN{ srand('"$RANDOM"')  } { printf "%d\n", rand() * 1000 }' > randomvalue.txt

これを単にsortしてuniqすると、手元の環境では1分20秒台で処理が完了しました。

# sort | uniq -c は速くない
kinoue@ubuntu1604LTS:~$ time cat randomvalue.txt | sort | uniq -c > /dev/null

real    1m25.391s
user    1m22.904s
sys     0m1.188s

ただし今回は数値の集合なので、sortの条件を変えたら約20秒の短縮ができました。

# 今回の試験データは数値だけの集合なので、sort -n | uniq -c で速度改善可能
kinoue@ubuntu1604LTS:~$ time cat randomvalue.txt | sort -n | uniq -c > /dev/null

real    1m3.361s
user    0m54.528s
sys     0m1.248s

事前にsortするのがボトルネックなので、それを止める方法を考える

結局、sort の方法を変えれば時間短縮できるということは、これがボトルネックであることを意味します。しかしそもそも sort と uniq を組み合わせるのではなく、連想配列やハッシュ配列、ディクショナリ型などを用いた実装で代替すれば、より高速に処理できる余地があります。

今回の例はawkのスクリプトでsort | uniq -cの処理を置き換えてみましたが、これだと約20秒で処理が完了しました。1分以上の時間が掛かっていたようにくらべると、とても高速になりました。

# 今回作成したスクリプトを使えば、sort | uniq -c よりも高速に処理が行える
kinoue@ubuntu1604LTS:~$ time cat randomvalue.txt | ./uniqc.awk > /dev/null

real    0m20.089s
user    0m19.692s
sys     0m0.348s

２種類の実行結果が合致することを確かめる

このように時間は短縮できましたけど、２つの方法の実行結果が本当に一致するかどうかを検証してみましょう。

1-1000のランダムデータ１億件の結果をここで引用するのは無理なので、別の母集団として1-6の値のランダムデータ100万件を作成してみます。この実行結果を２つの方法で比較すると集計結果は全く同じであることがわかります。

# 試験データの作成（1～6の値をランダムに100万件作る）
seq 1000000 | awk 'BEGIN{ srand('"$RANDOM"')  } { printf "%d\n", 1 + rand() * 6 }' > dicevalue.txt

# sort | uniq -c の実行結果
kinoue@ubuntu1604LTS:~$ cat dicevalue.txt | sort | uniq -c
 167433 1
 166536 2
 166209 3
 166335 4
 166403 5
 167084 6

# 今回作成したスクリプトでの実行結果
kinoue@ubuntu1604LTS:~$ cat dicevalue.txt | ./uniqc.awk
167433  1
166536  2
166209  3
166335  4
166403  5
167084  6

実装例

スクリプトをファイルにするならこんな感じです。

uniqc.awk

#!/usr/bin/awk -f

{
	# 入力行を添字とする連想配列をキーバリューストアのように使ってキーの出現数を管理する
	key=$0
	value[key]++
}

END {
	# value と key をタブ区切りで全件出力する
	for ( key in value ) print value[key] "\t" key
}

ワンライナーならこんなふうに書けます。スマホのメモアプリとかに転記しておけば、自分の管理下にない環境のようにスクリプトファイルをインストールしづらい状況でも使えます。

kinoue@ubuntu1604LTS:~$ cat dicevalue.txt | awk '{ v[$0]++ } END { for ( k in v ) print v[k] "\t" k }'
167433  1
166536  2
166209  3
166335  4
166403  5
167084  6