0

私は少し奇妙なことを求めていますが、これが私の要件です (これは少し計算集約的で、これまでのところどこにも見つかりませんでした)。

<TKey, TValue>約30アイテムのコレクションが必要です。しかし、コレクションは大規模にネストされたforeachループで使用されており、真剣に、最大で 10 億回近く繰り返される可能性があります。コレクションの操作は簡単で、次のようになります。

 Dictionary<Position, Value> _cells = new 


_cells.Clear();
_cells.Add(Position.p1, v1);
_cells.Add(Position.p2, v2);
//etc

要するに、約30個のアイテムの追加とコレクションのクリアに過ぎません。また、値はある時点で別の場所から読み取られます。キーによるこの読み取り/取得が必要です。だから私は a の線に沿って何かが必要ですDictionary。現在、CPU からすべてのオンスを絞り出そうとしているので、いくつかのマイクロ最適化も探しています。1 つには、追加中に重複が既に存在するかどうかをチェックするコレクションを必要としません (これにより、通常、追加の場合と比較して辞書が遅くなりますList<T>)。重複をキーとして渡さないことはわかっています。

Addメソッドはいくつかのチェックを行うため、代わりにこれを試しました：

_cells[Position.p1] = v1; 
_cells[Position.p2] = v2;
//etc

List<T>ただし、これは、次のような典型的な実装よりも、約 10,000 回の反復で約 200 ミリ秒遅くなります。

List<KeyValuePair<Position, Value>> _cells = new 


_cells.Add(new KeyValuePair<Position, Value>(Position.p1, v1));
_cells.Add(new KeyValuePair<Position, Value>(Position.p2, v2));
//etc

これで、完全な反復の後、かなりの時間までスケーリングできます。上記の場合、リストからインデックスでアイテムを読み取ったことに注意してください（テスト目的では問題ありませんでした）。私たちにとって定期的な問題List<T>は多く、主な理由はキーでアイテムにアクセスできないことです.

私の質問は次のとおりです。

  1. キーで項目にアクセスできるカスタム コレクション クラスはありますが、追加中に重複チェックをバイパスしますか? サードパーティのオープン ソース コレクションであれば何でも構いません。

  2. または、IDictionary<TKey, TValue>インターフェースからカスタムコレクションクラスを実装する方法について、良いスターターを教えてください

アップデート：

私は MiMo の提案に従いましたが、List はさらに高速でした。おそらく、辞書作成のオーバーヘッドに関係しているのでしょう。

4

2 に答える 2

2

私の提案は、のソースコードDictionary<TKey, TValue>から始めて、特定の状況に合わせて最適化するように変更することです。

個々のキーと値のペアの削除をサポートする必要はありません。これにより、コードが単純化される可能性があります。あなたが取り除くことができる鍵などの有効性についてのいくつかのチェックもあるようです。

于 2012-12-02T21:08:21.813 に答える
2

ただし、これは、このような典型的な List 実装よりも、約 10 回の反復で数ミリ秒遅くなります。

わずか 30 個の値を追加する 10 回の反復で数ミリ秒遅くなりますか? 私はそれを信じていません。ハッシュ/等価ルーチンが非常に遅い場合を除き、ほんの数個の値を追加するだけでも、ほんのわずかな時間がかかります。(これは本当の問題になる可能性があります。キーの選択を微調整して、すばやくハッシュされるものにすることで、コードが大幅に改善されるのを見てきました。)

本当にミリ秒以上かかる場合は、診断を確認することをお勧めします。

しかし、一般的に遅いのは当然のことです。より多くの作業を行っているのです。リストの場合、バッファを拡張する必要があるかどうかを確認し、配列要素に書き込み、サイズをインクリメントするだけです。それでおしまい。ハッシュなし、正しいバケットの計算なし。

キーで項目にアクセスできるカスタム コレクション クラスはありますが、追加中に重複チェックをバイパスしますか?

いいえ。あなたが避けようとしている作業そのものが、後でキーですばやくアクセスできるようにするものです。

しかし、いつキーによるルックアップを実行する必要があるでしょうか? キーを調べずにコレクションを使用することがよくありますか? キー ルックアップを実行するまでのコレクションのサイズは?

おそらく、キーと値のペアのリストを作成し、書き終えて検索を開始する準備ができたときにのみ、それを辞書に変換する必要があります。

于 2012-12-02T20:58:25.570 に答える