IEnumerable.Count() O(n)

Question

我刚刚偶然发现了这段代码，我想知道为什么在循环期间完成计数。

  /// <summary>
  /// find the first index in a sequence to satisfy a condition
  /// </summary>
  /// <typeparam name="T">type of elements in source</typeparam>
  /// <param name="source">sequence of items</param>
  /// <param name="predicate">condition of item to find</param>
  /// <returns>the first index found, or -1 if not found</returns>
  public static int FindIndex<T>(this IEnumerable<T> source, Predicate<T> predicate)
  {
         for (int i = 0; i < source.Count(); i++)
         {
               if (predicate(source.ElementAt(i))) return i;
         }
         return -1; // Not found
  }

如果计数可以改变，我们不应该这样做： for (int i = source.Count() - 1; i >= 0; i--)

否则，我认为我们应该在之前计算计数循环开始，而不是每次都开始。

这样做的正确方法是什么？

Answer 1

为此编写手动代码的正确方法是丢掉所有垃圾并简单地使用 foreach 进行迭代：

public static int FindIndex<T>(this IEnumerable<T> source, Predicate<T> predicate) 
{
    var index = 0;
    foreach(var item in source) {
        if(predicate(item)) {
            return index;
        }
        ++index;
    }

    return -1;
} 

Answer 2

这是真正糟糕的代码，可能 - 它可能会迭代所有 O (n^2) 的内容，因为 Count() 可能需要迭代（如果它没有实现 ICollection） -of-T/IList-of-T 提供 .Count（已测试），并且 ElementAt(x) 可能需要迭代 x 个项目，因为它可能没有用于索引器的 IList-of-T。它可能适用于列表/数组，但在一般情况下它提供了糟糕的性能。最坏的情况是它迭代所有 n 项 n 次（对于 Count()s），加上伸缩/三角形系列，给出另一个 n(n+1)/2 增量（对于 ElementAt()s）。

只需使用 foreach 即可。或者更好的是，查找现有的 IndexOf 方法。

Answer 3

如果您打算使用 LINQ，那么为什么不在 LINQ 中完成这一切呢？ LINQ 被设计为在这种情况下特别易于使用。

Answer 4

这是使用 Linq 执行此操作的 O(n) 方法：

public static int FindIndex<T>(this IEnumerable<T> source, Predicate<T> pred)
{
    var foundItem = 
        items
            .Select( (i,index) => new {i,index} )
            .FirstOrDefault( x => pred(x.i));
    return foundItem == null ? -1 : foundItem.index;
}