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

連結リスト(LinkedList)のベンチマーク

JavaScript

LinkedListは一言で言えば数珠繋ぎになったデータです。定義的には色々種類がありますが、今回は配列の代わりに順番にデータにアクセスする方法として使用します。具体的にはこういうことです。

function linkloop(){
  var n = first;
  do{
    // n
  } while ((n = n.next))
}

まず1つ目の要素を処理、1つ目から2つ目を参照して2つ目の要素を処理、とnextで繋がっているだけループが続くという簡単な仕組みです。
clockmakerさんのParticle 3000 - jsdo.it - Share JavaScript, HTML5 and CSSでLinkedListが使われていたのですが、forkする際になんとなくLinkedListを避け(型のないJavaScriptでは配列の方が速そうに思えたので)ました。で、その勘が本当に合ってるのか検証してみました。

loop benchmark - jsdo.it - Share JavaScript, HTML5 and CSS
結果はまあまあ予想通りで、最近のブラウザは配列へのアクセスがかなり最適化されているみたいなので、普通に配列を走査した方が良さそうです。ただ、IEはバージョンが古くなるほどLinkedListのほうが高速という…。
ただ、こういう微小な差しかないベンチマークは正しい結果がでているのか、怪しいところがあります。ちょっと条件を変えただけで全然結果が違ったりするかもしれないので、参考程度に見てください。
ちなみに、ChromeはLinkedListが割と高速で、特にコンストラクタでnextを用意しておくかどうかで速さが微妙に違います。コンストラクタで作ったプロパティにはJITが効きやすいみたいなのがありそうな感じです(ないかもしれないけど)。