データ構造のJavaScriptにおける実際

結論から書くとLinked ListはO(1)の操作を大量に行わない限りArrayの方が圧倒的に早く、Setに負けることすらある。Treeでも要素数1000以下では.indexOfが速すぎてArrayのほうが速い可能性が高い(特にHeap)。

まずオブジェクトの生成の時点でListは大幅に遅く不利でありこの出だしの遅れを操作コストの優位で挽回する形となるため基本的に生成コストの差でArrayのほうが圧倒的に速く、Setに追いつくのにすら数回の操作を要する(生成を直接測定するとArrayの4分の1程度の速度だが他のオブジェクト内だと最適化が外れて大幅に速度低下しやすい?)。 またListはループ系構文の遅さから走査が遅いため原則として要素の最後の取り出し以外でO(n)の操作を行ってはならない。 具体的には要素数1000程度のArrayの.indexOfによる走査速度は要素の参照のような単純な式や文と同等から10分の1程度という驚異的な速さだが素朴にループを回すと単純にループ回数に比例した時間がかかり100〜1000倍近い時間を要する。 逆に要素数がほとんどの場合1,2個程度かつ任意の要素を削除可能なキューとしてはSetがArrayより2倍以上速い(意味がわからない)場合があり5個程度で逆転する。 ライフサイクル全体で見ればLinked Listは静的なStackやQueueなどごく少数の用途において最速となるのみであり、原則として最大限Arrayに適した設計をしArrayを使うよう努力することがその他の適切なデータ構造の選択に勝る。 Tree構造も同じ根本的問題を共有していることからArrayを置換できる用途は限定的であると思われる。対数時間で走査できるようTree構造を実装しても要素数1000以下であればArrayで.indexOfしたほうが速いだろう。 さらに廃棄されたオブジェクトがGCにかける負荷も実際の最適化では重要な考慮事項となり廃棄オブジェクトの参照のされ方の考慮や参照の明示的な削除を行わなければGCの負荷で実行速度が2〜4分の1に低下する場合がある。 こうした問題は内部で最適化されたビルトインAPIとの実行性能の格差に由来することからチューニング済みのビルトインの標準ライブラリが提供されれば理論上適したデータ構造を実際に採用して実行速度を向上させられるようになるだろう。

追記 indexOfで実際のコードを高速化しようとするとうまくいかない。単体ベンチマークのスコアはメモリ上の局所性によるもので他の処理が挟まると局所性が失われるからかもしれない。しかし多少はループより速い。参照削除の効果は実コードでも明瞭に確認できる。