gawk の asort() 関数は相当おかしくない

gawk には asort() 関数という配列をマージソート (Merge Sort) を行う関数が用意されています。 PHPのsort関数は相当おかしいという記事が以前話題になりPHP - 以外の言語でPHPのsortを実装してみる。のようにいろいろ議論されました。 さて、gawk の asort() 関数はどうなのでしょうか?

「論より証拠」ということで試してみます。 ここでは以下のようなスクリプトを用意しました。

#! /usr/bin/gawk -f
# asort_2.awk

BEGIN {
    print "========================= Original Data";
}

{
    print $0;
    line[NR]     = $0;
    line_str[NR] = $0 "";
    line_num[NR] = $0 + 0;
}

END {
    asort(line);
    asort(line_str);
    asort(line_num);

    print "========================= Normal asort()";

    for (i = 1; i <= NR; i++) {
        print line[i];
    }

    print "========================= Strings";

    for (i = 1; i <= NR; i++) {
        print line_str[i];
    }

    print "========================= Numeric";

    for (i = 1; i <= NR; i++) {
        print line_num[i];
    }
}

要するに何もケアせずに asort() 関数を用いたもの、空列を連接することで文字列にしたもの、0 (ゼロ) を加えて数値にしたものを評価しています。 ここで、用意した入力ファイルは以下の 2 つです。

$ cat input_1.txt
1e1
1f1
9

$ cat input_2.txt
9
1e1
1f1

ちなみに、1e1 は数値変換すると 10 であり、1f1 は 1 になります。 さて、実行してみます。

$ gawk -f asort_2.awk input_1.txt
========================= Original Data
1e1
1f1
9
========================= Normal asort()
9
1e1
1f1
========================= Strings
1e1
1f1
9
========================= Numeric
1
9
10

$ gawk -f asort_2.awk input_2.txt
========================= Original Data
9
1e1
1f1
========================= Normal asort()
1f1
9
1e1
========================= Strings
1e1
1f1
9
========================= Numeric
1
9
10

予想どおりでしたか?

結果としては PHP の sort と同じ結果になっています。 つまり、awk は型を持たないため、勝手に解釈をしているのですが、最初が 9 の場合には数値として判定し、最初が 1e1 の場合には文字列として判定してしまっているのが原因です。

個人的には awk のような型を持たない言語はこのようなことがおこっても言語の責任ではなく、そういうデータを用意して何もケアせずに asort() 関数に渡してしまった側の問題と考えています。 文字列の頭2桁の数字を年に変換してソートしたいでも書きましたが、sort 関数のせいにするのではなく、sort 関数の流儀に合わせればいいのです。

とはいえ、これはかなり間違いが発生しそうなので、オレオレマージソートを作ってみました。

#! /usr/bin/gawk -f
# my_merge_sort.awk

BEGIN {
    print "========================= Original Data";
}

{
    print $0;
    line[NR]     = $0;
    line_str[NR] = $0 "";
    line_num[NR] = $0 + 0;
}

END {
    merge_sort(line_str, 1, NR);
    merge_sort(line_num, 1, NR);

    print "========================= My Merge Sort";

    merge_sort(line, 1, NR);

    for (i = 1; i <= NR; i++) {
        print line[i];
    }

    print "========================= My Merge Sort (Str)";

    merge_sort(line, 1, NR, "str");

    for (i = 1; i <= NR; i++) {
        print line[i];
    }

    print "========================= My Merge Sort (Num)";

    merge_sort(line, 1, NR, "num");

    for (i = 1; i <= NR; i++) {
        print line[i];
    }

    print "========================= Strings";

    for (i = 1; i <= NR; i++) {
        print line_str[i];
    }

    print "========================= Numeric";

    for (i = 1; i <= NR; i++) {
        print line_num[i];
    }
}

# function for recursive merge sort
function merge_sort(arr, a, b, key,   k) {
    if (a < b) {
        k = int((a + b) / 2);
        merge_sort(arr, a, k, key);
        merge_sort(arr, k + 1, b, key);
        merge(arr, a, k, b, key);
    }
}

# function for merge
function merge(arr, a, k, b, key,   i, j, p, c) {
    j = i = a;
    p = k + 1;
    while (a <= k && p <= b) {
        if (key == "str") {
            if (arr[a] "" <= arr[p] "") {
                c[i++] = arr[a++];
            } else {
                c[i++] = arr[p++];
            }
        } else if (key == "num") {
            if (arr[a] + 0 <= arr[p] + 0) {
                c[i++] = arr[a++];
            } else {
                c[i++] = arr[p++];
            }
        } else {
            if (arr[a] <= arr[p]) {
                c[i++] = arr[a++];
            } else {
                c[i++] = arr[p++];
            }
        }
    }
    while (a <= k) {
        c[i++] = arr[a++];
    }
    while (p <= b) {
        c[i++] = arr[p++];
    }
    while (j <= b) {
        arr[j] = c[j];
        j++;
    }
}

こうすることでどういうメリットがあるかというと、先ほどの数値への強制変換は元の配列となるべき値も破壊してしまっていますが、自分で破壊しないようにしてしまうことができます。

実際に実行してみましょう。

$ gawk -f my_merge_sort.awk input_1.txt
========================= Original Data
1e1
1f1
9
========================= My Merge Sort
9
1e1
1f1
========================= My Merge Sort (Str)
1e1
1f1
9
========================= My Merge Sort (Num)
1f1
9
1e1
========================= Strings
1e1
1f1
9
========================= Numeric
1
9
10

$ gawk -f my_merge_sort.awk input_2.txt
========================= Original Data
9
1e1
1f1
========================= My Merge Sort
1f1
9
1e1
========================= My Merge Sort (Str)
1e1
1f1
9
========================= My Merge Sort (Num)
1f1
9
1e1
========================= Strings
1e1
1f1
9
========================= Numeric
1
9
10

このように破壊することなくソートを行うことができます。 また、このオレオレマージソートは nawk でも動作します。

マージソートは比較条件式を用いている箇所が多いので、どこの比較が問題になっているか分かりにくいのですが、アルゴリズムを押えておけば、どこを修正すれば良いか分かるようになります。