これについてインターネットでいくつかの引用を見ましたが、公式のドキュメントはありませんか? これに関する情報を入手できる場所を誰か教えてもらえますか?
質問する
14786 次
5 に答える
32
これは実装の詳細であるため、文書化する必要はありません。
たとえば、 には複数の実装がSortedDictionaryあります。Microsoft の実装と Mono の実装があります。
実際、Mono の実装では、現在のバージョン (2.10.9) で赤黒ツリーを使用しています。現在の .NET バージョンも同様です (たとえば、ReflectorやMonoDevelopildasm.exeの組み込み IL ビューアーを使用して、コードを逆コンパイルすることで確認できます)。
ただし、実際にはより効率的な実装( B ツリーなど) があるため、これはおそらく将来変更される予定です。
繰り返しになりますが、この情報は役に立たず、実装の詳細であり、高い確率で変更されます。
于 2013-02-16T12:47:25.190 に答える
8
これはMSDNページの公式ドキュメントです。
SortedDictionary ジェネリック クラスは、O(log n) 検索を行う二分探索木です。ここで、n はディクショナリ内の要素の数です。
SortedDictionery は赤黒木ですか?
まあ、私はあまり詳しくありませんが、（無料の）クラスをred-black tree逆コンパイルしただけですが、赤黒ツリーの削除アルゴリズムとSortedDictionaryのRemove（）メソッドのコードは似ていないようです。だから、私のお金はいいえです。SortedDictionarydotPeek
SortedDictionaryキーは常にソートされます。これにより、自分でキーを並べ替える必要がなくなります。ルックアップのパフォーマンスは よりも遅くなりDictionaryます。メモリ内に並べ替えられたルックアップ テーブルが必要な場合に利点があります。
Dictionary lookup time: Close to O(1)
SortedDictionary lookup time: O(log n)
から詳細を確認してくださいhere。
于 2013-02-16T11:45:11.383 に答える
5
ドキュメンテーションは、BST から取得するために O(log n) を保証しているようです。可能性のあるツリーに対して「平均的に」報告している場合、バランスの取れていない実装でもそれを主張できます。最悪の場合の保証であったとしても、これが BST であることと合わせて、逆コンパイルに頼らずに赤黒木として実装されているかどうかを判断するには十分ではありません。また、AVL、スプレイ、またはその他のバランスのとれた種類の可能性もあります。
ドットピークを抜きました。4.0.0.0 システム アセンブリについて。OrderedDictionary は、SortedSet をサブクラス化する Treeset を使用します。これは、赤黒木である可能性が高いようです。ただし、これは、挿入または削除後にバランシングを実装する Web 上の多くの例と同様の典型的な例ではありません。実装は主に反復的であり、挿入は挿入後ではなく途中で色を修正するように見えます (トップダウン - この種のアプローチに関する論文がいくつかあります)。削除に関しても同様のことが起きていましたが、確認する時間がありません。確かに、直接比較できるものではありません。
少なくとも、私の推測では、同様の種類のランタイム特性が必要です。挿入/削除ポイントに到達するまでには、すべてが途中で完了しているため、多くのことはありません。
于 2013-08-23T17:24:27.383 に答える
2
MSDN ページから:
SortedDictionary ジェネリック クラスは、O(log n) 検索を行う二分探索木です。ここで、n はディクショナリ内の要素の数です。
于 2013-02-16T11:41:24.670 に答える
1
逆コンパイルできます（たとえば、リフレクターを使用）...しかし、それは「実装の詳細」であるため、私はそれに依存しません。更新によりいつでも変更できます。
そのような実装の詳細がどれほど関連性があるかはわかりませんが、本当にRedBlackツリーが必要な場合は明示的に実装してください...それ以外は「技術的負債」/「災害が起こるのを待っている」私見です。
于 2013-02-16T11:42:16.970 に答える