たとえばの機能を備えたデータ構造を探しています。つまり、要素の順序を維持OrderedDictionaryする連想コレクション (つまり、キーを値Listに関連付けるもの) です (通常のように)。
インデックスとキーの両方による高速検索が必要です。また、高速な「追加」操作 (最後に新しいアイテムを挿入する) と、任意のインデックス (インデックスまたはキーに基づく) を使用したアイテムの高速削除も必要です。
OrderedDictionary私が間違っていなければ、.NET ではハッシュ テーブルと配列の両方を使用してアイテムを格納します。したがって、キーに基づいてインデックスを取得すること (またはその逆) はO(n)であり、もちろん、配列の途中から項目を削除することは、最初はO(n)であり、加えて、キーで取り外す場合はキー。
私の質問は、私の条件を満たすより効率的なデータ構造が存在するかどうか、またはこれが本当に私の最良の選択肢であるかどうかです。
これは 2 つの赤黒ツリーで実行できると思います: 比較関数によって並べ替えられたキーを格納するキー ルックアップ ツリーと、リストのようにキーを任意の順序で並べたインデックス ルックアップ ツリーです。各インデックス ルックアップ ノードには「サイズ」フィールドが必要です。各ノードに「サイズ」フィールドが含まれている場合、赤黒ツリーはインデックスによるルックアップを実行できます。たとえば、C5 Generic Collection Libraryの RedBlackTreeSet 実装を参照してください。
キー ルックアップ ツリーの各エントリには、インデックス ルックアップ ツリー内の対応するエントリへのポインタが必要です。左ノード ポインタと右ノード ポインタと同様に、インデックス ルックアップ ツリーには、ボトム ツーを許可する親ポインタ フィールドが必要です。 -トップ ナビゲーションとトップ ツー ボトム。
全体として、各キーには 6 つのポインターが必要です。両方のノードの通常の左右のポインターに加えて、key-lookup-node から index-lookup-node へのポインター、さらに各 index-lookup の親ポインターです。 -ノード。保存された値を指すために、各ノードにポインターも必要です。
オペレーション：
追加 - 追加操作は、両方のツリーにキーを挿入します。1 回目はキー ルックアップ ツリー、比較関数によって決定された位置、2 回目はインデックス ルックアップ ツリーの右端の位置です。赤黒木への挿入は、対数時間演算です。
キーによるルックアップ - これはキールックアップ ツリーで行われ、比較関数を使用して正しい位置を見つけます - O(log(n))
インデックスによるルックアップ - これは、前述のように、インデックス ルックアップ フィールドで実行できます - O(log(n))
キーからインデックスを取得 - 最初にキー検索ツリー O(log(n)) でキーを検索します。インデックス ルックアップ ツリーまでポインタをたどります。ルート ノード (バランス ツリーの場合は O(log(n))) まで親ポインタをたどります。途中で「サイズ」フィールドを使用して、キーのインデックスを決定します。- O(log(n)) 全体。
インデックスによる削除 - インデックス ルックアップ ツリーでアイテムをルックアップします。インデックス ルックアップ ツリーから削除します。キー検索ツリーで見つかったキーを検索します。キー検索ツリーから削除します。すべての操作は O(log(n)) であるため、削除は全体で O(log(n)) です。
キーで削除 - 「キーからインデックスを取得」を使用して、キーのインデックスを取得します。インデックス ルックアップ ツリーからインデックスごとに削除します。キー検索ツリーからキーごとに削除します。O(log(n)) 全体。
この構造は、最後だけでなく、任意の位置での O(log(n)) 挿入もサポートします。
ストレージのオーバーヘッドは明らかにかなりのものですが、O(n) のままです。時間の複雑さはすべての要件を満たしています。
残念ながら、私はこの構造の実装を認識していません。
更新: ツリーとハッシュ テーブルを組み合わせて、O(1) キーによるルックアップを取得できることがわかりました。上記のように 2 つのツリーを使用する代わりに、キーによる検索にはハッシュ テーブルを使用し、位置による検索にはバランスの取れた順序統計ツリーを使用しますが、ハッシュ テーブルのスロットには次へのポインターを含めます。 get-list-position-by-key 検索を行うためのバランス ツリーのノード。キーによるルックアップは O(1) になり、それ以外は平均して O(ln(n)) のままです。もちろん、他のハッシュ テーブルと同様に、時折 O(n) 再ハッシュ ペナルティが発生します。
OrderedDictionary は実際にあなたの要件を満たしてくれます。
OrderedDictionary の分析は正しくありません。thisによると、実際にはキーベースのルックアップの場合は O(1) 、インデックスの場合は O(1) です。
単純な分析でも、キーまたはインデックスによる O(1) ルックアップが得られます。配列は O(1) アクセスを提供し、ハッシュ テーブルは実質的に O(1) アクセスを提供します。
挿入/削除はもう少し複雑ですが、償却分析はまだ O(1) です
この記事では、挿入と削除は O(n) であると主張しています。償却分析により、特定の要素を挿入する「コスト」を1から2に単純に引き上げることができるため、これは少なくとも挿入には当てはまりません。配列のサイズ変更を必要とする要素を挿入する場合、コストの後半は支払うために使用されますコピーのコスト。最終的な挿入には時間がかかりますが、それでも O(1) は償却され、不一致は配列のサイズ変更が発生する可能性が低い場合にのみ現れます。
リンクのように平衡二分探索木を使用できます。TreeNodeの定義ではキーを追加する必要がありますが、問題は要素がO（1）ではなく、キーとインデックスの両方でO（log（n））であることです（実際、インデックスはTreeNodeの一部ではなく、比較的見つけることができます）が、すべての操作はO（log（n））であり、比較方法に基づく最も高速な既知の方法です。