一部のライブラリコードには、50,000個以上のアイテムを含むことができるリストがあります。
ライブラリの呼び出し元は、文字列がリストに追加される結果となるメソッドを呼び出すことができます。追加される文字列の一意性を効率的に確認するにはどうすればよいですか？
現在、文字列を追加する直前に、リスト全体をスキャンして、各文字列を追加する文字列と比較しています。これにより、10,000アイテムを超えるスケールの問題が表示され始めます。
これをベンチマークしますが、洞察に興味があります。
- List<>をDictionary<>に置き換えると、リストが10,000アイテム以上に増えるので、ContainsKey（）はかなり速くなりますか？
- すべてのアイテムが追加されるまで一意性チェックを延期すると、より速くなりますか？その時点で、すべての要素を他のすべての要素と照合する必要がありますが、それでもn^^2操作です。
編集
いくつかの基本的なベンチマーク結果。FillとScanの2つのメソッドを公開する抽象クラスを作成しました。塗りつぶしは、コレクションをn個のアイテムで埋めるだけです（私は50,000を使用しました）。スキャンはリストをm回スキャンし（私は5000を使用しました）、指定された値が存在するかどうかを確認します。次に、そのクラスの実装をList用に、別のクラスをHashSet用に構築しました。
使用された文字列は、長さが均一に11文字であり、抽象クラスのメソッドを介してランダムに生成されました。
非常に基本的なマイクロベンチマーク。
Hello from Cheeso.Tests.ListTester
filling 50000 items...
scanning 5000 items...
Time to fill: 00:00:00.4428266
Time to scan: 00:00:13.0291180
Hello from Cheeso.Tests.HashSetTester
filling 50000 items...
scanning 5000 items...
Time to fill: 00:00:00.3797751
Time to scan: 00:00:00.4364431
したがって、その長さの文字列の場合、一意性をスキャンするとき、HashSetはListよりも約25倍高速です。また、このサイズのコレクションの場合、コレクションにアイテムを追加するときに、HashSetはリストに対してペナルティをゼロにします。
結果は興味深いものであり、有効ではありません。有効な結果を得るには、実装をランダムに選択して、ウォームアップ間隔、複数の試行を行う必要があります。しかし、それではバーが少ししか動かないだろうと私は確信しています。
みんな、ありがとう。
EDIT2
ランダム化と複数の試行を追加した後、この場合、HashSetは一貫してリストを約20倍上回っています。
これらの結果は、可変長の文字列、より複雑なオブジェクト、または異なるコレクションサイズには必ずしも当てはまりません。