約 3000 の異なるファイルを整理し、ゲーム中のさまざまなタイミングで取得する必要があります。
変数の独自の構造体を作成しました。アプリケーションの最初に「辞書」を作成し、ゲームの開始前にすべてのファイルをロードすることを考えていました。
パフォーマンスについて疑問があります。これほど多くのエントリを含む辞書を使用すると、アプリケーションが遅くなるのでしょうか? ディクショナリが大きいと、「TryGetValue」と「ContainsKey」の実行が遅くなりますか?
アドバイスありがとう！
27877 次
7 に答える
18
キーが十分に分散されたハッシュを持っている限り、TryGetValue と ContainsKey はそのサイズでかなり高速になるはずです。
ディクショナリには、インデックス可能な数の「バケット」があります。キーで値を追加または検索すると、GetHashCode() によって返された値が取得され、バケットの数よりも小さくなるように再度ハッシュ化されます (通常、モジュロのような単純なものですが、実装は定義されていません)。関連するバケットを調べます。
バケットには現在、0 個以上のアイテムがあります。ディクショナリは、.Equals() を使用して各項目をキーと比較します。
適切なバケットを見つける最初のビットは、一定時間 O(1) になります。キーをバケット内のキーと比較する 2 番目のビットは線形時間 O(n) になります。ここで、n はコレクション全体ではなく、そのバケット内のアイテムの数のみに関連します。
一般に、各バケット内の項目は非常に少ないはずです (これを維持しようとするためにバケットの数が増加します) ため、操作は基本的に一定の時間です。
ただし、ハッシュ コードの実装が不十分な場合、同じバケットに多数のキーが存在することになります。毎回 0 を返すだけの故意に悪い GetHashCode を持つオブジェクトを実験することでわかるように、時間の計算量は O(n) にどんどん近づいていきます。リストも O(n) であるため、最悪の場合はリストよりも悪いですが、ディクショナリにはより多くのオーバーヘッドがあります。
これは、心配する必要があるということですか？いいえ、比較的ナイーブなハッシュ方法でも比較的良い結果が得られるはずです。文字列キーを使用している場合は、おそらくすでに十分すぎるほどです。単純な組み込み型を使用している場合はなおさらです。
ただし、辞書へのアクセスが遅いことがわかった場合は、これに注意して、GetHashCode() メソッドを修正するか、IEqualityComparer を作成してください (GetHashCode() および Equals() で使用するための外部ルールを定義できます)。辞書、ハッシュセットなど)。
ほとんどの場合、3000 は何もありませんが、問題ありません。
于 2010-08-11T17:01:33.397 に答える
14
3000 エントリはDictionary<>. それは速度低下の原因にはなりません。
一方、起動時に 3000 個の異なるファイルをメモリに読み込むと、速度が低下します。必要なときにだけファイルをメモリに読み込み、後でアクセスできるようにファイルをメモリに保持する方がはるかに優れています。
于 2010-08-11T16:48:22.423 に答える
8
いいえ、そうではありません。これはメモリを消費しますが、辞書はハッシュテーブルであり、キーによる要素へのアクセスは一定であり、要素の数に依存しないため、かなり高速である必要がありますTryGetValue。ContainKey
于 2010-08-11T16:49:35.570 に答える
4
辞書キータイプにハッシュコードアルゴリズムを提供すると、ハッシュコードがInt32空間全体に比較的均等に分散され、ハッシュコードルックアップは辞書サイズの影響を受けません。
詳細については、 http：//en.wikipedia.org/wiki/Hashtable#Performance_analysisを参照してください。
于 2010-08-11T16:49:45.790 に答える
1
.NETの辞書はハッシュテーブルルックアップスキームを使用するため、エントリを追加してもルックアップパフォーマンスにほとんど影響しません。発生する唯一の問題は、メモリ使用量である可能性があります。3000アイテムのディクショナリは、キーと値型によって使用されるストレージの約3000倍を消費します。巨大なバイナリブロブのない単純な構造体の場合、3000は実に小さいです。
于 2010-08-11T16:49:14.027 に答える
1
ボトルネックは辞書のパフォーマンスではなく、3000ファイルの読み取りです。
于 2010-08-11T16:50:08.397 に答える
1
コンピューターに関するほとんどのこと (および特にパフォーマンスに関するもの) と同様に、"It Depends (tm)"
それはすべて Dictionary の実装に依存します。
これはバイナリ ツリーとして実行できます。この場合、ルックアップは O(log2 N) にする必要があります。これは、辞書のサイズが大きくなるにつれて、ルックアップ時間がゆっくりと長くなることを意味します。
これは、理論的には O(1) であるハッシュ テーブルとして実行できます。これは、辞書のサイズに関係なく、ルックアップに常に同じ時間がかかることを意味しますが、それは理論であり、バケットの数とハッシュ コードの品質。多数のアイテムが同じバケットに入って線形検索が必要になる場合、ディクショナリが大きくなるにつれて処理が大幅に遅くなります。
ただし、顕著な違いが見られるようになるには、ディクショナリが 3000 を超えて数桁大きくなる必要があります。
于 2010-08-11T16:53:49.117 に答える