FindAll vs Where扩展方法

Question

我只是想知道"FindAll"是否会比"Where"extentionMethod更快,为什么？

示例:

myList.FindAll(item=> item.category == 5);

要么

myList.Where(item=> item.category == 5);

哪个更好 ？

Answer 1

好吧,FindAll将匹配的元素复制到一个新列表,而Where只是返回一个延迟评估的序列 - 不需要复制.

因此,我希望Where比FindAll完全评估结果序列的速度稍微快一些- 当然,懒惰的评估策略Where意味着如果你只看(比如说)第一场比赛,它就不需要检查余数的清单.(正如Matthew所指出的那样,维护状态机的工作是Where.但是,这只会有固定的内存成本 - 而构建新的列表可能需要多个数组分配等)

基本上,FindAll(predicate)更接近于Where(predicate).ToList()公正Where(predicate).

只是对马修的答案做出更多反应,我认为他的测试不够彻底.他的谓词碰巧选择了一半的项目.这是一个简短但完整的程序,它测试相同的列表,但有三个不同的谓词 - 一个选择没有项目,一个选择所有项目,一个选择其中一半.在每种情况下,我都会进行五十次测试以获得更长的时间.

我正在使用Count()以确保Where结果得到充分评估.结果显示,收集约一半的结果,两个是颈部和颈部.没有结果,FindAll赢了.收集所有结果,Where获胜.我觉得这很有趣:随着越来越多的匹配被发现,所有的解决方案变得越来越慢:FindAll要做更多的复制,并且Where必须返回匹配的值而不是仅仅在MoveNext()实现中循环.然而,FindAll变得比Where它慢得多,所以失去了早期的领先优势.很有意思.

结果:

FindAll: All: 11994
Where: All: 8176
FindAll: Half: 6887
Where: Half: 6844
FindAll: None: 3253
Where: None: 4891

(使用/ o +/debug-编译并从命令行运行.NET 3.5.)

码:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

class Test
{
    static List<int> ints = Enumerable.Range(0, 10000000).ToList();

    static void Main(string[] args)
    {
        Benchmark("All", i => i >= 0); // Match all
        Benchmark("Half", i => i % 2 == 0); // Match half
        Benchmark("None", i => i < 0); // Match none
    }

    static void Benchmark(string name, Predicate<int> predicate)
    {
        // We could just use new Func<int, bool>(predicate) but that
        // would create one delegate wrapping another.
        Func<int, bool> func = (Func<int, bool>) 
            Delegate.CreateDelegate(typeof(Func<int, bool>), predicate.Target,
                                    predicate.Method);
        Benchmark("FindAll: " + name, () => ints.FindAll(predicate));
        Benchmark("Where: " + name, () => ints.Where(func).Count());
    }

    static void Benchmark(string name, Action action)
    {
        GC.Collect();
        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < 50; i++)
        {
            action();
        }
        sw.Stop();
        Console.WriteLine("{0}: {1}", name, sw.ElapsedMilliseconds);
    }
}

Answer 2

我们测试而不是猜测怎么样？很遗憾看到错误的答案出来了.

var ints = Enumerable.Range(0, 10000000).ToList();
var sw1 = Stopwatch.StartNew();
var findall = ints.FindAll(i => i % 2 == 0);
sw1.Stop();

var sw2 = Stopwatch.StartNew();
var where = ints.Where(i => i % 2 == 0).ToList();
sw2.Stop();

Console.WriteLine("sw1: {0}", sw1.ElapsedTicks);
Console.WriteLine("sw2: {0}", sw2.ElapsedTicks);
/*
Debug
sw1: 1149856
sw2: 1652284

Release
sw1: 532194
sw2: 1016524
*/

编辑:

即使我转动上面的代码

var findall = ints.FindAll(i => i % 2 == 0);
...
var where = ints.Where(i => i % 2 == 0).ToList();

... 至 ...

var findall = ints.FindAll(i => i % 2 == 0).Count;
...
var where = ints.Where(i => i % 2 == 0).Count();

我得到了这些结果

/*
Debug
sw1: 1250409
sw2: 1267016

Release
sw1: 539536
sw2: 600361
*/

编辑2.0 ...

如果你想要一个当前列表子集的列表,那么最快的方法是FindAll().这样做的原因是简单的.FindAll实例方法使用当前List上的索引器而不是枚举器状态机.Where()扩展方法是对使用枚举器的其他类的外部调用.如果从列表中的每个节点步进到下一个节点,则必须调用封面下的MoveNext()方法.从上面的示例中可以看出,使用索引条目创建新列表(指向原始项目,因此内存膨胀最小)甚至只是获取已过滤项目的计数甚至更快.

现在,如果您要从Enumerator中提前中止,Where()方法可能会更快.当然,如果将早期中止逻辑移动到FindAll()方法的谓词,您将再次使用索引器而不是枚举器.

现在还有其他原因使用Where()语句(例如其他linq方法,foreach块等等),但问题是FindAll()比Where()更快.除非你不执行Where(),否则答案似乎是肯定的.(比较苹果和苹果)

我不是说不要使用LINQ或.Where()方法.它们使代码更易于阅读.问题是关于性能而不是关于阅读和理解代码的容易程度.快速执行此工作的最快方法是使用for block步进每个索引并根据需要执行任何逻辑(甚至是早期退出).LINQ之所以如此伟大,是因为复杂的表达式树和你可以得到的转换.但是使用.Where()方法中的迭代器必须经过大量代码才能找到内存状态机的方法,这只是将下一个索引从List中取出.还应该注意,这个.FindAll()方法仅对实现它的对象有用(例如Array和List.)

更多......

for (int x = 0; x < 20; x++)
{
    var ints = Enumerable.Range(0, 10000000).ToList();
    var sw1 = Stopwatch.StartNew();
    var findall = ints.FindAll(i => i % 2 == 0).Count;
    sw1.Stop();

    var sw2 = Stopwatch.StartNew();
    var where = ints.AsEnumerable().Where(i => i % 2 == 0).Count();
    sw2.Stop();

    var sw4 = Stopwatch.StartNew();
    var cntForeach = 0;
    foreach (var item in ints)
        if (item % 2 == 0)
            cntForeach++; 
    sw4.Stop();

    Console.WriteLine("sw1: {0}", sw1.ElapsedTicks);
    Console.WriteLine("sw2: {0}", sw2.ElapsedTicks);
    Console.WriteLine("sw4: {0}", sw4.ElapsedTicks);
}


/* averaged results
sw1 575446.8
sw2 605954.05
sw3 394506.4
/*