¿C# tiene un equivalente std :: nth_element?

Question

Estoy portando un código C++ a C#.

¿Tiene C# un equivalente a std::nth_element() o tengo que hacer el mío?

Answer 1

Supongo que está buscando un descriptor de acceso que devuelva el elemento N-ésimo de una colección desordenada realizando una clasificación parcial en la colección. Esto tiende a ser útil cuando tiene una colección muy grande y le interesa uno de los primeros elementos basado en algún predicado de ordenamiento.

Que yo sepa, ni las extensiones .NET BCL o LINQ ofrecen un equivalente. Todos los métodos de clasificación (incluido Enumerable.OrderBy) realizan un ordenamiento completo de la colección.

Si necesita una versión eficiente de Nth, tendrá que pasar su propio método de extensión en IEnumerable para hacerlo. Si va a rodar su propia cuenta, puede consultar el Quick Select algorithm, que tiene un rendimiento O (n).

Si la versión de fuerza bruta es suficiente, se puede utilizar LINQ:

var someCollection = new []{ 5, 2, 8, 9, 0, 1, 3, 12, 4 }; 

var fifthItem = someCollection.NthItem(5); 

public static class NthExtensions 
{ 
    public static T NthItem(this IEnumerable<T> coll, int n) 
    { 
     return coll.OrderBy(x => x).Skip(n - 1).First(); 
    } 
} 

Answer 2

No, no es así. Tendrá que escribir el algoritmo de selección (preferiblemente quick select) a mano.

Answer 3

No hay un equivalente directo. Podría, potencialmente, utilizar OrderBy y Take/Skip de LINQ para lograr los mismos objetivos en cualquier IEnumerable, pero se ordenará la colección completa en este proceso.