2

使用 LINQ，是否有更快的替代Where()方法来替代带有List<T>.Contains()内部谓词的方法，从而得到完全相同的结果？

这是一个例子：

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

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

我发现的一种替代方法是使用Intersect()方法：

var result = a.Intersect(b);

在result变量中，a值顺序被保留。a但是，如果 in 中的值包含重复项，则它不会提供完全相同的结果，因为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运算符执行内部连接，这很接近，但并不完全相同。幸运的是，您可以使用 aGroupJoin来执行左连接。 

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

另一种选择是将第二个序列中的项目放入 aHashSet中，这样可以比 a 更有效地搜索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 个随机整数的列表。
  • 每种方法 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 回答