c# - ツリーとディクショナリの妥当なサイズ

Question

現在、リクエストごとに再処理するのではなく、ほぼ瞬時にデータにアクセスできるように、非常に複雑なツリー構造を実装しています。

ツリーのサイズが大きくなりすぎる理論的または実用的な制限があるかどうか、または辞書が衝突でいっぱいになりすぎて正しく/迅速に機能しないポイントがあるかどうか疑問に思っていますか?

一般的な回答をいただければ幸いですが、C# 固有の情報の方がはるかに優れています。

Answer 1

.NET では、ツリーまたはディクショナリのいずれかの最大値は 2^31 - 1 です (オーバーヘッドがあると、おそらくそれより少し少なくなります)。

実際には、それよりずっと前にメモリが不足している可能性があります。

ツリーのバランスが保たれている場合、検索は約 2 のままになります。O(log N)。

辞書は、使用される基礎となるアルゴリズムにより敏感です。たとえば、さまざまな特性を持つ多くのハッシュ スキームがあります。

Answer 2

何を大量と考えるかによります。数百または数千でも問題ありませんが、専門的なものを探すには数百万の価値があるかもしれません。

ストレージ技術とリバランスに応じて、ツリーは成長するにつれて遅くなります。

ディクショナリはかなり一貫している必要がありますが、保存する可能性のあるデータの量に適したサイズで作成するようにしてください (安全のために x2 など)。

Answer 3

この質問を参照してください-それは私が最初に答えたものの1つです:)

問題は、約 900,000 アイテムのディクショナリを構築する際のパフォーマンスの低下でした。時間を 10 分以上から 0.34 秒に短縮しました。

教訓は、辞書はハッシュ関数と同じくらい優れているということです。一意のハッシュをすばやく生成できれば、稲妻のように実行されます。

お役に立てれば、

編集：

比較クラスは重要ではありません。.net 文字列には非常に強力なハッシュ関数があるため、辞書で優れたパフォーマンスを発揮します。彼が弦のペアの代わりに単一の弦を使用していた場合、その男の問題は「なくなった」だけだったでしょう。