1

私は、データのコレクションを反復処理し、「主キー」が重複しているエントリを削除する必要があるプロジェクトに取り組んできました。私は使用してみました

List<int>

と

Dictionary<int, bool>

辞書を使用すると、各エントリでブール値をタグ付けする必要はありませんが、パフォーマンスがわずかに向上することがわかりました。私の期待は、これはリストがインデックス付きアクセスを許可し、ディクショナリが許可しないためです。私が疑問に思っていたのは、この問題に対するより良い解決策があるかどうかです。エントリに再度アクセスする必要はありません。見た「主キー」を追跡するだけで、新しい主キーを持つエントリに対してのみ追加作業を実行するようにできます。私はC＃と.NET2.0を使用しています。また、入力データを修正してソースから重複を削除することはできません（残念ながら！）。そして、スケーリングの感覚をつかむことができます。全体として、アプリケーションで約1,000,000回重複をチェックしていますが、一意である必要があるのは約64,000以下のサブセットです。

4

6 に答える 6

3

彼らは.NET3.5にHashSetクラスを追加しました。しかし、私はそれが辞書と同等になると思います。100個未満の要素がある場合は、リストのパフォーマンスが向上する可能性があります。

于 2008-09-18T12:12:21.320 に答える
1

編集：私のコメントを気にしないでください。あなたはC++について話していると思いました。私の投稿が C# の世界に関連しているかどうかはわかりません..

ハッシュテーブルは少し速いかもしれません。二分木 (辞書で使用されているもの) は、メモリへのアクセス方法が原因で、比較的遅くなる傾向があります。これは、ツリーが非常に大きくなる場合に特に当てはまります。

ただし、データ構造を変更する前に、辞書にカスタム プール アロケーターを使用しようとしましたか? ツリー自体の走査に時間が費やされるのではなく、ディクショナリが行う何百万もの割り当てと割り当て解除に時間が費やされるに違いありません。

単純なプール アロケータをディクショナリ テンプレートに差し込むだけで、10 倍の速度向上が見られる場合があります。Afaik ブーストには、直接使用できるコンポーネントがあります。

別のオプション: 整数に 64.000 エントリしか存在しないことがわかっている場合は、それらをファイルに書き込んで、完全なハッシュ関数を作成できます。そうすれば、ハッシュ関数を使用して整数を 0 から 64.000 の範囲にマップし、ビット配列にインデックスを付けることができます。

おそらく最速の方法ですが、柔軟性は低くなります。整数のセットが変更されるたびに、完全なハッシュ関数をやり直す必要があります (自動的に実行できます)。

于 2008-09-18T12:17:43.570 に答える
0

私はあなたが求めているものを本当に理解していません。

第一に、あなたが言うことの正反対です。ディクショナリにはインデックス付きアクセス（ハッシュテーブル）がありますが、deListにはありません。

すでに辞書にデータがある場合は、すべてのキーが一意であり、重複することはありません。

別のデータ型にデータが保存されていて、それを辞書に保存しているのではないかと思います。その場合、データの挿入は2つの辞書で機能します。

foreach (int key in keys)
{
  if (!MyDataDict.ContainsKey(key))
  {
    if (!MyDuplicatesDict.ContainsKey(key))
      MyDuplicatesDict.Add(key);
  }
  else
    MyDataDict.Add(key); 
}
于 2008-09-18T12:16:02.653 に答える
0

整数の一意性をチェックしており、整数の範囲が十分に制限されている場合は、配列を使用できます。

より適切にパッキングするには、ビットマップ データ構造を実装できます (基本的には配列ですが、配列内の各 int は、キーごとに 1 ビットを使用して、キー スペース内の 32 個の int を表します)。そうすれば、最大数が 1,000,000 の場合、データ構造に必要なメモリは最大 30.5 KB だけです。

ビットマップの実行は O(1) (チェックごと) であり、打ち負かすのは困難です。

于 2008-09-18T12:21:50.003 に答える
0

リストを使用する場合は、BinarySearch を使用します。

 // initailize to a size if you know your set size
List<int> FoundKeys = new List<int>( 64000 );
Dictionary<int,int> FoundDuplicates = new Dictionary<int,int>();

foreach ( int Key in MyKeys )
{
   // this is an O(log N) operation
   int index = FoundKeys.BinarySearch( Key );
   if ( index < 0 ) 
   {
       // if the Key is not in our list, 
       // index is the two's compliment of the next value that is in the list
       // i.e. the position it should occupy, and we maintain sorted-ness!
       FoundKeys.Insert( ~index, Key );
   }
   else 
   {
       if ( DuplicateKeys.ContainsKey( Key ) )
       {
           DuplicateKeys[Key]++;
       }
       else
       {
           DuplicateKeys.Add( Key, 1 );
       }
   } 
}

これは、オーバーロードを使用して IComparer を定義できる任意の型にも使用できます。 BinarySearch( T item, IComparer< T > );

于 2008-09-18T16:39:55.873 に答える
0

配列から重複を削除することについて、しばらく前に質問がありました。質問の目的上、パフォーマンスはあまり考慮されていませんでしたが、いくつかのアイデアが得られる可能性があるため、回答を確認することをお勧めします. また、私はここでベースから外れているかもしれませんが、配列から重複を削除しようとしている場合は、Enumerable.Distinctのような LINQ コマンドを使用すると、自分で記述したものよりもパフォーマンスが向上する可能性があります。LINQ を .NET 2.0 で動作させる方法があることが判明したので、これは調査する価値のあるルートかもしれません。

于 2008-09-18T12:26:30.943 に答える