CODEWITHSUNDEEP
c#.netlinqlinq-to-objects
Jader Dias
Jader Dias

Reputation: 90475

How to get the Point with minimal X from an array of Points without using OrderBy?

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?

Upvotes: 3

Views: 1471

Answers (3)

Chris Pitman
Chris Pitman

Reputation: 13104

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.

Upvotes: 0

Yuriy Faktorovich
Yuriy Faktorovich

Reputation: 68687

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.

Upvotes: 2

jason
jason

Reputation: 241641

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.

Upvotes: 3

Related Questions