CODEWITHSUNDEEP
c#linqienumerable
bevacqua
bevacqua

Reputation: 48476

IEnumerable.Count() O(n)

I just stumbled upon this fragment of code, I was wondering why the Count is done 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 count can change, shouldn’t we just do it like this instead: for (int i = source.Count() - 1; i >= 0; i--)

Otherwise, I think we should calculate the count before the looping starts, instead of every time.

What would be the correct way to do this?

Upvotes: 5

Views: 359

Answers (4)

spender
spender

Reputation: 120390

Here's an O(n) way of doing it with 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;
}

Upvotes: 0

Marc Gravell
Marc Gravell

Reputation: 1062550

That is really bad code, potentially - it could be iterating everything O (n^2), since Count() might need to iterate (if it doesn't implement ICollection-of-T/IList-of-T to offer .Count, which is tested), and ElementAt(x) might need to iterate x items, since it might not have IList-of-T for the indexer. It might work ok for lists/arrays, but in the general case it offers terrible performance. The worst case is that it iterates all n items n times (for the Count()s), plus the telescoping/triangular series, giving another n(n+1)/2 increments (for the ElementAt()s).

Just use foreach. Or better, look for an existing IndexOf method.

Upvotes: 3

Ken Wayne VanderLinde
Ken Wayne VanderLinde

Reputation: 19339

If your going to use LINQ, then why not do it all in LINQ? LINQ was designed to be especially easy to use in situations like this.

Upvotes: 1

Jon
Jon

Reputation: 437336

The correct way to write manual code for this would be to lose all that rubbish and simply iterate 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;
}

Upvotes: 14

Related Questions