3

Imagine I have

 var points = new Point[]
 {
     new Point(1, 2),
     new Point(2, 3)
 };

To get the point with the minimum X I could:

 var result = points.OrderBy(point => point.X).First();

But for large arrays, I don't think this is the faster option. There is a faster alternative?

Jader Dias
  • 88,211
  • 155
  • 421
  • 625

3 Answers3

3

It is better to use

int x = points.Min(p => p.X);
var result = points.First(p => p.X == x);

as this eliminates the necessity of sorting this list (i.e., it is O(n) as opposed to, say, O(n log n)). Further, it's clearer than using OrderBy and First.

You could even write an extension method as follows:

static class IEnumerableExtensions {
    public static T SelectMin<T>(this IEnumerable<T> source, Func<T, int> selector) {
        if (source == null) {
            throw new ArgumentNullException("source");
        }

        int min = 0;
        T returnValue = default(T);
        bool flag = false;

        foreach (T t in source) {
            int value = selector(t);
            if (flag) {
                if (value < min) {
                    returnValue = t;
                    min = value;
                }
            }
            else {
                min = value;
                returnValue = t;
                flag = true;
            }
        }

        if (!flag) {
            throw new InvalidOperationException("source is empty");
        }

        return returnValue;
    }

Usage:

IEnumerable<Point> points;
Point minPoint = points.SelectMin(p => p.X);

You can generalize to your needs. The advantage of this is that it avoids potentially walking the list twice.

jason
  • 236,483
  • 35
  • 423
  • 525
  • Unless my logic is failing me .Min() must inspect every element? Then it returns that value. First then starts going through the same list again, until it finds the first point with that X value. Worst case that is 2*n? – Pieter Breed Oct 15 '09 at 19:10
  • I have added an extension method to address this. Second, `2 * n` is `O(n)`. – jason Oct 15 '09 at 19:23
2

The following should be the quickest, but not the prettiest way to do it:

public static T MinValue<T>(this IEnumerable<T> e, Func<T, int> f)
{
    if (e == null) throw new ArgumentException();
    var en = e.GetEnumerator();
    if (!en.MoveNext()) throw new ArgumentException();
    int min = f(en.Current);
    T minValue = en.Current;
    int possible = int.MinValue;
    while (en.MoveNext())
    {
        possible = f(en.Current);
        if (min > possible)
        {
            min = possible;
            minValue = en.Current;
        }
    }
    return minValue;
}

I only included the int extension, but it is trivial to do others.

Edit: modified per Jason.

Yuriy Faktorovich
  • 67,283
  • 14
  • 105
  • 142
  • 2
    Comment: `Count` is bad to invoke unless absolutely necessary on an `IEnumerable` as it causes the list to be walked (in the general case). If walking through the `IEnumerable` is expensive, this is bad. – jason Oct 15 '09 at 19:25
  • Another comment: Note that in the `while` loop you compute `f(en.Current)` on the current element twice. If `f` is expensive then this is not optimal. – jason Oct 15 '09 at 19:31
0

For anyone looking to do this today, MoreLinq is a library available by NuGet which includes the operator provided by the other answers as well as several other useful operations not present in the framework.

Chris Pitman
  • 12,990
  • 3
  • 41
  • 56