Array関数のJavaScript実行時の複雑さ

質問

JS規格で定義されているランタイムの複雑さは、一般的な Array のような関数で push , pop , shift , slice または splice ? Esp.私はランダムな位置でエントリを削除および挿入することに興味があります。複雑さが定義されていない場合、私は、例えば、V8で何を期待できますか？

(この質問は この . また このベンチマーク を掲載しました。 ここに も気になりますが、関係ない現象かもしれません)

(非常に関連した質問として はこちら . しかし、受理された回答に対するコメントの1つに、今は間違っていると書かれています。また、採用された回答には、規格が本当にそのように定義しているのかについての言及はありません)。

どのように解決するのですか?

ECMA仕様では、境界のある複雑さは指定されていませんが、仕様のアルゴリズムから導き出すことができます。

push は O(1) となりますが、実際には O(N) コピーコストは、スロット配列が再割り当てされる必要があるため、エンジンで定義された境界で発生します。これらの境界は通常対数です。

pop は O(1) と同じような注意点があり push と同じですが O(N) のコピーは、しばしばガベージコレクションに折り込まれるため、めったに遭遇しません（たとえば、コピーコレクターは配列の使用部分のみをコピーすることができます）。

shift は最悪の場合 O(N) として実装できますが、特別な場合には O(1) として実装することも可能ですが、インデックス作成の速度を落とすという代償を払うことになります。

slice は O(N) ここで N は end - start . 両方の配列への書き込みを大幅に遅くすることなく、ここでの最適化の機会はそれほど多くはありません。

splice は、最悪の場合 O(N) . を分割するアレイストレージ技術があります。 N を定数で割る配列ストレージ技術がありますが、これらはインデックスの作成を著しく遅くしてしまいます。エンジンがこのような技術を使用する場合、アクセス パターンの変更によってストレージ技術を切り替えるので、異常に遅いオペレーションに気づくかもしれません。

あなたが言及しなかったもののひとつは sort . これは、平均的なケースで O(N log N) . しかし、エンジンが選択したアルゴリズムによっては、次のようになります。 O(N^2) を得ることができる場合があります。たとえば、エンジンが QuickSort を使用する場合（InsertionSort へのレイトアウトがあっても）、よく知られているように N^2 のケースがあります。これはアプリケーションの DoS の原因となる可能性があります。これが懸念される場合、ソートする配列のサイズを制限するか（多分、サブ配列をマージする）、HeapSortに救済されます。