2006年11月23日 14:45 [Edit]

javascript - Array#sortがオレquicksortより遅い!?

な、なんだってー!?

ごっつええブログ - JavaScriptによるソートアルゴリズムの比較実験
『JavaScriptを使って一定以上の数量をもった数値配列をソートする場合は、組み込みメソッドよりもクイックソートを使用したほうが高速である』

自分でも検証してみた。


どうやらMozilla系列のJavaScript実装に関しては嘘ではないらしい。以下で確認してほしい。

Firefox 2に関してはほぼ同等だが、Mac IE 5, Safari 2.0.4, Opera 9.02ではbuiltinの方が速かった。しかしその差は最も大きかったSafariでも3倍程度で、builtinとしてはやはり遅いように見える。

# of Items:

検証用ソース一式
<script>
function SortBench(n){
    function $(id){ return document.getElementById(id) }
    this.random_array = function(n){
        var result = [0];
        while(--n) result[n] = n; // sorted array
        n = result.length;
        while (--n) {             // Fisher-Yates Suffle
            var m = Math.floor(Math.random() * (n + 1));
            if (n == m) continue;
            var k = result[n];
            result[n] = result[m];
            result[m] = k;
        }
        return result;
    };
    this.init = function(n){
        this.seed  = this.random_array(n || 1024);
    }
    var ncmp = function(a,b){ return a - b };
    this.timeit = function(sorter){
        var ary = Array.apply(null, this.seed);   // clone via mala's hack
        var elapsed = (new Date).getTime();
        sorter(ary) // where sorter is DISTRUCTIVE sort
        elapsed =  (new Date).getTime() - elapsed;
        return elapsed;
    }
    this.builtin_sort = function(ary){ ary.sort(ncmp) };
    var qsort = function(ary, cmp){
        function q(ary, head, tail) {
            var pivot = ary[parseInt( head +  (tail - head)/2 )];
            var i = head - 1;
            var j = tail + 1;
            while (1){
                while (cmp(ary[++i], pivot) < 0);
                while (cmp(ary[--j], pivot) > 0);
                if (i >= j) break;
                var tmp = ary[i];
                ary[i] = ary[j];
                ary[j] = tmp;
            }
            if (head < i - 1) q(ary, head, i - 1);
            if (j + 1 < tail) q(ary, j + 1, tail);
            return ary;
        }
        return q(ary, 0, ary.length - 1);
    }
    this.quick_sort = function(ary){
        qsort(ary, ncmp);
    }
    this.run = function(){
        this.init( $('nitems').value );
        $('log').innerHTML = 
            'Sorting Random Array with ' + this.seed.length + ' items.<br/>';        
        $('log').innerHTML += 
            'Builtin: ' + this.timeit(this.builtin_sort) + 'ms<br/>';
        $('log').innerHTML += 
            'Quicksort: ' + this.timeit(this.quick_sort) + 'ms<br/>';
    }
    this.init(n);
};
var sb = new SortBench();
</script>
<div style="border:dotted 1px; padding: 0.5em">
# of Items: <input id="nitems" type="text" value="10000" size="5" maxlength="5">
<input type="submit" value="start" onclick="sb.run()">
<pre id="log"></pre>
</div>

取り急ぎ以上。

Dan the Surprised JavaScripter

追記:Spidermonkeyでも同様の結果が。

js> load('sortbench.js')       
js> var sb = new SortBench()   
js> sb.init(10000)             
js> sb.timeit(sb.builtin_sort)
521
js> sb.timeit(sb.quick_sort)   
411

ちなみにMozilla系のArray#sortは以下でソースを見ることも可能。

seamonkey/js/src/jsarray.c
1050 static JSBool 1051 array_sort(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)

コメントには"Perl-inspired"とあって使っているのはmerge sortなのだけど、なぜこんなに遅いのか、これだけじゃまだわからないなあ。

追記2:

ちなみに、Perlの例。

% perl sortbench.pl 10000                 Benchmark: running builtin, quicksort for at least 3 CPU seconds...
   builtin:  3 wallclock secs ( 3.12 usr +  0.02 sys =  3.14 CPU) @ 38.54/s (n=121)
 quicksort:  3 wallclock secs ( 3.01 usr +  0.00 sys =  3.01 CPU) @  3.99/s (n=12)
            Rate quicksort   builtin
quicksort 3.99/s        --      -90%
builtin   38.5/s      867%        --
#!/usr/local/bin/perl
use strict;
use warnings;
use Benchmark qw/timethese cmpthese/;
use List::Util qw/shuffle/;

sub qsort(@&){
    my ($aref, $cref) = @_;
    my $q;
    $q = sub{
        my ($head, $tail) = @_;
        my $pivot = $aref->[int($head + ($tail - $head)/2)];
        my $i = $head - 1;
        my $j = $tail + 1;
        while(1){
            1 while($cref->($aref->[++$i], $pivot) < 0);
            1 while($cref->($aref->[--$j], $pivot) > 0);
            last if ($i >= $j);
            ($aref->[$i], $aref->[$j]) = ($aref->[$j], $aref->[$i]);
        }
        $q->($head, $i - 1) if ($head < $i - 1);
        $q->($j + 1, $tail) if ($j + 1 < $tail);
        return $aref;
    };
    return $q->(0, scalar(@$aref)-1);
}

my $nelem = shift || 1000;
my @seed = shuffle (1..$nelem);

cmpthese(timethese(0,{
                       builtin => sub {
                           my @a = @seed;
                           @a = sort { $a -  $b } @a;
                       },
                       quicksort => sub{
                           my @a = @seed;
                           qsort(\@a, sub{ $_[0] - $_[1] })
                       }
}));

この記事へのトラックバックURL

この記事へのトラックバック
その後のブラウザーの進化も凄まじいので、改めてベンチマークとってみたら以外な事実が。 404 Blog Not Found:javascript - Array#sortがオレquicksortより遅い!?Firefox 2に関してはほぼ同等だが、Mac IE 5, Safari 2.0.4, Opera 9.02ではbuiltinの方が速かった。しかしそ...
javascript - Array#sortはオレquicksortより遅い by Chrome【404 Blog Not Found】at 2009年02月26日 17:07
livedoor Blogを私が愛用しつづけている理由のひとつが、JavaScriptを受け付けること。 おかげでかなりのentriesが溜まりましたが、それだけにで実行用のソースと表示用のソースを用意するのが人一倍おっくうに感じられます。そんなわけで、どうやれば怠慢をもっと発揮でき....
javascript - ソースを見せてかつ動かすための3つのtips【404 Blog Not Found】at 2009年02月24日 04:45
404 Blog Not Found:javascript - Array#sortがオレquicksortより遅い!?はちょっとした驚きですが、実はデータの種類さえ限定できれば、builtin sortを出し抜くことはJavaScriptでなくてもそれほど難しくありません。
Algorithm - O(n log(n))より速いsort【404 Blog Not Found】at 2006年12月03日 01:53
組み込み機能を実装し直す必要はないはずです、ふつうは。簡単なアルゴリズムでも、パ...
組み込み機能を実装し直す必要は?【{informa,computa,evolu}tion】at 2006年11月25日 23:58
JavaScriptのビルドインソートは自前で実装するクイックソートより遅いらしい Blog Not Found javascript - Array#sortがオレquicksortより遅い!?どうやらMozilla系列のJavaScript実装に関しては嘘ではないらしい。以下で確認してほしい。 Firefox 2に関してはほぼ同等だが、...
JavaScriptのソート【enchanting an air of joyous bliss】at 2006年11月24日 12:35
いい機会なのでPerl 5.8のsortプラグマを紹介。 sawatの日記遅いのはマージソートだからでいいのでは?
perl - use sort;【404 Blog Not Found】at 2006年11月23日 17:14
この記事へのコメント
https://bugzilla.mozilla.org/show_bug.cgi?id=224128
https://bugzilla.mozilla.org/show_bug.cgi?id=143354
この辺を見ると、SpiderMonkey の組み込みソートは数値より文字列のソートを高速になるようにしているので、文字列のテストもお願いします。
Posted by mal at 2006年11月24日 18:38
まさかPure Javascriptで作り直した方が速いとは…
ところでquicksortは再帰部分を展開できたと思うのですが、それだとさらにどれぐらい速くなるんでしょうか?
Posted by 【えぬ】 at 2006年11月24日 06:32
zorioさん、
すみません。scratch版をpasteしちゃったようです。差し替えました。
Dan the Man to Err
Posted by at 2006年11月23日 18:01
Quick Sortと書いてある方も、組み込みのSortをしてるように見えるのですが。
Posted by zorio at 2006年11月23日 17:31