9

次の問題に出くわしました。
1 から 100.000.000 までのすべての数字を含むハッシュセットが必要です。次のコードを試しました：

var mySet = new HashSet<int>();
for (var k = 1; k <= 100000000; k++)
     mySet.Add(k);

49mil あたりでメモリ オーバーフローが発生したため、そのコードはうまくいきませんでした。これもかなり遅く、メモリが過度に増加しました。

それから私はこれを試しました。

var mySet = Enumerable.Range(1, 100000000).ToHashSet();

ToHashSet() は次のコードです。

public static HashSet<T> ToHashSet<T>(this IEnumerable<T> source)
{
    return new HashSet<T>(source);
}

再びメモリ オーバーフローが発生しましたが、前のコードよりも多くの数値を入力できました。

機能するのは次のとおりです。

var tempList = new List<int>();
for (var k = 1; k <= 100000000; k++)
     tempList.Add(k);

var numbers = tempList.ToHashSet();

私のシステムでは、Enumerable.Range() が 4 ティックしかかからない tempList を埋めるのに約 800 ミリ秒かかります!

HashSetが必要です。そうしないと、値を検索するのに時間がかかります（O（1）にする必要があります）。それを最速の方法で行うことができれば素晴らしいと思います。

私の質問は次のとおり
です。最初の 2 つの方法ではメモリ オーバーフローが発生するのに、3 番目の方法では発生しないのはなぜですか?

初期化時に HashSet がメモリに対して行う特別なことはありますか?

私のシステムには 16GB のメモリが搭載されているため、オーバーフロー例外が発生したときは非常に驚きました。

4

4 に答える 4

10

他のコレクション タイプと同様に、要素を追加すると、HashSet の容量が必要に応じて自動的に増加します。多数の要素を追加すると、多数の再割り当てが発生します。

を取るコンストラクターで初期化すると、が実際に であるIEnumerable<T>かどうかがチェックされ、そうであれば、HashSet の容量がコレクションのサイズに初期化されます。IEnumerable<T>ICollection<T>

これが 3 番目の例で起こっていることです。List<T>これも である を追加しているICollection<T>ため、HashSet にはリストのサイズに等しい初期容量が与えられるため、再割り当てが不要になります。

List<T>容量パラメータを取るコンストラクタを使用すると、リストを作成する際の再割り当てが回避されるため、さらに効率的になります。

var noElements = 100000000;
var tempList = new List<int>(noElements); 
for (var k = 1; k <= noElements; k++) 
     tempList.Add(k); 

var numbers = tempList.ToHashSet();

システムメモリに関しては; これが 32 ビット プロセスか 64 ビット プロセスかを確認します。32 ビット プロセスでは、最大 2GB のメモリを使用できます (/3GB スタートアップ スイッチを使用した場合は 3GB)。

他のコレクション型 ( List<T>、 などDictionary<TKey,TValue>)とは異なり、初期容量を設定HashSet<T>するパラメーターを受け取るコンストラクターがありません。多数の要素でcapacityを初期化する場合、おそらく最も効率的な方法は、最初に要素を配列に追加するか、適切な容量で追加し、次にこの配列またはリストをコンストラクターに渡すことです。HashSet<T>List<T>HashSet<T>

于 2012-07-19T08:54:07.677 に答える
2

HashSet<T>ほとんどの .net コレクションと同様に、成長のために配列倍増戦略を使用していると思います。残念ながら、容量を取るコンストラクターのオーバーロードはありません。

ただし、初期容量をチェックしICollection<T>て使用する場合は、その実装の基本的な実装を実装できます。そうすれば、一時的な を具体化せずにを直接埋めることができます。ICollection<T>.CountICollection<T>GetEnumerator()CountHashSet<T>List<T>

于 2012-07-19T09:06:50.490 に答える
1

1.5GB を消費するハッシュセットに 1 億 int を入れると (私のマシン)、bool[100000000] を作成して、true にしなければならなかった各数値を設定すると、100MB しかかからず、ハッシュセットよりも高速に検索されます。これは、int の範囲が 0 ～ 100000000 であることを前提としています。

于 2012-07-21T21:58:46.460 に答える
0

HashSetは倍増して大きくなり、その割り当てによって使用可能なメモリを超えます。

64 ビットシステムでは、HashSet は8,900 万アイテム以上を保持できます。

32 ビットシステムでは、制限は約6,170 万アイテムです。

そのため、メモリオーバーフロー例外が発生しています

詳細については

http://blog.mischel.com/2008/04/09/hashset-limitations/

于 2012-07-19T08:56:15.837 に答える