C# - For循环和Foreach循环-巨大的性能差异

Question

我正在对一种算法进行优化，该算法在给定的数组中找到比X大的最小数，但我发现了一个奇怪的差异。在下面的代码中，“ForeachUpper”结束于625毫秒，而“ForUpper”结束于几个小时（非常慢）。为什么会这样？

  class Teste
{
    public double Valor { get; set; }

    public Teste(double d)
    {
        Valor = d;
    }

    public override string ToString()
    {
        return "Teste: " + Valor;
    }
}

  private static IEnumerable<Teste> GetTeste(double total)
    {
        for (int i = 1; i <= total; i++)
        {
            yield return new Teste(i);
        }
    }
    static void Main(string[] args)
    {
        int total = 1000 * 1000*30 ;
        double test = total/2+.7;

        var ieTeste = GetTeste(total).ToList();


        Console.WriteLine("------------");

        ForeachUpper(ieTeste.Select(d=>d.Valor), test);
        Console.WriteLine("------------");
        ForUpper(ieTeste.Select(d => d.Valor), test);
        Console.Read();
    }

    private static void ForUpper(IEnumerable<double> bigList, double find)
    {
        var start1 = DateTime.Now;

        double uppper = 0;
        for (int i = 0; i < bigList.Count(); i++)
        {
            var toMatch = bigList.ElementAt(i);
            if (toMatch >= find)
            {
                uppper = toMatch;
                break;
            }
        }

        var end1 = (DateTime.Now - start1).TotalMilliseconds;

        Console.WriteLine(end1 + " = " + uppper);
    }

    private static void ForeachUpper(IEnumerable<double> bigList, double find)
    {
        var start1 = DateTime.Now;

        double upper = 0;
        foreach (var toMatch in bigList)
        {
            if (toMatch >= find)
            {
                upper = toMatch;
                break;
            }
        }

        var end1 = (DateTime.Now - start1).TotalMilliseconds;

        Console.WriteLine(end1 + " = " + upper);
    }

谢谢

- WoF_Angel

---

顺便提一下，使用Stopwatch类。 - SLaks

我正在对一种算法进行优化，该算法可以找到比X大的最小数字。其实你不需要任何算法，只需要使用var number = MyList.Where(l => l > x).Max()即可。使用LinQ，永远不要再使用for和foreach了。 - Federico Berasategui

@HighCore，你搞反了，应该是这样：collection.Where(value => value > someConstant).Min(); - Servy

@HighCore: 这就是为什么我们会得到一些想要用 LINQ 做任何事情的问题，即使 foreach 更好。不要忘记 for 和 foreach。只需要学会如何使用你所拥有的每一个工具。 - Daniel Hilgarth

@Alex那是O(n*log(n))而不是O(n)。你只需要排序整个序列中的最小值/最大值就可以了，不必对整个序列进行排序。如果你先进行过滤，那么所有随后的操作都会更快，而不是在最后才进行过滤。 - Servy

Answer 1

IEnumerable<T> 无法进行索引。

你在每次迭代中调用的 Count() 和 ElementAt() 扩展方法都是 O(n) 的；它们需要循环遍历集合来查找计数或第 n 个元素。

教训: 了解你的集合类型。

- SLaks

---

关于 Count() 值得注意的是，它取决于实际的集合类型，如果它实现了带有 Count 属性的 ICollection，则 Count() 将使用它。 - sll

@sll：对于ElementAt也是如此。如果OP在Select后添加.ToArray()，那么这些巨大的差异将消失。 - Daniel Hilgarth

有趣的是，这意味着当源集合是可枚举的时，像快速排序/二分查找这样的算法很容易被简单的 foreach 超越。 - WoF_Angel

@WoF_Angel：更准确地说，您不应该在任意的IEnumerable<T>上使用for。 - SLaks

@WOF_Angel：实际上是相反的：像快速排序和二分查找这样的算法依赖于集合可以被索引以提供其承诺的时间复杂度。使用可枚举对象永远不会使这样的算法更快（嗯，实际上对集合的任何迭代都几乎总是使用普通数组/for循环更快）。 - vgru

Answer 2

这种差异的原因在于您的 for 循环将在每次迭代中执行 bigList.Count()。在您的情况下，这真的很昂贵，因为它将执行 Select 并迭代完整的结果集。

此外，您正在使用 ElementAt，再次执行选择并迭代到您提供的索引位置。

- Daniel Hilgarth