Comment obtenir le point avec un minimum de X à partir d'un tableau de points sans utiliser OrderBy?

Question

Imaginez que j'ai

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

Pour obtenir le point avec le X minimum que je pouvais:

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

Mais pour les grands tableaux, je ne pense pas que ce soit l'option plus rapide. Il y a une alternative plus rapide?

Answer 1

Il est préférable d'utiliser

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

car cela élimine la nécessité de trier cette liste (par exemple, il est O(n) par opposition à, disons, O(n log n)). En outre, il est plus clair que d'utiliser OrderBy et First.

Vous pouvez même écrire une méthode d'extension comme suit:

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

Utilisation:

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

Vous pouvez généraliser à vos besoins. L'avantage de ceci est qu'il évite potentiellement de parcourir deux fois la liste.

Answer 2

Ce qui suit doit être le plus rapide, mais pas la plus jolie façon de le faire:

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

Je ne compris l'extension int, mais il est trivial de faire d'autres.

Édition: modifié par Jason.

Answer 3

Pour ceux qui cherchent à le faire aujourd'hui, MoreLinq est une bibliothèque disponible par NuGet qui comprend l'opérateur fourni par les autres réponses, ainsi que plusieurs autres opérations utiles ne sont pas présents dans le cadre.