ES6 コレクション: 線形時間計算量は必須ですか?

ES6 仕様では、Set、Map、WeakSet、WeakMap などのキー付きコレクションが導入されています。これらのコレクションは、キーに基づいてデータを保存および取得する効率的な方法を提供します。ただし、疑問が生じます: 仕様では、これらのコレクションに対する操作に対して線形時間計算量が義務付けられていますか?

線形時間計算量またはアルゴリズム選択はオープンのままです

期待にもかかわらずSet および Map プロトタイプに対する O(1) アクセスなどの広く受け入れられているパフォーマンス アルゴリズムですが、ES6 仕様は驚くべきことに線形時間への扉を開いたままにしています。アルゴリズム.

仕様には、「セット オブジェクトは、平均してサブリニアなアクセス時間を提供する [メカニズム] を使用して実装する必要がある」と記載されています。この言語は、線形時間アルゴリズムを含むと解釈できます。ただし、それらを明示的に義務付けるものではありません。

同様に、仕様では、対数的な時間計算量を提供する、ハッシュ テーブルやバランス ツリーなどのよりパフォーマンスの高いアルゴリズムを除外していません。

明示的なパフォーマンス義務

仕様に明示的なパフォーマンス義務がないため、この仕様に期待していた開発者の間で眉をひそめています。

ただし、この仕様は、予測可能な反復順序など、観察可能なセマンティクスに焦点を当てていることに注意することが重要です。効率的なハッシュベースの実装が広く期待されていますが、仕様では、対数的な時間計算量を提供するツリーのような代替データ構造が許可されています。

結論

ES6 仕様では、キー付きコレクションに対する操作の線形時間計算量は明示的には義務付けられていません。一部の実装では線形時間アルゴリズムが観察可能ですが、仕様にはよりパフォーマンスの高い実装の余地が残されています。開発者は、さまざまなコンテキストにおけるこれらの収集操作の実際の時間の複雑さを理解するために、特定のブラウザーまたはランタイムのドキュメントを参照する必要があります。