Geek Answers Handbook

IEnumerable.Count () O (n)

I just stumbled upon this piece of code, I was wondering why the graph is executed during the loop.

  /// <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
  }

If the counter can change, we should not just do it like this: for (int i = source.Count () - 1; i> = 0; i -)

Otherwise, I think we should calculate the score before the start of the cycle, and not every time.

What would be the right way to do this?

+5
source share
4 answers

The correct way to write manual code for this is to lose all this garbage and simply loop over with 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;
}
+14
source

, O (n ^ 2), Count() ( ) t 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.

+3

LINQ, LINQ? LINQ , .

+1

O (n) Linq:

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;
}
0

More articles:


All Articles