25

Listと のような2 つの int 型がList AありList Bます。List Aのアイテムが何個あるか調べたいですList B。私はこれを行うことができますがforeach、コードの最適化が主要なターゲットであるため、回避しようとしている効率的な方法は何ですか。

List<int> A = new List<int>;
List<int> B = new List<int>;
// Some logic....item added in both lists. Then

foreach(var item in A)
{
    if (B.Contains(item))
    {
        // Subtract number of duplicates
    }
}

と を使用してみIntersectましAnyたが、それが返さboolれるため、それらを完全に適用することはできません。

4

15 に答える 15

11

標準実装B.Intersect(A).Count()には、測定されたパフォーマンスの問題がない限り、短くて読みやすいという大きな利点があります。

パフォーマンスが導入可能な問題である場合HashSet<int>、リソースの使用量と検索時間の点で適切な妥協点となります。ただし、パフォーマンスが心配なので、いくつかのテストを実行する必要があります (私が書いたこの無料のツールを使用しています)。

CPU: 1.8 GHz Pentium Core 2 Duo
反復回数: 100
各リストの項目数: 1000

A.Where(a => B.Contains(a)).Count(): 8338 ティック
A.Intersect(B).Count(): 288 ティック
B.Count - B.Except(A).Count(): 313 ティック

テストで紹介しましょうHashSet<int>（他の回答から実装を選択してください）：

HashSet<int>: 163 ティック

はるかに優れたパフォーマンスを発揮します。もっとうまくやれるでしょうか？入力範囲がわかっている (そして制限されている) 場合は、 を使用すると、これよりもはるかに優れた結果を得ることができますBitArray。この例では、(簡単にするために) 正の数のみを想定していますが、簡単に適用できます。

public static int UseBitArray(int range, List<int> listA, List<int> listB) {
    var BitArray array = new BitArray(range);
    for (int i = 0; i < listA.Count; ++i)
        array[listA[i]] = true;

    int count = 0;
    for (int i = 0; i < listB.Count; ++i) {
        if (array[listB[i]])
            ++count;
    }

    return count;
}

それはどのように実行しますか？

BitArray: 95 ティック

性能比較

2 番目に良い方法 ( ) の 58% しかかかりませんHashSet<int>。他人と比べることもしません。メモリを大量に使用し、広い範囲 (Int32.MaxValue / 2たとえばInt32.MaxValue、あなたは間違いなくそれと一緒に行くべきです。

また、入力についていくつかの仮定を行うことができれば、検索機能をさらに最適化できることにも注意してください (たとえば、セットが順序付けられていると仮定できる場合)。

スケールアップ方法 (Y 軸スケールは対数):

異なる入力セットでのパフォーマンス比較

アイテムの数が増えた場合Exceptよりもパフォーマンスが向上することに注意してください。Intersectまた、そのような些細なオブジェクト (整数) の場合、並行して実行してもパフォーマンスが向上しないことに注意してください (文字列の 2 つのリストの違いを見つけるも参照してください):非常に多数のアイテムに対して適切に調整されたアルゴリズムでない限り)。

パフォーマンスの向上の最後のビットを本当に探している場合は、独自のBitArrayクラスを実装することもできます (不要なものやエラーチェックなし):

sealed class FastBitArray {
    public FastBitArray(int length) {
        m_array = new int[((length - 1) / 32) + 1];
    }

    public bool this[int index] {
        get {
            return (m_array[index / 32] & (1 << (index % 32))) != 0;
        }
        set {
            if (value)
                m_array[index / 32] |= (1 << (index % 32));
            else
                m_array[index / 32] &= ~(1 << (index % 32));
        }
    }

    private int[] m_array;
}

truesetter の内部には分岐があることに注意してください。分岐予測子にとってパターンは簡単 (常に) であるため、分岐を最適化する必要はありません。これよりも複雑にするパフォーマンスの向上はありません。

最新のテスト:

反復回数: 100
各リストの項目数: 1000000

HashSet<int>: 144748 ティック
BitArray: 37292 ティック
FastBitArray: 28966 ティック

それらを視覚的に比較してみましょう (青色のシリーズは 1,000 項目でのテスト、オレンジ色のシリーズは 1,000,000、Y 軸は 1k のシリーズと簡単に比較できるように対数です)。遅いことがわかっているメソッドは単に省略されています。

性能比較表1

1M シリーズのみを示す同じデータと線形 Y 軸:

性能比較表2

于 2015-06-26T10:14:24.770 に答える
3 
HashSet<int> Btemp = new HashSet<int>(B);
var x = A.Count(p => B.Contains(p));

// or var x = A.Count(B.Contains); 
// but I have always found it to be a little unreadable to skip a lambda
// but this shorted form could be a little faster, because it skips a delegate

また

HashSet<int> Btemp = new HashSet<int>(B);
Btemp.IntersectWith(A); // note that this method is of the HashSet, it isn't 
                        // a "generic" Intersect, so it's optimized against 
                        // the HashSet internals
var y = Btemp.Count;

HashSet(理論的には、 areO(1)操作での追加と存在の確認の両方)

どちらもwithではなくO(n)whereです。n = A.CountO(m * n)m = B.CountO(x^2)

(技術的にはO(n) + O(m)の建物はHashSetですがO(m)、それでもO(x)です)...

最終的に、それらは二次ではなく時間的に線形になります...しかし、これはすべてBの長さに依存します... Bが1〜3要素の場合、Containあなたがしたように直接使用する方がおそらく高速です。

一般に、A が B よりもはるかに大きいことがわかっている場合は、A を に入れ、HashSetB を に残すList必要があります (B が A よりもはるかに大きい場合は、逆を行う必要があります)。

于 2013-08-05T09:42:08.963 に答える
2

私は同じ問題を抱えていましたが、より効率的なものを探していました。

// Testcase: 500 items exist in both lists
List<int> InputA = Enumerable.Range(0, 1000).ToList();
List<int> InputB = Enumerable.Range(500, 1000).ToList();

// Result
int Result1 = InputA.Where(a => InputB.Contains(a)).Count(); //13000 ticks
int Result2 = InputA.Intersect(InputB).Count(); //5700 ticks
int Result3 = B.Count - B.Except(A).Count(); //5800 ticks

int Result4 = InputA.CountIntersect(InputB); //2400 ticks

私の解決策は、要素をコピーせずIntersectにカウントするだけで、内部メソッドと同じです。そのため、2 倍以上高速です。

コード：

public static int CountIntersect<T>(this IEnumerable<T> collectionA, IEnumerable<T> collectionB)
{
    HashSet<T> tempA = new HashSet<T>(collectionA);
    int Result = 0;
    foreach (var itemB in collectionB)
    {
        if (tempA.Remove(itemB))
            Result++;
    }
    return Result;
}
于 2015-05-26T11:15:52.900 に答える
0

リストが非常に大きく、効率的にしたい場合は、最初にそれらをソートする必要があります。2 番目に行うことは、ターゲット (非カウント リスト) 内の重複を削除することです。ただし、問題が十分に大きい場合は、他の回答で説明されている単純な linq 式では不十分です。データを SQL サーバーにプッシュし、クエリを実行して回答を得る必要があります。次に、sqlserver のマルチスレッド性により、問題が大きい場合に必要となるスケーリングが処理されます。

于 2015-06-23T17:06:05.563 に答える
0

厳密なデータ構造の観点から、入力がソートされていない場合、実行できる最善の方法は O(n*m) です。O(n+m) が必ずしも正しくない理由については、以下の注を参照してください。

嫌な疑似コード:

int FindCommonIntersects (ListA, ListB){
    int return_var = 0
    for each_a_entry in ListA: // Assumes that ListA is sorted
        if each_a_entry != each_a_entry->next.value() then:
            for each_b_entry in ListB:
                if each_a_entry == each_b_entry then return_var++
    return return_var;

リストがソートされていない場合、リストA の場合はO(n)、リスト B の場合は O(m) を通過します。

したがって、最適なソリューションは O(n*m) で実行され、各リストを 1 回だけトラバースします。A に同じ要素が複数ある場合でも、each_a_entry != each_a_entry->next.value()行は B の要素と比較しないことを意味するため、時間を節約できることに注意してください。

サイズ n のマップを作成できると仮定すると、何かハッシュ構造を使用してこれをより高速に実行できると確信しています。ただし、無限のメモリがないため、異常なサイズのハッシュマップを作成できないと想定しています。

于 2015-06-25T22:06:49.180 に答える
0

2 つのリストの情報が時間の経過とともに収集される場合は、アイテムが挿入/削除されるときに重複を追跡することを検討してください。そうすれば、答えを決定するためのコストはリストの存続期間にわたって償却され、1 回限りのイベントで発生することはありません。

于 2015-06-26T00:48:55.713 に答える
0 
A.Where(B.Distinct().ToDictionary(_ => _).ContainsKey).Count(); //This should work for other scenario with good performance
于 2015-06-24T14:40:23.327 に答える