118

JavaScriptの配列は、アイテムを追加および削除することで非常に簡単に変更できます。ほとんどの言語の配列が固定サイズであり、サイズを変更するには複雑な操作が必要であるという事実をいくらか覆い隠しています。JavaScriptを使用すると、パフォーマンスの低い配列コードを簡単に記述できるようです。これは質問につながります：

配列のパフォーマンスに関して、JavaScriptの実装からどのようなパフォーマンス（時間の複雑さの点で）を期待できますか？

私は、すべての合理的なJavaScript実装には、せいぜい次の大きなOがあると思います。

  • アクセス-O（1）
  • 追加-O（n）
  • プリペンディング-O（n）
  • 挿入-O（n）
  • 削除-O（n）
  • スワッピング-O（1）

new Array(length)JavaScriptを使用すると、構文を使用して、配列を特定のサイズに事前入力できます。（ボーナス質問：この方法で配列を作成していますかO（1）またはO（n））これは従来の配列に似ており、事前サイズの配列として使用すると、O（1）を追加できます。循環バッファロジックを追加すると、O（1）の先頭に追加できます。動的に拡張する配列を使用する場合、O（log n）は両方の平均的なケースになります。

ここでの私の仮定よりもいくつかのことでより良いパフォーマンスを期待できますか？仕様に何も概説されていないと思いますが、実際には、すべての主要な実装が舞台裏で最適化されたアレイを使用している可能性があります。動的に拡張するアレイやその他のパフォーマンスを向上させるアルゴリズムが機能していますか？

PS

私がこれを不思議に思っている理由は、私がいくつかのソートアルゴリズムを研究しているためです。それらのほとんどは、全体的な大きなOを記述するときに、追加と削除がO（1）操作であると想定しているようです。

4

2 に答える 2

124

注：この回答は2012年には正しかったのですが、現在、エンジンはオブジェクトと配列の両方に非常に異なる内部表現を使用しています。この答えは正しい場合とそうでない場合があります。

Javascriptで配列を使用して配列を実装するほとんどの言語とは対照的に、配列はオブジェクトであり、値は通常のオブジェクト値と同じようにハッシュテーブルに格納されます。そのような：

  • アクセス-O（1）
  • 追加-償却O（1）（ハッシュテーブルのサイズ変更が必要な場合があります。通常は挿入のみが必要です）
  • unshift接頭辞-すべてのインデックスを再割り当てする必要があるため、を介してO（n）
  • 挿入-値が存在しない場合は、O（1）を償却します。O（n）既存の値をシフトする場合（たとえば、を使用splice）。
  • 削除-値を削除するために償却されたO（1）、。を介してインデックスを再割り当てする場合はO（n）splice。
  • スワッピング-O（1）

一般に、dictのキーの設定または設定解除は、償却されたO（1）であり、インデックスが何であるかに関係なく、配列にも同じことが当てはまります。影響を受けるすべての値を更新する必要があるという理由だけで、既存の値の番号を付け直す必要がある操作はすべてO（n）です。

于 2012-07-18T06:01:59.867 に答える
3

保証

配列操作には、指定された時間計算量の保証はありません。アレイのパフォーマンスは、エンジンが選択する基礎となるデータ構造によって異なります。エンジンはまた、異なる表現を持ち、特定のヒューリスティックに応じてそれらを切り替える場合があります。初期配列サイズは、そのようなヒューリスティックである場合とそうでない場合があります。

現実

たとえば、V8は（現在）ハッシュテーブルと配列リストの両方を使用して配列を表します。また、オブジェクトのさまざまな表現があるため、配列とオブジェクトを比較することはできません。したがって、配列アクセスは常にO（n）よりも優れており、C++配列アクセスと同じくらい高速である可能性もあります。データ構造のサイズに達し、スケーリングする必要がある場合（O（n））を除いて、追加はO（1）です。プリペンディングはさらに悪いです。delete array[index]エンジンがその表現を変更することを余儀なくされる可能性があるため、（しないでください！）のようなことを行うと、削除はさらに悪化する可能性があります。

助言

数値データ構造には配列を使用します。それが彼らの意図です。それがエンジンがそれらを最適化するものです。スパース配列は避けてください（または、必要な場合は、パフォーマンスの低下を期待してください）。データ型が混在する配列は避けてください（内部表現がより複雑になるため）。

特定のエンジン（およびバージョン）を本当に最適化したい場合は、そのソースコードで絶対的な答えを確認してください。

于 2020-05-10T14:16:08.480 に答える