4

私は 2 つの非常に大きなList<List<int>>A と B を持っています。これらのリストの各要素間の交差を見つける必要があります。

A[0] = { 1, 2, 3};
B[0] = {2, 3, 4};

Intersection = { 2, 3 };

私の実装:

List<int> intersection = A[0].Intersection(B[0]).ToList();

このソリューションの実行には非常に長い時間がかかります。これを行うためのより良い方法と、より良い時間で実行するために使用できるより効率的なデータ構造があるかどうか疑問に思っています。

ありがとう！

4

2 に答える 2

7

これには C# で Hashset を使用する必要がありますHashSet<T>。ハッシュセットのルックアップは、リストの O(n) とは対照的に、O(1) (適切なハッシュ関数と下に配列を使用する場合) です。

C# で Linq を使用すると、基本的にこの「組み込み」を取得できますIntersect()。2 つのリストを使用する場合、ハッシュセットを内部的に使用して、O(n^2) ではなく O(n) で交差を計算します。

var intersection = a.Intersect(b).ToList();
于 2013-02-12T03:59:54.357 に答える
1

HashSet(T).IntersectWithを使用したコード例:

HashSet<string> lst1 = new HashSet<string> 

     { "id1", "id2", "id3" };

HashSet<string> lst2 = new HashSet<string> 

     { "id2", "id3", "id4" };

// what happens is that, lst1 will be modified by only leaving the intersect items
lst1.IntersectWith(lst2);

PS: String のサンプルを使用しましたが、独自の整数値を使用できます。

于 2013-02-12T04:19:58.623 に答える