Contents

実行環境

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

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

処理の中心部分

今回、浅野・和田・増澤『アルゴリズム論』（オーム社，2003年）90～94頁を参考に2通りの方法で作ってみました。それぞれのクラスメソッドを抜き出し、日本語コメントを付けると ↓ こんな感じ。全体のソースは次項に、両者の比較は次々項にあります。

// アルゴリズム 1

// メイン処理 : 配列の要素を一つずつ末端ノードを追加していく
TestHeap.prototype.build1 = function () {
    var len = this.ary.length;
    for (var i = 0; i < len; i++) {
        this.heap.push(this.ary[i]);
        this.arrange1(i);
    }
    this.build_after(0);
};

// 整形用関数 : 引数（ノード位置）を起点に、上へ遡ってヒープにする
TestHeap.prototype.arrange1 = function (ord) {
    if (ord === 0) return;
    var h = this.heap,
        parent = Math.floor((ord + 1) / 2) - 1,
        vc = h[ord],    // value current
        vp = h[parent]; // value parent
    if (vc > vp) {
        h[ord] = vp;
        h[parent] = vc;
        this.arrange1(parent); // 再帰呼び出し
    }
    this.cnt++; // 比較回数カウント（上の vc > vp）
};

// アルゴリズム 2

// メイン処理 : 子を持つノードから先頭に遡ってヒープに組み換え
TestHeap.prototype.build2 = function () {
    this.heap = this.aryCopy;
    var start = Math.floor(this.heap.length / 2) - 1;
    for (var i = start; 0 <= i; i--) this.arrange2(i);
};

// 整形用関数 : 引数（ノード位置）から下にたどってヒープにする
TestHeap.prototype.arrange2 = function (ord) {
    var h = this.heap,
        below = 2 * (ord + 1) - 1,
        vc = h[ord],       // value current
        vb = h[below],     // value below
        vr = h[below + 1]; // value right below
    if (typeof vb === 'undefined') {
        return;
    } else if (typeof vr !== 'undefined' && vb < vr) {
        below++;
        vb = vr;
    }
    if (vc < vb) {
        h[ord] = vb;
        h[below] = vc;
        this.arrange2(below); // 再帰呼び出し
    }
    this.cnt += 2; // 比較回数カウント（合計2回）
};

ソース

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

処理時間の違い（ブラウザ、2つのアルゴリズム）

元の配列は一様分布乱数で、だいたい均等に（例えば要素数1000なら0～1000の整数からランダムに）なっています。測定した処理時間は「配列からヒープへの組み換え」と、正しくヒープになってるかチェックする部分。後者は2つのアルゴリズムで同じなので測る必要なかったですが、うっかり入れてしまったので。PCはCore i5-4300M、メモリ3.5GB（32bitのOS管理分）のノートパソコン。まずChromeで、要素数100万で5回行った結果が下のとおり。

# Chrome Portable 43

type1 check (OK), number of comparisons (1580282), time (40ms)
type2 check (OK), number of comparisons (1591198), time (26ms)

type1 check (OK), number of comparisons (1581731), time (37ms)
type2 check (OK), number of comparisons (1591610), time (27ms)

type1 check (OK), number of comparisons (1582602), time (38ms)
type2 check (OK), number of comparisons (1593392), time (27ms)

type1 check (OK), number of comparisons (1579996), time (39ms)
type2 check (OK), number of comparisons (1591774), time (27ms)

type1 check (OK), number of comparisons (1581640), time (41ms)
type2 check (OK), number of comparisons (1592078), time (27ms)

2番目のアルゴリズムの方が、数値どうしの比較回数は多いものの処理全体で若干速かったです。1番目の方は元配列の先頭要素から1つずつ取り出し、新しい配列の末端に追加してからヒープ用に整形するので、比較回数以外の処理に足を引っ張られるのかも。どちらにしても、ノートパソコンで要素数100万の配列の処理がミリ秒単位というのは驚き。

次にFirefoxは、Chromeと少し違って両アルゴリズムともほぼ同等。1番目のアルゴリズムの処理はChromeより若干速いようです。参考：Gigazineの昨年の記事FirefoxのJavaScriptエンジン「Spidermonkey」がChromeのV8よりも高速に（2014.10.29）。

# Firefox Portable 40

type1 check (OK), number of comparisons (1580740), time (29ms)
type2 check (OK), number of comparisons (1591354), time (30ms)

type1 check (OK), number of comparisons (1580138), time (29ms)
type2 check (OK), number of comparisons (1591682), time (30ms)

type1 check (OK), number of comparisons (1580036), time (28ms)
type2 check (OK), number of comparisons (1591680), time (30ms)

type1 check (OK), number of comparisons (1582423), time (29ms)
type2 check (OK), number of comparisons (1592782), time (29ms)

type1 check (OK), number of comparisons (1581937), time (29ms)
type2 check (OK), number of comparisons (1592318), time (31ms)

最後にIE10は、1番目のアルゴリズムの処理がChrome、Firefoxより倍以上かかりました。それでも数十ミリ秒なので大きな差とは言えないかも。

# Internet Explorer 10

type1 check (OK), number of comparisons (1581624), time (80ms)
type2 check (OK), number of comparisons (1592998), time (32ms)

type1 check (OK), number of comparisons (1580937), time (78ms)
type2 check (OK), number of comparisons (1591616), time (35ms)

type1 check (OK), number of comparisons (1581608), time (75ms)
type2 check (OK), number of comparisons (1592232), time (33ms)

type1 check (OK), number of comparisons (1580717), time (77ms)
type2 check (OK), number of comparisons (1592294), time (33ms)

type1 check (OK), number of comparisons (1582923), time (78ms)
type2 check (OK), number of comparisons (1593666), time (35ms)

いずれにしても、要素数100万の配列をヒープに組み換える処理がミリ秒単位で済むと分かったので、更にソートを加えても結構実用になる気がしてきました。特にChromeのV8エンジンはPL/V8としてPostgreSQLのストアド関数に使えるので、早く試したいです。

初出時（9月8日）からの変更点

1番目のアルゴリズムで、元配列から要素を取り出してヒープの末端に加える際、無駄にArray.shift()して元配列から削除していたのが大きなネックだと分かり、止めました。
2番目のアルゴリズムは不完全だったので全面的に差し替え。
作成したヒープの全ての親子関係が正しいか（ルートに近い方が大きな値か）のチェックを挿入。
上の変更後、各ブラウザで改めてテストし、結果とコメント部分を差し替え。前はアルゴリズム間・ブラウザ間で大きな差が出ていましたが、変更後は大差なく、内容的な面白味は減りました^^;
変更前の内容は不正確で役にも立ちませんが、一応、Bitbucketで履歴は見れます。