C # Ordenar y ordenar por comparación

105

Puedo ordenar una lista usando Sort u OrderBy. Cual es mas rapido? ¿Ambos trabajan en el mismo algoritmo?

List<Person> persons = new List<Person>();
persons.Add(new Person("P005", "Janson"));
persons.Add(new Person("P002", "Aravind"));
persons.Add(new Person("P007", "Kazhal"));

1.

persons.Sort((p1,p2)=>string.Compare(p1.Name,p2.Name,true));

2.

var query = persons.OrderBy(n => n.Name, new NameComparer());

class NameComparer : IComparer<string>
{
    public int Compare(string x,string y)
    {
      return  string.Compare(x, y, true);
    }
}
user215675
fuente
22
No puedo creer que ninguna de las respuestas mencione esto, pero la mayor diferencia es la siguiente: OrderBy hace una copia ordenada de Array o List, mientras que Sort realmente la ordena en su lugar.
PRMan
2
como título dice comparación, me gustaría agregar que OrderBy es estable y sort es estable hasta 16 elementos ya que hasta 16 elementos se usa la ordenación por inserción si los elementos son más que eso, entonces cambia a otros algos inestables Editar: estable significa mantener el orden relativo de elementos que tienen la misma clave.
Eklavyaa
@PRMan No, OrderBy crea un enumerable perezoso. Solo si llama a un método como ToList en el enumerable devuelto, obtiene una copia ordenada.
Stewart
1
@ Stewart, ¿no considera que Array.Copy o Collection.Copy en TElement [] en el búfer en System.Core / System / Linq / Enumerable.cs sea una copia? Y si llama a ToList en IEnumerable, podría tener momentáneamente 3 copias en la memoria a la vez. Este es un problema para matrices muy grandes, que era parte de mi punto. Además, si necesita el mismo orden ordenado más de una vez, llamar a Ordenar en el lugar una vez es mucho más eficiente que ordenar repetidamente la Lista, debido a su permanencia.
PRMan
1
@PRMan Oh, querías decir que una copia ordenada se construye internamente. Aún así, eso es inexacto, ya que OrderBy no crea la copia; por lo que puedo ver, esto lo hace el método GetEnumerator cuando realmente comienza a recorrer la colección. Intenté revisar mi código y descubrí que el código que llena una variable de una expresión LINQ se ejecuta casi instantáneamente, pero cuando ingresa al bucle foreach, pasa tiempo clasificándolo. Supongo que cuando tenga un poco más de tiempo debería dedicar un poco a tratar de averiguar cómo funciona entre bastidores.
Stewart

Respuestas:

90

Por qué no medirlo:

class Program
{
    class NameComparer : IComparer<string>
    {
        public int Compare(string x, string y)
        {
            return string.Compare(x, y, true);
        }
    }

    class Person
    {
        public Person(string id, string name)
        {
            Id = id;
            Name = name;
        }
        public string Id { get; set; }
        public string Name { get; set; }
    }

    static void Main()
    {
        List<Person> persons = new List<Person>();
        persons.Add(new Person("P005", "Janson"));
        persons.Add(new Person("P002", "Aravind"));
        persons.Add(new Person("P007", "Kazhal"));

        Sort(persons);
        OrderBy(persons);

        const int COUNT = 1000000;
        Stopwatch watch = Stopwatch.StartNew();
        for (int i = 0; i < COUNT; i++)
        {
            Sort(persons);
        }
        watch.Stop();
        Console.WriteLine("Sort: {0}ms", watch.ElapsedMilliseconds);

        watch = Stopwatch.StartNew();
        for (int i = 0; i < COUNT; i++)
        {
            OrderBy(persons);
        }
        watch.Stop();
        Console.WriteLine("OrderBy: {0}ms", watch.ElapsedMilliseconds);
    }

    static void Sort(List<Person> list)
    {
        list.Sort((p1, p2) => string.Compare(p1.Name, p2.Name, true));
    }

    static void OrderBy(List<Person> list)
    {
        var result = list.OrderBy(n => n.Name, new NameComparer()).ToArray();
    }
}

En mi computadora, cuando se compila en modo de lanzamiento, este programa imprime:

Sort: 1162ms
OrderBy: 1269ms

ACTUALIZAR:

Como sugirió @Stefan, aquí están los resultados de ordenar una lista grande menos veces:

List<Person> persons = new List<Person>();
for (int i = 0; i < 100000; i++)
{
    persons.Add(new Person("P" + i.ToString(), "Janson" + i.ToString()));
}

Sort(persons);
OrderBy(persons);

const int COUNT = 30;
Stopwatch watch = Stopwatch.StartNew();
for (int i = 0; i < COUNT; i++)
{
    Sort(persons);
}
watch.Stop();
Console.WriteLine("Sort: {0}ms", watch.ElapsedMilliseconds);

watch = Stopwatch.StartNew();
for (int i = 0; i < COUNT; i++)
{
    OrderBy(persons);
}
watch.Stop();
Console.WriteLine("OrderBy: {0}ms", watch.ElapsedMilliseconds);

Huellas dactilares:

Sort: 8965ms
OrderBy: 8460ms

En este escenario, parece que OrderBy funciona mejor.


ACTUALIZACIÓN2:

Y usando nombres aleatorios:

List<Person> persons = new List<Person>();
for (int i = 0; i < 100000; i++)
{
    persons.Add(new Person("P" + i.ToString(), RandomString(5, true)));
}

Dónde:

private static Random randomSeed = new Random();
public static string RandomString(int size, bool lowerCase)
{
    var sb = new StringBuilder(size);
    int start = (lowerCase) ? 97 : 65;
    for (int i = 0; i < size; i++)
    {
        sb.Append((char)(26 * randomSeed.NextDouble() + start));
    }
    return sb.ToString();
}

Rendimientos:

Sort: 8968ms
OrderBy: 8728ms

Aún así, OrderBy es más rápido

Darin Dimitrov
fuente
2
Creo que es muy diferente de ordenar una lista muy pequeña (3 elementos) 1000000 veces, o de ordenar una lista muy grande (1000000 elementos) solo unas pocas veces. Ambos son muy relevantes. En la práctica, el tamaño medio de la lista (¿qué es medio? ... digamos 1000 elementos por ahora) es lo más interesante. En mi humilde opinión, ordenar listas con 3 elementos no es muy significativo.
Stefan Steinegger
25
Tenga en cuenta que existe una diferencia entre "más rápido" y "notablemente más rápido". En su último ejemplo, la diferencia fue de aproximadamente un cuarto de segundo. ¿Se dará cuenta el usuario? ¿Es inaceptable que el usuario espere casi nueve segundos para obtener el resultado? Si las respuestas a ambas preguntas son "no", entonces realmente no importa cuál elija desde la perspectiva del desempeño.
Eric Lippert
12
Tenga en cuenta también que la prueba aquí ordena la lista antes de iniciar el cronómetro, por lo que estamos comparando cómo se comparan los dos algoritmos cuando se enfrentan a una entrada ordenada. Esto puede ser bastante diferente a su rendimiento relativo con entradas sin clasificar.
phoog
3
En mi humilde opinión, estos resultados son bastante sorprendentes, considerando el hecho de que LINQtiene que gastar memoria adicional en comparación con una List<T>.Sortimplementación en el lugar . No estoy seguro de si mejoraron esto en las versiones más recientes de .NET, pero en mi máquina (i7 3.ª generación de .NET 4.5 de 64 bits) Sortsupera OrderByen todos los casos. Además, al observar el OrderedEnumerable<T>código fuente, parece que crea tres matrices adicionales (primero a Buffer<T>, luego una matriz de claves proyectadas, luego una matriz de índices) antes de finalmente llamar a Quicksort para ordenar la matriz de índices en su lugar.
Groo
2
... y luego de todo esto, está la ToArrayllamada que crea la matriz resultante. Las operaciones de memoria y la indexación de matrices son operaciones increíblemente rápidas, pero todavía no puedo encontrar la lógica detrás de estos resultados.
Groo
121

No, no son el mismo algoritmo. Para empezar, el LINQ OrderByestá documentado como estable (es decir, si dos elementos tienen el mismo Name, aparecerán en su orden original).

También depende de si almacena la consulta en búfer o la itera varias veces (LINQ-to-Objects, a menos que almacene el resultado, reordenará por foreach).

Para la OrderByconsulta, también estaría tentado a usar:

OrderBy(n => n.Name, StringComparer.{yourchoice}IgnoreCase);

(para {yourchoice}uno de CurrentCulture, Ordinalo InvariantCulture).

List<T>.Sort

Este método usa Array.Sort, que usa el algoritmo QuickSort. Esta implementación realiza un tipo inestable; es decir, si dos elementos son iguales, es posible que no se conserve su orden. Por el contrario, una clasificación estable conserva el orden de los elementos que son iguales.

Enumerable.OrderBy

Este método realiza una clasificación estable; es decir, si las claves de dos elementos son iguales, se conserva el orden de los elementos. Por el contrario, una ordenación inestable no conserva el orden de los elementos que tienen la misma clave. ordenar; es decir, si dos elementos son iguales, es posible que no se conserve su orden. Por el contrario, una clasificación estable conserva el orden de los elementos que son iguales.

Marc Gravell
fuente
5
Si usa .NET Reflector o ILSpy para abrir Enumerable.OrderByy profundizar en su implementación interna, puede ver que el algoritmo de clasificación OrderBy es una variante de QuickSort que realiza una clasificación estable. (Ver System.Linq.EnumerableSorter<TElement>.) Por lo tanto, Array.Sorty Enumerable.OrderByse puede esperar que ambos tengan tiempos de ejecución O (N log N) , donde N es el número de elementos de la colección.
John Beyer
@Marc No sigo muy bien cuál sería la diferencia si dos elementos fueran iguales y su orden no se conservara. Ciertamente, esto no parece un problema para los tipos de datos primitivos. Pero incluso para un tipo de referencia, ¿por qué importaría, si tuviera que ordenar, la persona con nombre Marc Gravell apareciera antes que otra persona con el nombre Marc Gravell (por ejemplo :))? No estoy cuestionando su respuesta / conocimiento, más bien busco una aplicación de este escenario.
Mukus
4
@Mukus imagina que clasificas la libreta de direcciones de una empresa por nombre (o incluso por fecha de nacimiento); inevitablemente habrá duplicados. En última instancia, la pregunta es: ¿qué les sucede? ¿Está definido el suborden?
Marc Gravell
55

La respuesta de Darin Dimitrov muestra que OrderByes un poco más rápido que List.Sortcuando se enfrenta a una entrada ya ordenada. Modifiqué su código para que ordene repetidamente los datos sin clasificar y, OrderByen la mayoría de los casos, sea un poco más lento.

Además, la OrderByprueba utiliza ToArraypara forzar la enumeración del enumerador Linq, pero eso obviamente devuelve un tipo ( Person[]) que es diferente del tipo de entrada ( List<Person>). Por lo tanto, volví a ejecutar la prueba usando en ToListlugar de ToArrayy obtuve una diferencia aún mayor:

Sort: 25175ms
OrderBy: 30259ms
OrderByWithToList: 31458ms

El código:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

class Program
{
    class NameComparer : IComparer<string>
    {
        public int Compare(string x, string y)
        {
            return string.Compare(x, y, true);
        }
    }

    class Person
    {
        public Person(string id, string name)
        {
            Id = id;
            Name = name;
        }
        public string Id { get; set; }
        public string Name { get; set; }
        public override string ToString()
        {
            return Id + ": " + Name;
        }
    }

    private static Random randomSeed = new Random();
    public static string RandomString(int size, bool lowerCase)
    {
        var sb = new StringBuilder(size);
        int start = (lowerCase) ? 97 : 65;
        for (int i = 0; i < size; i++)
        {
            sb.Append((char)(26 * randomSeed.NextDouble() + start));
        }
        return sb.ToString();
    }

    private class PersonList : List<Person>
    {
        public PersonList(IEnumerable<Person> persons)
           : base(persons)
        {
        }

        public PersonList()
        {
        }

        public override string ToString()
        {
            var names = Math.Min(Count, 5);
            var builder = new StringBuilder();
            for (var i = 0; i < names; i++)
                builder.Append(this[i]).Append(", ");
            return builder.ToString();
        }
    }

    static void Main()
    {
        var persons = new PersonList();
        for (int i = 0; i < 100000; i++)
        {
            persons.Add(new Person("P" + i.ToString(), RandomString(5, true)));
        } 

        var unsortedPersons = new PersonList(persons);

        const int COUNT = 30;
        Stopwatch watch = new Stopwatch();
        for (int i = 0; i < COUNT; i++)
        {
            watch.Start();
            Sort(persons);
            watch.Stop();
            persons.Clear();
            persons.AddRange(unsortedPersons);
        }
        Console.WriteLine("Sort: {0}ms", watch.ElapsedMilliseconds);

        watch = new Stopwatch();
        for (int i = 0; i < COUNT; i++)
        {
            watch.Start();
            OrderBy(persons);
            watch.Stop();
            persons.Clear();
            persons.AddRange(unsortedPersons);
        }
        Console.WriteLine("OrderBy: {0}ms", watch.ElapsedMilliseconds);

        watch = new Stopwatch();
        for (int i = 0; i < COUNT; i++)
        {
            watch.Start();
            OrderByWithToList(persons);
            watch.Stop();
            persons.Clear();
            persons.AddRange(unsortedPersons);
        }
        Console.WriteLine("OrderByWithToList: {0}ms", watch.ElapsedMilliseconds);
    }

    static void Sort(List<Person> list)
    {
        list.Sort((p1, p2) => string.Compare(p1.Name, p2.Name, true));
    }

    static void OrderBy(List<Person> list)
    {
        var result = list.OrderBy(n => n.Name, new NameComparer()).ToArray();
    }

    static void OrderByWithToList(List<Person> list)
    {
        var result = list.OrderBy(n => n.Name, new NameComparer()).ToList();
    }
}
phoog
fuente
2
Ejecuto el código de prueba ahora en LinqPad 5 (.net 5) y OrderByWithToListtoma el mismo tiempo que OrderBy.
dovid
38

Creo que es importante notar otra diferencia entre Sorty OrderBy:

Supongamos que existe un Person.CalculateSalary()método que requiere mucho tiempo; posiblemente más que incluso la operación de ordenar una lista grande.

Comparar

// Option 1
persons.Sort((p1, p2) => Compare(p1.CalculateSalary(), p2.CalculateSalary()));
// Option 2
var query = persons.OrderBy(p => p.CalculateSalary()); 

La opción 2 puede tener un rendimiento superior, porque solo llama al CalculateSalarymétodo n veces, mientras que la Sortopción puede llamar CalculateSalaryhasta 2 n log ( n ) veces, dependiendo del éxito del algoritmo de ordenación.

Omer Raviv
fuente
4
Esto es cierto, aunque hay una solución a ese problema, a saber, mantener los datos en una matriz y usar la sobrecarga Array.Sort que toma dos matrices, una de claves y la otra de valores. Al completar la matriz de claves, llamará CalculateSalary ntimes. Obviamente, esto no es tan conveniente como usar OrderBy.
phoog
14

En pocas palabras:

Ordenar lista / matriz ():

  • Tipo inestable.
  • Hecho en el lugar.
  • Utilice Introsort / Quicksort.
  • La comparación personalizada se realiza proporcionando un comparador. Si la comparación es cara, puede ser más lenta que OrderBy () (que permite usar claves, ver más abajo).

OrderBy / ThenBy ():

  • Tipo estable.
  • Fuera de lugar.
  • Utilice Quicksort. Quicksort no es un tipo estable. Aquí está el truco: al ordenar, si dos elementos tienen la misma clave, compara su orden inicial (que se ha almacenado antes de ordenar).
  • Permite usar claves (usando lambdas) para ordenar elementos por sus valores (ej x => x.Id.:). Todas las claves se extraen primero antes de ordenar. Esto podría resultar en un mejor rendimiento que usar Sort () y un comparador personalizado.

Fuentes: MDSN , fuente de referencia y repositorio dotnet / coreclr (GitHub).

Algunas de las declaraciones enumeradas anteriormente se basan en la implementación actual del marco .NET (4.7.2). Podría cambiar en el futuro.

tigrou
fuente
0

debe calcular la complejidad de los algoritmos utilizados por los métodos OrderBy y Sort. QuickSort tiene una complejidad de n (log n) como recuerdo, donde n es la longitud de la matriz.

También he buscado orderby's, pero no pude encontrar ninguna información ni siquiera en la biblioteca msdn. si no tiene los mismos valores y clasificación relacionados con una sola propiedad, prefiero usar el método Sort (); si no, use OrderBy.

icaptán
fuente
1
De acuerdo con la documentación actual de MSDN, Sort utiliza 3 algoritmos de clasificación diferentes basados ​​en la entrada. Entre los cuales se encuentra QuickSort. La pregunta sobre el algoritmo OrderBy () está aquí (Quicksort): stackoverflow.com/questions/2792074/…
Thor
-1

Solo quiero agregar que orderby es mucho más útil.

¿Por qué? Porque puedo hacer esto:

Dim thisAccountBalances = account.DictOfBalances.Values.ToList
thisAccountBalances.ForEach(Sub(x) x.computeBalanceOtherFactors())
thisAccountBalances=thisAccountBalances.OrderBy(Function(x) x.TotalBalance).tolist
listOfBalances.AddRange(thisAccountBalances)

¿Por qué comparador complicado? Simplemente ordene según un campo. Aquí estoy ordenando según TotalBalance.

Muy fácil.

No puedo hacer eso con el género. Me pregunto porque. Hazlo bien con orderBy.

En cuanto a la velocidad, siempre es O (n).

user4951
fuente
3
Pregunta: ¿El tiempo O (n) (supongo) en su respuesta se refiere a OrderBy o Comparer? No creo que la clasificación rápida pueda lograr el tiempo O (N).
Kevman