Как получить точку с минимальным X из массива точек без использования OrderBy?

Question

Представьте меня

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

Чтобы получить точку с минимальным X I Could:

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

Но для больших массивов, я не думаю, что это быстрее вариант. Существует более быстрая альтернатива?

Answer 1

Лучше использовать

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

как это устраняет необходимость сортировки этого списка (то есть, это O(n) в отличие, скажем, O(n log n)). Кроме того, это более понятно, чем использование OrderBy и First.

Можно даже написать метод расширения следующим образом:

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

Использование:

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

Вы можете обобщить для ваших нужд. Преимущество этого заключается в том, что он избегает потенциальной ходьбы по списку дважды.

Answer 2

Следующее должно быть быстрым, но не самый красивый способ сделать это:

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

Я включил только расширение Int, но это тривиально, чтобы сделать другие.

Редактировать: модифицировано за Джейсон.

Answer 3

Для тех, кто хочет сделать это сегодня, MoreLinq - это библиотека, доступная NuGet, которая включает в себя оператора, предоставленного другими ответами, а также несколько других полезных операций, не присутствующих в рамках.