最古にして最速?

おそらくプログラムを組んだことがない人でも「誰にも教えられずに」知った「天然の」アルゴリズムの筆頭に来るのがこのバケットソートではないでしょうか。

0. ソートしたいものに適当に番号を振っておく
1. 番号がついたバケツを用意する
2. ソートしたいものの番号がついたバケツにそれを放り込む
3. 必要があればバケツの中身を同じやり方でソートする
4. 番号順にバケツの中身をぶちまける

花札やトランプといった番号が振られたカードを整列させるとき、誰に言われるまでもなく我々はバケツの代わりに「山」を作ってそこにカードを押し込んで行きます。訓練された郵便局員ではないアルバイトでも年賀状の仕分けができるのも、我々が空気のようにこのアルゴリズムを日常で使っているからです。

それでいて、mergesort, quicksort, heapsort といった比較ソートよりも高速なのです。比較ソートにはO(nlogn)という超えられない壁がありますが、比較しないソートであるバケットソートはあっさりそれを凌駕しております。これを手に入れるためなら私は性転換して若返りしてでもQBと契約しちゃうと思いますが、今ではみんな「知っていることさえ忘れている」ほどあまねく利用されているので魔女にならずにすみましたw。

Counting Sort

(追記:2012-1-10) id:m11m さんのコメントによりこのソートはバケットソート*1と呼ばれる既知のソートアルゴリズムであることがわかりました ^^;

その中でも特に簡潔かつ高速なのがcounting sort。番号は要素そのものなのでそのまま使えばよいですし、「バケツに放り込む」のは配列[要素] += 1でいい。rubyの実質一行にはほれぼれしますが、他の言語でもそんなに頑張らなくても書けます。

Perlによる実装

use 5.012;
use List::Util qw/shuffle/;

sub countingsort {
    my @bucket;
    $bucket[$_]++ for @_;
    map { ($_) x $bucket[$_] } 0..@bucket-1;
}

my @random = shuffle 1..42;
say join(",", @random);
say join(",", countingsort @random);
say join(",", sort { $a <=> $b } @random);

JavaScriptによる実装

いきなり++とか出来ない分やや泥臭くなりますが、それでもこの程度。

countingSort = function(src) {
    var tab = [], dst = [];
    src.forEach(function(v) {
        var t = tab[v];
        tab[v] = t ? t + 1 : 1;
    });
    tab.forEach(function(v, i) {
        for (var n = v; n; n--) dst.push(i);
    });
    return dst;
};

var a = shuffle(orderedArray(4, 4));
p(a);
p(countingSort(a)); 

整数のみからなるコレクションをソートするのであればおそらくこれが最強のアルゴリズム。ただし範囲には注意する必要があります。これが0から0xFFFFFFFFFFFFFFFFにあまねく散らばる64bitの整数だったら…

Bucket Sortを汎用化してみる

これほど素晴らしいアルゴリズムなのに、なぜlibcやLL言語の組み込みとして用意されていないのでしょう?理由はいくつか考えられます。

あまりに簡単で都度再発明すればいい?

Counting sortとかならとにかく、汎用品ともなるとそうはいかないでしょう。実際みかけないし…

メモリーをどか食いする?

これが一番大きかったと思われますが、「富豪プログラム」という言葉が登場してもうどれくらい経つのでしょう…

レコードの型が限られる?

確かにCounting Sortに見られるように、バケットソートは整数キーを前提としているところがあります。しかしそれなら何らかの手段でキーを整数化すればいい。radix sortはそうしています。でもキーが数値や文字列でない場合はどうしたものか…

重複キーどうする?

これはバケツの中を再びソートしようとする時に問題になります。バケツが一つだけになった場合、ソート完了していると見なしていいのか否か。radix sortは最長キーの回数だけソートしなおすというやり方でこれを解決していますが、それだと汎用とは言い難い。オブジェクトとかどうしたものか…

そんなことを考えながら、書き下ろしたのが以下です。

bucketSort = function(src, k2i, v2k) {
    if (src.length <= 1) return src;
    k2i = k2i || function(k, d){ return (''+k).charCodeAt(d) || 0 };
    v2k = v2k || function(v){ return v };
    /* first we bundle elements with same keys */
    var valOf = Object.create(null), concat = Array.prototype.concat;
    src.forEach(function(v){
        var k = v2k(v);
        if (valOf[k])   valOf[k].push(v);
        else            valOf[k] = [v];
    });
    return concat.apply([],
        /* then we sort its keys ... */
        (function inner(src, depth){
            var buckets = [];
            /* spread the items into buckets */
            src.forEach(function(v) {
                var i = k2i(v, depth, src);
                if (buckets[i]) buckets[i].push(v);
                else            buckets[i] = [v];
            });
            return concat.apply([], buckets
                .filter(function(v){ return !!v })  /* no empty buckets */
                .map(function(v) {
                    return v.length === 1
                        ?   v 
                        :   inner(v, depth+1) /* recurse if necessary */
                })
            );
         })(Object.keys(valOf), 0)
        /* … and retrieve the values */
        .map(function(k){ return valOf[k]})
    );
};

工夫のしどころは二カ所。一つは。要素からキーを取り出すv2kと、そのキーから番号を取り出すk2iをユーザー指定できるようにしたこと。デフォルトではv2kは値をそのまま返し、k2iは呼び出しの深さに対応する文字のunicode番号を返すようにしてあります。別の言い方をするとMSD radix sortと同じ振るまい。JavaScript(に限らずスクリプト言語の組み込みsortの多く)はデフォルトが辞書順(lexicographic order)なのでそのまま代用できます。

そしてもう一つが、重複キーを持つ要素を一旦連想配列(JavaScriptでは素のオブジェクト)に落とした上で、キーだけをソートしてからそのキーを使って連想配列に格納した要素を取り出していること。こうすることで、「バケツが一個しか使われなかった」状態が一意にソート終了となります。

/* number */
var a = '31415926535897932384626433832795028841972'
    .split('').map(function(d){return +d});
var aa = bucketSort(a), ab = a.concat().sort();
p(a);
p(aa);
p(ab);
p(JSON.stringify(aa) === JSON.stringify(ab));
/* string */
a = Object.keys(window || this);
shuffle(a);
aa = bucketSort(a), ab = a.concat().sort();
p( a.slice(0,4), '…');
p(aa.slice(0,4), '…');
p(ab.slice(0,4), '…');
p(JSON.stringify(aa) === JSON.stringify(ab));
/* object */
a = [
    {name:0, zero:0},
    {name:1, one:1},
    {name:1, one:'single'}, 
    {name:2, two:2},
    {name:2, two:'double'},
    {name:2, two:'duo'},
];
shuffle(a);
aa = bucketSort(
    a, 
    null,                       /* use default indexer */
    function(v){return v.name}  /* key is stored in its .name */
), 
ab = a.concat().sort(function(a, b){ return a.name - b.name });
p(JSON.stringify(a));
p(JSON.stringify(aa));
p(JSON.stringify(ab));
p(JSON.stringify(aa) === JSON.stringify(ab));

ベンチマーク

作ってみて驚いたのは、結構簡単にビルトインを出し抜けたこと。

if (!confirm('It will take a while!')) return;
for (var i = 0; i < 10; i++) (function(n) { setTimeout(function() {
    var s = Math.pow(2, n),
        ary = shuffle(orderedArray(s, s));
        l = ary.length, c = (1 << 18) / l;
    p('ary.length=' + ary.length, 'run=' + c);
    p(' counting:    ', timeit(c, function() {
        countingSort(ary);
    }));
    p(' bucket(lex): ', timeit(c, function() {
        bucketSort(ary);
    }));
    p(' bucket(num): ', timeit(c, function() {
        bucketSort(ary, function(k, d) {return +k });
    }));
    p(' builtin(lex):', timeit(c, function() {
        ary.concat().sort();
    }));
    p(' builtin(num):', timeit(c, function() {
        ary.concat().sort(function(a,b) {return a - b});
    }));
}, 10) })(i);

64の重複キーを持つ64種類のキーを持つ配列(長さ4096)程度でもビルトインより速い。ただしSafariのビルトイン数値ソートはかなり優秀で、上のベンチマーク程度でも出し抜けませんでした。

温故知新の極み

それにしても面白いのは、ソートという分野ではむしろ昔に発見されたアルゴリズムほど高速なこと。明らかに有史以前に発見された bucket sort が未だ最高速で、メモリーが潤沢になった今や quick sort よりよく用いられている merge sort が1945年(by von Neumann. でもそれ以前から見つけていた人はいたはず)。shell sort が1959年(by Shell)で quick sort が 1960年 (by Hoare)。で時は流れ merge sort の改良版 tim sort が2002年で。そして sleep sort (笑)が2010年。

しかも面白いことに、この sleep sort も実は bucket sort の変種なのです。空間ではなく時間をバケツに使った。日本語版Wikipediaも指摘しているとおり(なぜか英語版にはまだない。追記しとくべきか?)

Dan the Bucket Sorter

Auxiliary codes

orderedArray = function(n, d) {
    var dst = [];
    for (var i = 0; i < n; i++) for (j = 0; j < d; j++) dst.push(i);
    return dst;
};

shuffle = function(ary){ /* Fischer-Yates */
    var i, r, t;
    for (i = ary.length - 1; i ; i--){
        r = Math.floor(Math.random() * (i + 1));
        t = ary[r]; ary[r] = ary[i]; ary[i] = t;
    };
    return ary;
};

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