読者です 読者をやめる 読者になる 読者になる

山崎屋の技術メモ

IT業界で働く中で、気になること、メモしておきたいことを書いていきます。

javascriptのunshift、shiftは遅すぎる。

私がjs初心者だから知らないだけで、常識なのかも知れないが、ここまで遅いのは驚きでした。

10万回位ループするプログラムを組んでいて、処理時間なんかまったく気にしていなかったら、ぜんぜん返ってこなくて、調べてみたら犯人はキューとして使用していたArrayのshift()だった。

どれくらい遅いのかサンプルで確認しましょう。

<!DOCTYPE html>
<html>
<head>
<script type="text/javascript">
var COUNT=50000;
var arr=[];
var start;
var i;
for(var j=0;j<3;j++){
    start=new Date();
    for(i=0;i<COUNT;i++){
        arr.push(i);
    }
    for(i=0;i<COUNT;i++){
        arr.pop();
    }
    document.write('poshとpop '+COUNT+' 回の時間['+(new Date()-start)+']ミリ秒<br>');

    arr=[];
    start=new Date();
    for(i=0;i<COUNT;i++){
        arr.unshift(i);
    }
    for(i=0;i<COUNT;i++){
        arr.shift();
    }
    document.write('shiftとunshift '+COUNT+' 回の時間['+(new Date()-start)+']ミリ秒<br><br>');
}
</script>
</head>
<body>
</body>
</html>

5万要素、Arrayに値を追加し、同じ回数Arrayから値を取り出します。
push・popの場合とunshift・shiftでそれぞれ時間を計測します。
それを3セット繰り返しています。

実行結果は次のようになりました。

pushとpop 50000 回の時間[25]ミリ秒
shiftとunshift 50000 回の時間[2077]ミリ秒

pushとpop 50000 回の時間[10]ミリ秒
unshiftとshift 50000 回の時間[2159]ミリ秒

pushとpop 50000 回の時間[1]ミリ秒
unshiftとshift 50000 回の時間[2021]ミリ秒

!!!。

この時点でunshift・shiftペアはpush・popペアに比べ、100倍以上の差をあけられています。ただし、2回目以降、push・popペアは明らかにJITコンパイラによる最適化サポートを受けているので、あまり参考になりません。

恐る恐る10万回で試した結果は以下になります。

pushとpop 100000 回の時間[73]ミリ秒
unshiftとshift 100000 回の時間[11288]ミリ秒

pushとpop 100000 回の時間[9]ミリ秒
unshiftとshift 100000 回の時間[10812]ミリ秒

pushとpop 100000 回の時間[2]ミリ秒
unshiftとshift 100000 回の時間[11173]ミリ秒

さらに差は開いて150倍以上になりました。

javascriptでキューを使いたいとき、Arrayを使えば楽だと安易に考えると痛い目にあうことがあるので気を付けましょう。