非再帰マージソート

既にAWK Users JP :: gawk の asort() 関数は相当おかしくないなどで何度も取り上げているマージソートですが、再帰なしのマージソート - Windows Live に書かれている非再帰のマージソートを awk に移植してみました。

以下のコードを見てもらうと分かると思いますが、再帰のものも非再帰のものもコアとなるマージソート部分は同じであることが分かります。

#! /usr/local/bin/nawk -f
# non_recursive_merge_sort.awk
# 非再帰マージソート
# usage: nawk -f non_recursive_merge_sort.awk file(s)

{
    line[NR] = $0;
}

END {
    non_recursive_merge_sort(line, NR);

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

function non_recursive_merge_sort(arr, len,
            div, seg, fb, fe, sb, se, i, j, n, p, tmp) {

    for (div = 1; div <= len; div *= 2) {
        for (seg = 0; seg < len; seg += div * 2) {
            fb = n = seg;
            sb = fe = (fb + div <= len) ? fb + div : len + 1;
            se = (sb + div <= len) ? sb + div : len + 1;

            i = fb;
            j = sb;
            while (i < fe && j < se) {
                tmp[n++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
            }
            while (i < fe) {
                tmp[n++] = arr[i++];
            }
            while (j < se) {
                tmp[n++] = arr[j++];
            }
            for (p = seg; p < n; ++p) {
                arr[p] = tmp[p];
            }
        }
    }
}

非再帰のものは再帰のものと比べて関数を呼び出すオーバーヘッドが少ないため、高速に動作すると言われています。

そこでまず 1000000 行のランダムな数字の羅列を以下の用にして生成します。

$ nawk 'BEGIN{for(i=1;i<=1000000;i++)print rand()}' > test.dat

次にこれをソートしますが、再帰版のマージソートとしては以下のようなものを用いました。

#! /usr/bin/gawk -f

{
  line[NR] = $0;
}

END {
    merge_sort( line, 1, NR );

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

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

#--------------------------------------------------------------------
# function for merge
#--------------------------------------------------------------------
function merge(arr, a, k, b,   i, j, p, c) {
    j = i = a;
    p = k + 1;
    while (a <= k && p <= b) {
        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++;
    }
}

若干、再帰版と非再帰版で異なりますが、そこはご了承ください。

$ time nawk -f recursive_merge_sort.awk test.dat > /dev/null
168.81s user 0.36s system 94% cpu 2:58.12 total

$ time nawk -f non_recursive_merge_sort.awk test.dat > /dev/null
158.18s user 0.34s system 96% cpu 2:45.06 total

わずかの差になりましたが、非再帰版の方が約 10 秒高速に動作しているようです。