gawk のビルトイン asort() はオレ quick sort より速い
GNU awk こと gawk は配列をソートする関数 asort() の拡張が行われていますので、従来のように sort コマンドでパイプ処理を行ったり、自前で sort を用意する必要がないため便利になっています。 javascript - Array#sortはオレquicksortより遅い by Chrome にありますが、こうしたビルトイン関数とオレオレ関数の速度には差があるのですが、awk の場合にはどうなのでしょうか?
gawk の拡張である asort() 関数は中身はマージソートになっていますので、本来はマージソート比較をするべきなのかもしれませんが、ここではクイックソートを用いてみます。 クイックソートは同じ O(n log(n)) の計算量であるマージソートと比較しても高速に動作する場合が多く、安定ソートではないものの良く使われるソートです。
ここでは再帰版と非再帰版と asort() 版で比較してみます。
まずは再帰版のクイックソートです。
#! /usr/bin/gawk -f
# recursive_quick_sort.awk
{
a[NR] = $0;
}
END {
# Quick Sort
quick_sort(a, 1, NR);
# ソートされた配列の表示
for (i = 1; i <= NR; i++) {
print a[i];
}
}
# quick_sort(): 再帰版 Quick Sort
# in: 配列 arr
# 最初のインデックス left
# 最後のインデックス right
# out: ソートされた配列
function quick_sort(array, left, right, i, j, tmp, pivot) {
if (left < right) {
i = left;
j = right;
pivot = array[int((left + right) / 2)];
while (i <= j) {
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
tmp = array[i];
array[i] = array[j];
array[j] = tmp;
i++;
j--;
}
}
quick_sort(array, left, j);
quick_sort(array, i, right);
}
}
一般的に良く知られたクイックソートはこの形であることが多いです。 次に非再帰版クイックソートです。
#! /usr/bin/gawk -f
# nonrecursive_quick_sort.awk
{
a[NR] = $0;
}
END {
# Quick Sort
quick_sort(a, 1, NR);
# ソートされた配列の表示
for (i = 1; i <= NR; i++) {
print a[i];
}
}
# quick_sort(): 非再帰版 Quick Sort
# in: 配列 arr
# 最初のインデックス left
# 最後のインデックス right
# out: ソートされた配列
function quick_sort(array, left, right, i, j, tmp, pivot, sp, left_stack, right_stack) {
sp = 0;
while (1) {
if (right - left <= 0) {
if (!sp) {
break;
}
left = left_stack[--sp];
right = right_stack[sp];
} else {
i = left;
j = right;
pivot = array[int((left + right) / 2)];
while (1) {
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i >= j) {
break;
}
tmp = array[i];
array[i] = array[j];
array[j] = tmp;
i++;
j--;
}
if (i - left < right - j) {
left_stack[sp] = left;
right_stack[sp++] = i - 1;
left = j + 1;
} else {
left_stack[sp] = j + 1;
right_stack[sp++] = right;
right = i - 1;
}
}
}
}
再帰版と比較すると長くなっています。 次に asort() 版です。
#! /usr/bin/gawk -f
# builtin_sort.awk
{
a[NR] = $0;
}
END {
# Builtin Sort (マージソート)
asort(a);
# ソートされた配列の表示
for (i = 1; i <= NR; i++) {
print a[i]
}
}
非常にスッキリとなることが分かります。
さて、実際の速度を調べてみましょう。
$ time seq 1000000 | tac | gawk -f recursive_quick_sort.awk > /dev/null seq 1000000 0.69s user 0.01s system 90% cpu 0.775 total tac 0.03s user 0.04s system 4% cpu 1.847 total gawk -f recursive_quick_sort.awk > /dev/null 15.56s user 0.10s system 94% cpu 16.623 total $ time seq 1000000 | tac | gawk -f nonrecursive_quick_sort.awk > /dev/null seq 1000000 0.74s user 0.00s system 86% cpu 0.855 total tac 0.04s user 0.03s system 3% cpu 1.934 total gawk -f nonrecursive_quick_sort.awk > /dev/null 15.63s user 0.12s system 94% cpu 16.737 total $ time seq 1000000 | tac | gawk -f builtin_sort.awk > /dev/null seq 1000000 0.72s user 0.01s system 94% cpu 0.771 total tac 0.04s user 0.04s system 4% cpu 1.888 total gawk -f builtin_sort.awk > /dev/null 3.23s user 0.07s system 78% cpu 4.187 total
なんと圧倒的にビルトイン asort() 関数が高速であることが分かります。 もっとも C で書かれた sort が awk で書かれた sort に負けては困るわけですが・・・。
おまけで awk の中で最速の mawk で試してみます。 mawk はバイトコンパイルを行うため、非常に高速に処理することができます。
$ time seq 1000000 | tac | mawk -f recursive_quick_sort.awk > /dev/null seq 1000000 0.74s user 0.01s system 86% cpu 0.874 total tac 0.05s user 0.04s system 6% cpu 1.332 total mawk -f recursive_quick_sort.awk > /dev/null 3.89s user 0.05s system 81% cpu 4.816 total $ time seq 1000000 | tac | mawk -f nonrecursive_quick_sort.awk > /dev/null seq 1000000 0.74s user 0.01s system 88% cpu 0.843 total tac 0.04s user 0.04s system 6% cpu 1.317 total mawk -f nonrecursive_quick_sort.awk > /dev/null 3.77s user 0.06s system 81% cpu 4.692 total
う〜ん、惜しい。 よって、awk では gawk のビルトイン asort() が最速ということになります。
さらに惜しいのは、これだけ高速に動作する mawk が実質メンテナンスをあまりされていないため、今後 mawk を使う機会が少なくなっていくことです。 BSD 系の OS では使われることも多いようですが、Linux では Debian 系くらいしかサポートされていない上に、比較的新しい環境ではビルドすることも困難になってきています。
