2

LINQ を使用して、まったく同じ結果が得られる、述語内にあるWhere()メソッドのより高速な代替手段はありますか?List<T>.Contains()

例を次に示します。

List<int> a = ...
List<int> b = ...

var result = a.Where(x => b.Contains(x)); //very slow

私が見つけた1つの代替手段は、Intersect()メソッドを使用することです:

var result = a.Intersect(b);

result変数では、値のa順序が保持されます。aただし、値に重複が含まれている場合、Intersect()演算子は個別の値のみを返すため、まったく同じ結果は得られません。

別の方法 ：

var result = a.Join(b, x => x, y => y, (x, y) => x);

繰り返しますが、b重複が含まれている場合、結果は同じではありません。

別の可能性はありますか？

避けたいこと：

  • 独自の LINQ 拡張メソッドを作成するには
  • HashSet最初のリストで個別に作成し、Contains()内部で使用しますWhere()。
4

2 に答える 2

3

意味的には、必要なのはleft inner joinです。LINQJoin演算子は内部結合を実行します。これは近いですが、まったく同じではありません。幸い、 a を使用してleft joinGroupJoinを実行できます。 

var query = from n in a
            join k in b
            on n equals k into matches
            where matches.Any()
            select n;

もう 1 つのオプションは、2 番目のシーケンスのアイテムを、HashSetよりもはるかに効果的に検索できる に配置することListです。(これは、Join/GroupJoin が内部で行うことと似ています。)

var set = new HashSet<int>(b);
var query = a.Where(n => set.Contains(n));

別のオプションはJoin、あなたが行ったように を使用することですが、最初からすべての重複を削除するだけですb。重複がない場合は、必要なことが行われるためです。

var result = a.Join(b.Distinct(), x => x, y => y, (x, y) => x);
于 2013-09-18T14:46:16.443 に答える
0

より高速で複製するには、従来の「for」を使用します。

編集
私は以下を考慮してテストコードを書きました:

  • 1000 個のランダムな int を持つリスト。
  • 各メソッドごとに 200 テスト。
  • 1、2、4、および 8回の結果の使用は、結果を何度も使用する場合のIEnumerable<int>ように、LINQ の結果をより適切なデータ構造に変換する必要があることを示しています。List<int>

結果は次のとおりです。

1 uses per result
Tigrou-Where        : count=  93,  3.167,0ms
Tigrou-Intersect    : count=  89,    116,0ms
Tigrou-Join         : count=  96,    179,0ms
Servy-GroupJoin     : count=  93,    262,0ms
Servy-HashSet       : count=  93,     71,0ms
Servy-JoinDisctinct : count=  93,    212,0ms
JoseH-TheOldFor     : count=  93,     72,0ms

2 uses per result
Tigrou-Where        : count=  93,  6.007,0ms
Tigrou-Intersect    : count=  89,    182,0ms
Tigrou-Join         : count=  96,    293,0ms
Servy-GroupJoin     : count=  93,    455,0ms
Servy-HashSet       : count=  93,     99,0ms
Servy-JoinDisctinct : count=  93,    407,0ms
JoseH-TheOldFor     : count=  93,     73,0ms

4 uses per result
Tigrou-Where        : count=  93, 11.866,0ms
Tigrou-Intersect    : count=  89,    353,0ms
Tigrou-Join         : count=  96,    565,0ms
Servy-GroupJoin     : count=  93,    899,0ms
Servy-HashSet       : count=  93,    165,0ms
Servy-JoinDisctinct : count=  93,    786,0ms
JoseH-TheOldFor     : count=  93,     73,0ms

8 uses per result
Tigrou-Where        : count=  93, 23.831,0ms
Tigrou-Intersect    : count=  89,    724,0ms
Tigrou-Join         : count=  96,  1.151,0ms
Servy-GroupJoin     : count=  93,  1.807,0ms
Servy-HashSet       : count=  93,    299,0ms
Servy-JoinDisctinct : count=  93,  1.570,0ms
JoseH-TheOldFor     : count=  93,     81,0ms

コードは次のとおりです。

class Program
{
    static void Main(string[] args)
    {
        Random random = new Random(Environment.TickCount);
        var cases = 1000;
        List<int> a = new List<int>(cases);
        List<int> b = new List<int>(cases);
        for (int c = 0; c < cases; c++)
        {
            a.Add(random.Next(9999));
            b.Add(random.Next(9999));
        }

        var times = 100;
        var usesCount = 1;

        Console.WriteLine("{0} times", times);
        for (int u = 0; u < 4; u++)
        {
            Console.WriteLine();
            Console.WriteLine("{0} uses per result", usesCount);
            TestMethod(a, b, "Tigrou-Where", Where, times, usesCount);
            TestMethod(a, b, "Tigrou-Intersect", Intersect, times, usesCount);
            TestMethod(a, b, "Tigrou-Join", Join, times, usesCount);
            TestMethod(a, b, "Servy-GroupJoin", GroupJoin, times, usesCount);
            TestMethod(a, b, "Servy-HashSet", HashSet, times, usesCount);
            TestMethod(a, b, "Servy-JoinDisctinct", JoinDistinct, times, usesCount);
            TestMethod(a, b, "JoseH-TheOldFor", TheOldFor, times, usesCount);
            usesCount *= 2;
        }

        Console.ReadLine();
    }

    private static void TestMethod(List<int> a, List<int> b, string name, Func<List<int>, List<int>, IEnumerable<int>> method, int times, int usesCount)
    {
        var stopwatch = new Stopwatch();
        stopwatch.Start();
        int count = 0;
        for (int t = 0; t < times; t++)
        {
            // Process
            var result = method(a, b);
            // Count
            for (int u = 0; u < usesCount; u++)
            {
                count = 0;
                foreach (var item in result)
                {
                    count++;
                }
            }
        }
        stopwatch.Stop();
        Console.WriteLine("{0,-20}: count={1,4}, {2,8:N1}ms", 
            name, count, stopwatch.ElapsedMilliseconds);
    }

    private static IEnumerable<int> Where(List<int> a, List<int> b)
    {
        return a.Where(x => b.Contains(x));
    }

    private static IEnumerable<int> Intersect(List<int> a, List<int> b)
    {
        return a.Intersect(b); 
    }

    private static IEnumerable<int> Join(List<int> a, List<int> b)
    {
        return a.Join(b, x => x, y => y, (x, y) => x);
    }

    private static IEnumerable<int> GroupJoin(List<int> a, List<int> b)
    {
        return from n in a
               join k in b
               on n equals k into matches
               where matches.Any()
               select n;
    }

    private static IEnumerable<int> HashSet(List<int> a, List<int> b)
    {
        var set = new HashSet<int>(b);
        return a.Where(n => set.Contains(n));
    }

    private static IEnumerable<int> JoinDistinct(List<int> a, List<int> b)
    {
        return a.Join(b.Distinct(), x => x, y => y, (x, y) => x);
    }

    private static IEnumerable<int> TheOldFor(List<int> a, List<int> b)
    {
        var result = new List<int>();
        int countA = a.Count;
        var setB = new HashSet<int>(b);
        for (int loopA = 0; loopA < countA; loopA++)
        {
            var itemA = a[loopA];
            if (setB.Contains(itemA))
                result.Add(itemA);
        }
        return result;
    }
}

List<int>コードの行を変更して、結果を使用する前に変換すると、これらが 8 回使用されます。

8 uses per result
Tigrou-Where        : count=  97,  2.974,0ms
Tigrou-Intersect    : count=  91,     91,0ms
Tigrou-Join         : count= 105,    150,0ms
Servy-GroupJoin     : count=  97,    224,0ms
Servy-HashSet       : count=  97,     74,0ms
Servy-JoinDisctinct : count=  97,    223,0ms
JoseH-TheOldFor     : count=  97,     75,0ms

したがって、勝者は次のようになると思います: 少し変形した Servy-HashSet メソッド:

var set = new HashSet<int>(b);
var result = a.Where(n => set.Contains(n)).ToList();
于 2013-09-18T15:11:15.963 に答える