asin:4894712369
珠玉のプログラミング
Jon Bentley / 小林健一郎訳

ぐぬぅ。男子ゆえ女子をこじらせようがないとはいえ、風邪が普通にこじれている。

というわけでアルゴリズムのことなどつらつら考えていた。

要はソートすべき配列中にすでに存在する秩序を活用するのがtimsortなのだと。

だけどすでにソート済みの配列を活用するなら、こういう方法もありではというわけでentry。

If it ain't broke, don't fix it.

ソート済みの配列に要素を加えるなら、要素を加えてからソートするよりもどこに要素を加えるか調べてからそこに要素を挿入した方が速いはず。

というわけでJavaScriptによる実例。

万能な二分探索

まず下準備として「万能な」二分探索を実装してみます。

binsearch = function(ary, val, cmp) {
    cmp = cmp || function(a, b) { return a === b ? 0 : a < b ? -1 : 1 };
    var head = 0,
        tail = ary.length - 1,
        here, that, h, m, t;
    while (head <= tail) {
        here = head + ((tail - head) >> 1);
        that = cmp(ary[here], val);
        if (0 === that) {   /* if found, binary-search the boundary */
            h = 0, t = here;
            while (h <= t) {
                m = h + ((t - h) >> 1);
                if (0 === cmp(ary[m], val)) t = m - 1;
                else                        h = m + 1;
            }
            head = h;
            h = here, t = ary.length;
            while (h <= t) {
                m = h + ((t - h) >> 1);
                if (0 === cmp(ary[m], val)) h = m + 1;
                else                        t = m - 1;
            }
            tail = t;
            return { found: true, head: head, tail: tail };
        }
        if (0 < that) tail = here - 1;
        else          head = here + 1;
    }
    return { found: false, head: tail, tail: head };
};

s = binsearch(ary, val [,cmp]);
s.found がtrueつまり見つかった場合
s.headはvalと一致する最初のindex
s.tailはvalと一致する最後のindex
s.foundがfalseつまり見つからなかった場合
s.headはval < ary[index]となる最後のindex
s.tailはval > ary[index]となる最初のindex

これで重複したキーを持つ配列の場合は見つかった範囲を返し、値が見つからなかった場合でも値を挿入するとしたらどこに挿入すればよいかがわかります。

var fill = function(v, l) {
    for (var a = [], i = 0; i < l; i++) { a.push(v) } return a;
};
var ncmp = 0,
    cmp = function(a,b) {ncmp++; return a - b},
    ary = fill(0, 1e6).concat([1]).concat(fill(2, 1e6)).concat([3]);
p(ary.length);
ncmp = 0; p(JSON.stringify(binsearch(ary, 0.5, cmp)) , ncmp);
ncmp = 0; p(JSON.stringify(binsearch(ary, 0, cmp)) , ncmp);
ncmp = 0; p(JSON.stringify(binsearch(ary, 1, cmp)) , ncmp);
ncmp = 0; p(JSON.stringify(binsearch(ary, 2, cmp)) , ncmp);
ncmp = 0; p(JSON.stringify(binsearch(ary, 3, cmp)) , ncmp);





ベンチマークしてみると、要素数が3桁なら線形探索しているbuiltinのindexOfやlastIndexOfよりほぼ確実に高速になります。




var fill = function(v, l) {
    for (var a = [], i = 0; i < l; i++) { a.push(v) } return a;
};
for (var i = 0; i < 7; i++) (function(n) { setTimeout(function() {
    var size = Math.pow(10, n),
        ary = fill(0, size).concat([1]).concat(fill(2, size)).concat([3]);
    p('ary.length=' + ary.length, 'run=' + 1e6 / size);
    p(' binsearch:  ', timeit(1e6 / size, function() {binsearch(ary, 0.5)}));
    p(' indexOf:    ', timeit(1e6 / size, function() {ary.indexOf(0.5)}));
    p(' lastIndexOf:', timeit(1e6 / size, function() {ary.lastIndexOf(0.5)}));
    p(' binsearch:  ', timeit(1e6 / size, function() {binsearch(ary, 1)}));
    p(' indexOf:    ', timeit(1e6 / size, function() {ary.indexOf(1)}));
    p(' lastIndexOf:', timeit(1e6 / size, function() {ary.lastIndexOf(1)}));
}, 0) })(i);





値を挿入する


ここまで来れば、挿入は簡単です。


insert = function(ary, val, cmp) {
    var s = binsearch(ary, val, cmp),
        i = s.found ? s.tail + 1 : s.tail;
    ary.splice(i, 0, val);
    return i;
};



実際にやってみましょう。




var ary = [1, 2];
p(insert(ary, 0.5));
p(insert(ary, 1.5));
p(insert(ary, 2.5));
p(ary);
var cmp = function(a, b) { return a[0] - b[0] };
ary = [[1, 'one'], [2, 'two']];
p(insert(ary, [0.5, 'half'], cmp));
p(insert(ary, [1.5, 'one+half'], cmp));
p(insert(ary, [2.5, 'two+half'], cmp));
p(insert(ary, [2, 'double'], cmp));
p(insert(ary, [1, 'single'], cmp));
p(insert(ary, [1, 'solo'], cmp));
p(JSON.stringify(ary));





ベンチマークしてみると、値を追加してから全体をソートするよりずっと高速なことがわかります。




var ordered = function(h, t) {
    var a = [];
    for (var i = h; i <= t; i++) a.push(i);
    return a;
};
var ncmp = 0,
    cmp = function(a, b) { ncmp++; return a - b },
    aa, ab;
ncmp = 0, aa = ordered(1, 100e3);
p(timeit(1, function() { insert(aa, 50e3, cmp) }), ncmp);
ncmp = 0, ab = ordered(1, 100e3);
p(timeit(1, function() { ab.push(50e3); ab.sort(cmp) }), ncmp);
p(JSON.stringify(aa) === JSON.stringify(ab));





おまけ


以下のようなことは出来ますが、もちろん翡翠賞。




var insertionSort = function(ary, cmp) {
    var ret = [], i, l = ary.length;
    for (i = 0; i < l; i++) insert(ret, ary[i], cmp);
    return ret;
};
var randomArray = function(n) {
    for (var a = []; n; n--) {a.push(Math.random())} return a;
};
var ncmp = 0,
    cmp = function(a, b) { ncmp++; return a - b },
    ar = randomArray(10e3),
    aa, ab;
ncmp = 0, aa = ar.concat();
p(timeit(1, function() { aa = insertionSort(aa, cmp) }), ncmp);
ncmp = 0, ab = ar.concat();
p(timeit(1, function() { ab.sort(cmp) }), ncmp);
p(JSON.stringify(aa) === JSON.stringify(ab));





ところでJavaScriptのArray.prototype.sortはなぜ破壊的になったんでしょうねえ。perlもrubyも非破壊的なのに。あ、pythonは破壊的か(merge sortの変種であるtimsortを採用しているのに)。いちおうpythonにも非破壊的なsortedがあるし、rubyにも破壊的なArray#sort!がありはするけど…


Dan the Man with too Much Data to Sort


Auxiliary codes


timeit = function(l, f) {
    var i, started = Date.now();
    for (i = 0; i < l; i++) f();
    return Date.now() - started + 'ms';
}