C# FindAll VS Where 速度

Question

有人知道List的Where和FindAll方法之间的速度差异吗？我知道Where是IEnumerable接口的一部分，而FindAll是List的一部分，我只是想知道哪个更快。

- Dested

---

可能是FindAll vs Where extension-method的重复问题。 - Ryan Gates

Answer 1

List<T>类的FindAll方法实际上构造一个新列表对象，并将结果添加到其中。而IEnumerable<T>的Where扩展方法将简单地遍历现有列表，并生成匹配结果的枚举，而不创建或添加任何东西（除了枚举器本身）。

对于小型数据集，这两种方法可能表现相似。但是，对于大型数据集，Where应该优于FindAll，因为用来包含结果的新列表将动态增长以容纳更多结果。当匹配结果数量增加时，FindAll的内存使用率也会呈指数级增长，而Where应该具有恒定最小的内存使用率（本身而言……不包括您对结果的处理）。

- jrista

---

特例是你真的需要在之后拥有一个列表（也许你需要调用 Count 或更改成员，或者要多次迭代它）。虽然 Where() 比 FindAll() 更好，但 FindAll() 在比较 Where().ToList() 时更好。 - Jon Hanna

@JonHanna: 起初我认为我同意你的观点，但现在不确定了。你有任何参考资料显示.ToList()比.FindAll()慢吗？对查询调用.ToList()将是可枚举的迭代，因此应该保持其内存效率。不仅如此，某些内部实现的Where迭代器甚至可以预先创建恰好正确大小（内存分配）的列表，从而在这些情况下胜过FindAll。我并不是特别反对，但如果有一个明确说明FindAll优势的可靠参考资料会更好。 - jrista

这个答案是完全错误的。请看@Wiory的观测结果。 - Carlo V. Dango

@Carlo：抱歉，但实际上是您错了。您对 Wiory 的回答的评论似乎没有注意到他确实通过“Check()”方法枚举了每种方法……包括 where->ienum 方法。Wiory 的结果验证了我的答案……FindAll 比使用 Where 更慢。此外，针对不同类型基础集合的 Where 的各种实现通常针对集合的特定机制进行优化，提供进一步的性能提升（即它并不全是纯通用的“where”行为……它可以相当高效！） - jrista

Answer 2

FindAll明显比Where慢，因为它需要创建一个新的列表。无论如何，我认为你应该考虑Jon Hanna的评论 - 在许多情况下，对结果和列表进行一些操作会更有用。我编写了一个小测试，将其粘贴到Console App项目中。它测量了函数执行的时间/刻度，对结果集进行的操作（以获得“真实”使用的性能，并确保编译器不会优化未使用的数据等 - 我是C＃的新手，还不知道它是如何工作的，抱歉）。注意：除了WhereIENumerable（）之外，每个测量的函数都会创建新的元素列表。我可能做错了什么，但是明显迭代IEnumerable需要更长的时间比迭代列表。

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

namespace Tests
{

    public class Dummy
    {
        public int Val;
        public Dummy(int val)
        {
            Val = val;
        }
    }
    public class WhereOrFindAll
    {
        const int ElCount = 20000000;
        const int FilterVal =1000;
        const int MaxVal = 2000;
        const bool CheckSum = true; // Checks sum of elements in list of resutls
        static List<Dummy> list = new List<Dummy>();
        public delegate void FuncToTest();

        public static long TestTicks(FuncToTest function, string msg)
        {
            Stopwatch watch = new Stopwatch();
            watch.Start();
            function();
            watch.Stop();
            Console.Write("\r\n"+msg + "\t ticks: " + (watch.ElapsedTicks));
            return watch.ElapsedTicks;
        }
        static void Check(List<Dummy> list)
        {
            if (!CheckSum) return;
            Stopwatch watch = new Stopwatch();
            watch.Start();

            long res=0;
            int count = list.Count;
            for (int i = 0; i < count; i++)     res += list[i].Val;
            for (int i = 0; i < count; i++)     res -= (long)(list[i].Val * 0.3);

            watch.Stop();
            Console.Write("\r\n\nCheck sum: " + res.ToString() + "\t iteration ticks: " + watch.ElapsedTicks);
        }
        static void Check(IEnumerable<Dummy> ieNumerable)
        {
            if (!CheckSum) return;
            Stopwatch watch = new Stopwatch();
            watch.Start();

            IEnumerator<Dummy> ieNumerator = ieNumerable.GetEnumerator();
            long res = 0;
            while (ieNumerator.MoveNext())  res += ieNumerator.Current.Val;
            ieNumerator=ieNumerable.GetEnumerator();
            while (ieNumerator.MoveNext())  res -= (long)(ieNumerator.Current.Val * 0.3);

            watch.Stop();
            Console.Write("\r\n\nCheck sum: " + res.ToString() + "\t iteration ticks :" + watch.ElapsedTicks);
        }
        static void Generate()
        {
            if (list.Count > 0)
                return;
            var rand = new Random();
            for (int i = 0; i < ElCount; i++)
                list.Add(new Dummy(rand.Next(MaxVal)));

        }
        static void For()
        {
            List<Dummy> resList = new List<Dummy>();
            int count = list.Count;
            for (int i = 0; i < count; i++)
            {
                if (list[i].Val < FilterVal)
                    resList.Add(list[i]);
            }      
            Check(resList);
        }
        static void Foreach()
        {
            List<Dummy> resList = new List<Dummy>();
            int count = list.Count;
            foreach (Dummy dummy in list)
            {
                if (dummy.Val < FilterVal)
                    resList.Add(dummy);
            }
            Check(resList);
        }
        static void WhereToList()
        {
            List<Dummy> resList = list.Where(x => x.Val < FilterVal).ToList<Dummy>();
            Check(resList);
        }
        static void WhereIEnumerable()
        {
            Stopwatch watch = new Stopwatch();
            IEnumerable<Dummy> iEnumerable = list.Where(x => x.Val < FilterVal);
            Check(iEnumerable);
        }
        static void FindAll()
        {
            List<Dummy> resList = list.FindAll(x => x.Val < FilterVal);
            Check(resList);
        }
        public static void Run()
        {
            Generate();
            long[] ticks = { 0, 0, 0, 0, 0 };
            for (int i = 0; i < 10; i++)
            {
                ticks[0] += TestTicks(For, "For \t\t");
                ticks[1] += TestTicks(Foreach, "Foreach \t");
                ticks[2] += TestTicks(WhereToList, "Where to list \t");
                ticks[3] += TestTicks(WhereIEnumerable, "Where Ienum \t");
                ticks[4] += TestTicks(FindAll, "FindAll \t");
                Console.Write("\r\n---------------");
            }
            for (int i = 0; i < 5; i++)
                Console.Write("\r\n"+ticks[i].ToString());
        }
    
    }

    class Program
    {
        static void Main(string[] args)
        {
            WhereOrFindAll.Run();
            Console.Read();
        }
    }
}

结果(ticks) - 检查和已启用(对结果进行某些操作)，模式：发布而无调试(CTRL+F5)：

 - 16,222,276 (for ->list)
 - 17,151,121 (foreach -> list)
 -  4,741,494 (where ->list)
 - 27,122,285 (where ->ienum)
 - 18,821,571 (findall ->list)

校验和已禁用（完全不使用返回的列表）：

 - 10,885,004 (for ->list)
 - 11,221,888 (foreach ->list)
 - 18,688,433 (where ->list)
 -      1,075 (where ->ienum)
 - 13,720,243 (findall ->list)

你的结果可能会略有不同，要得到真正的结果需要更多迭代。

- Wiory

---

你的测试很好。它们表明LINQ机制比直接在列表上操作要慢。这并不奇怪。你的“1075（where ->ienum）”是错误的，因为使用where而不遍历结果元素将永远不会实际执行where！ - Carlo V. Dango

抱歉，Carlo，但他即使在where->ienum实现中也调用他的“Check（）”方法。 Check（）迭代所有集合，因此他的结果完全有效。因此，这也使我的答案是正确的......你称之为“完全错误”的答案。 - jrista

Answer 3

更新（来自评论）：查看那段代码后，我同意，.Where 在最坏情况下应该具有相等的性能，但几乎总是更好。

原始答案：
.FindAll() 应该更快，它利用已知的 List 大小并通过简单的 for 循环遍历内部数组。 .Where() 必须启动一个枚举器（在这种情况下称为 WhereIterator 的封闭框架类），并以不太具体的方式完成相同的工作。

请记住，.Where() 是可枚举的，不会主动创建内存中的 List 并填充它。 它更像是流式传输，因此在处理非常大的数据时，内存使用可能会有显着差异。 另外，您可以更快地使用 4.0 中的 .Where() 方法以并行方式开始使用结果。

- Nick Craver

---

除非在 where 子句中涉及索引，否则实际使用 WhereEnumerableIterator 而不是 WhereIterator。WhereEnumerableIterator 比 WhereIterator 更高效。对于 List<T>，它会产生额外的方法调用成本（应在发布代码中内联），但不需要动态调整内部列表作为其处理的一部分。Where 的效率应该优于 FindAll，除了最小的列表（任何大于 4 个结果都将导致一个或多个调整）。 - jrista

在调用数组或List<T>上的Where时，有两个额外的内部迭代器类WhereArrayIterator和WhereListIterator，它们针对这两种情况进行了优化。一般来说，调用Where应该比调用FindAll更有效率。 - jrista

@jrista - 我完全错过了.Where()重载中的案例堆栈返回，谢谢！浏览那段代码后，我同意.Where()应该在最坏的情况下具有相等的性能，但几乎总是更好。此外，如果没有人花费额外的时间来教育他人，例如您和这些评论，stackoverflow将毫无用处，+1教会了我一些东西。 - Nick Craver

很高兴我能为您服务。 :) - jrista

Answer 4

Where比FindAll快得多。无论列表有多大，Where所需的时间都是完全相同的。

当然，Where只是创建一个查询，它不像FindAll一样创建一个列表。

- Jonathan Allen

---

这可能在技术上是正确的，但我认为显然OP询问的是在实际枚举结果的情况下的性能，而不仅仅是裸方法调用本身。 - Dan Tao

Answer 5

jrista的回答很有道理。然而，新列表添加了相同的对象，因此只是基于现有对象的引用增长，这不应该那么慢。 只要3.5 / Linq扩展是可能的，无论如何都更好。 当限制在2.0时，FindAll更有意义。

- Eric