Contents

実行環境

昨日と同様、Windows7 32bit + Chrome Portable43、Firefox Portable40、IE10で動作確認しました。冒頭の画像はChrome。下の点線内が実際にHTMLで動かしているところ（インラインフレーム）とURLで、ロードするたび値が変わります。古いブラウザではエラーになるかもしれません。URLのクエリパラメータのlenが配列の要素数、printが結果表示する要素数。

» http://kenpg.bitbucket.org/blog/201509/11/array_to_heap_sort.html?len=5000&print=10

処理の中心部分

ソートも昨日と同様、浅野・和田・増澤『アルゴリズム論』（オーム社，2003年）90～94頁を参考にしました。その前のヒープを作る部分は、昨日の2番目のアルゴリズムだけに（1番目は少し遅かったので）。中心的なクラスメソッドを抜き出すと ↓ こんな感じ。ヒープの任意ノードから下へ下へ辿って整形する関数は、ヒープ作成・ソート両方で使えるよう共通化。全体のソースは次項にあります。

// 配列からヒープを作成

TestHeap.prototype.build2 = function () {
    var h = this.ary.concat(),
        len = h.length,
        ord_start = Math.floor(len / 2) - 1;
    for (var i = ord_start; 0 <= i; i--) this.arrange3(i, len, h);
    this.heap_init = h;
};

// ヒープをソート（降順）

TestHeap.prototype.sort1 = function () {
    this.heap_sorted = this.heap_init.concat();
        // 元ヒープを新しい配列にコピー
    var h1 = this.heap_init.concat(), h2 = this.heap_sorted,
        len = h1.length - 1, last = null;
    for(var i = 0; i <= len; i++) {
        h2[i] = h1[0]; // 元ヒープの頂点の値を、新しい配列にコピー
        if (i === len) break;
        last = len - i;
        h1[0] = h1[last];
        this.arrange3(0, last, h1);
    }
};

// ヒープの任意ノードから下へ下へ辿って整形する関数

TestHeap.prototype.arrange3 = function (ord, last, h) {
    var below = 2 * (ord + 1) - 1;
    if (last < below) return;

    var vc = h[ord],       // value current
        vb = h[below],     // value below
        vr = h[below + 1]; // value right below
    if (below < last && vb < vr) {
        below++;
        vb = vr;
    }
    if (vc < vb) {
        h[ord] = vb;
        h[below] = vc;
        this.arrange3(below, last, h); // 再帰呼び出し
    }
};

ソース

loading from Bitbucket...loading from Bitbucket...

要素数100万での処理時間

昨日と同様、元の配列は一様分布乱数で、だいたい均等（例えば要素数1000なら0～1000の整数からランダムに）。PCはCore i5-4300M、メモリ3.5GB（32bitのOS管理分）のノートパソコン。要素数100万の配列をヒープ化、続けてソートする処理を5回実行。測定した処理時間は「配列からヒープ作成」と「ヒープのソート」のみ。昨日はうっかりヒープのチェック処理も含めて測定しましたが、今日は除きました。だからヒープ作成部分は少し短縮されてます。まずChromeで、要素数100万で5回行った結果は下のとおり。

# Chrome Portable 43

heap initial : check (OK), time (16ms)
heap sorted : check (OK), time (334ms)

heap initial : check (OK), time (17ms)
heap sorted : check (OK), time (335ms)

heap initial : check (OK), time (17ms)
heap sorted : check (OK), time (337ms)

heap initial : check (OK), time (18ms)
heap sorted : check (OK), time (333ms)

heap initial : check (OK), time (19ms)
heap sorted : check (OK), time (603ms)

ヒープ作成がだいたい20ミリ秒弱、それに比べソートは300ミリ秒以上。5回目のみ更に遅く、繰り返し実行していると数回に1回、そういう時がある模様。いずれにしても要素数100万の配列のソートが、ノートパソコンで1秒以内で済むと分かりました。

続いてFirefoxは下のとおり。ヒープ作成まではChromeとほとんど同じ、ソートは僅かに速いようです。こちらも数回に1回、500～600ミリ秒かかる時がありました。

# Firefox Portable 40

heap initial : check (OK), time (17ms)
heap sorted : check (OK), time (291ms)

heap initial : check (OK), time (19ms)
heap sorted : check (OK), time (294ms)

heap initial : check (OK), time (18ms)
heap sorted : check (OK), time (292ms)

heap initial : check (OK), time (26ms)
heap sorted : check (OK), time (555ms)

heap initial : check (OK), time (19ms)
heap sorted : check (OK), time (294ms)

↓ 最後にIE10。Chrome、Firefoxと比べると少し遅い感じ。でも今回測った中では、ChromeやFirefoxのように「数回に1回、目立って遅い」時は出現しませんでした。

# Internet Explorer 10

heap initial : check (OK), time (24ms)
heap sorted : check (OK), time (412ms)

heap initial : check (OK), time (24ms)
heap sorted : check (OK), time (421ms)

heap initial : check (OK), time (23ms)
heap sorted : check (OK), time (419ms)

heap initial : check (OK), time (24ms)
heap sorted : check (OK), time (421ms)

heap initial : check (OK), time (24ms)
heap sorted : check (OK), time (418ms)

初歩的ですがヒープの扱いが分かったので、次はPostgreSQLの集約関数の自作に使えるか検討します。配列を遷移状態にして、最後にヒープソートするとか。PL/pgSQLと、PL/V8両方で比べてみたい。