javascript - 対数検索時間を持つ JavaScript セットのデータ構造

Question

重複の可能性:
Javascript に Set データ型のライブラリはありますか?

C++ セットを模倣する JavaScript データ構造を作成する方法はありますか? log(n) 時間で検索を実行する必要がありますが、うまく機能する言語が見つかりません。セットをオブジェクトとして表現する必要があるという質問をいくつか見ました。それはうまくいきますか？配列のキーとペイロードは数値です。

Answer 1

順序付けられていないセットの場合は、おそらくハッシュ テーブルを実装したほうがよいでしょう。これらは、ハッシュ テーブルが過負荷にならない限り、O(1) ルックアップを行います。

順序付けられたメモリ内セットの場合、標準的な答えは、treaps (平均時間は良好、標準偏差は高い) と赤黒木 (平均時間は低く、標準偏差は低い) のようです。これらは両方とも O(logn) ルックアップです。

Answer 2

順序集合（定義した順序で最小要素から最大要素にループできる）が必要な場合は、JSで独自のデータ構造を実装できます。私はこれを直接行ったことがないので、これについてこれ以上の情報を与えることはできません。

順序付けされていないセットに満足している場合は、次のように実装できます。

1. セットに格納されるオブジェクトの正規化された文字列表現を定義します。数字のセットが必要な場合は、数字の文字列表現を使用してください。ユーザー定義オブジェクトのセットが必要な場合は、オブジェクトのIDを定義するプロパティを選択し、それらを正規化された文字列表現で使用できます。
2. 正規化された文字列表現を実際のオブジェクトにマッピングすることにより、セットとして使用するJSオブジェクトを作成します。
3. 文字列表現でプロパティ名を確認することで検索できます。
4. セットへの挿入は、次の方法で実行できます。まず、検索によって文字列表現がすでに存在するかどうかを確認し、次に、オブジェクトがまだセットにない場合は、文字列表現を実際のオブジェクトにマップします。
5. 削除は、を使用して実行できますdelete。プロパティ名は、削除するオブジェクトの文字列表現です。

Answer 3

JavaScript では、すべてがオブジェクトである必要があります。