C# de Tri et de comparaison OrderBy

Question

Je peux trier une liste à l'aide de Tri ou Tri. Lequel est le plus rapide? Travaillent tous les deux sur la même algorithme?

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

Answer 1

Non, ils ne sont pas le même algorithme. Pour commencer, le LINQ OrderBy est documenté comme stable (c'est à dire si deux éléments ont le même Name, qu'elles apparaissent dans leur ordre d'origine).

Il dépend également de la mémoire tampon de la requête vs itérer plusieurs fois (LINQ-to-Objets, à moins que vous le tampon, le résultat, sera de nouveau à l'ordre par foreach).

Pour l' OrderBy de la requête, je voudrais aussi être tentés de l'utiliser:

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

( {yourchoice} l'un de l' CurrentCulture, Ordinal ou InvariantCulture).

List<T>.Sort

Cette méthode utilise la Matrice.Trier, qui utilise l'algorithme QuickSort. Cette la mise en œuvre effectue une instable trier, c'est, si deux éléments sont égaux, leur ordre peut ne pas être préservé. En revanche, un tri stable conserve l'ordre des éléments sont égaux.

Enumerable.OrderBy

Cette méthode effectue un tri stable; qui est, si les clés de deux éléments que sont l'égalité, l'ordre des éléments est préservée. En revanche, un tri instable ne permet pas de conserver l'ordre des éléments qui ont la même clé. trier, c'est, si deux éléments sont égaux, leur ordre peut ne pas être préservé. En revanche, un tri stable conserve l'ordre des éléments sont égaux.

Answer 2

Pourquoi ne pas le mesurer:

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

Sur mon ordinateur lorsqu'il est compilé en mode Release, ce programme imprime:

Sort: 1162ms
OrderBy: 1269ms

---

Mise à JOUR:

Comme suggéré par @Stefan voici les résultats de tri d'une grande liste de moins en moins de temps:

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

Impressions:

Sort: 8965ms
OrderBy: 8460ms

Dans ce scénario, il ressemble à OrderBy fonctionne mieux.

---

UPDATE2:

Et avec des noms aléatoires:

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

Où:

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

Rendements:

Sort: 8968ms
OrderBy: 8728ms

Encore OrderBy est plus rapide

Answer 3

Darin Dimitrov réponse montre qu' OrderBy est légèrement plus rapide qu' List.Sort lorsqu'ils sont confrontés à déjà triés à l'entrée. J'ai modifié son code de sorte qu'il à plusieurs reprises trie les données non triées, et OrderBy est dans la plupart des cas, elle est légèrement plus lent.

En outre, l' OrderBy test ToArray de la force de l'énumération de l'Linq agent recenseur, mais que de toute évidence, renvoie un type (Person[]) qui est différent du type d'entrée (List<Person>). J'ai donc relancé le test à l'aide de ToList plutôt que d' ToArray et a obtenu une différence encore plus importante:

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

Le code:

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

Answer 4

Je pense qu'il est important de noter une autre différence entre l' Sort et OrderBy:

Supposons qu'il existe un Person.CalculateSalary() méthode, ce qui prend beaucoup de temps; peut-être plus de même l'opération de tri d'une grande liste.

Comparer

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

Option 2 peuvent avoir des performances supérieures, car il ne s'appelle l' CalculateSalary méthode n fois, alors que l' Sort option pourrait appeler CalculateSalary jusqu'à 2n log(n) fois, en fonction de l'algorithme de tri du succès.

Answer 5

vous devez calculer la complexité des algorithmes utilisés par les méthodes de Tri et de Tri. QuickSort a une complexité en n (log n) que je me souvienne, où n est la longueur du tableau.

j'ai cherché pour l'orderby est trop, mais je ne pouvais pas trouver toutes les informations, même dans la bibliothèque msdn. si vous n'avez pas toutes les mêmes valeurs et le tri liée à une seule propriété, je préfère utiliser Méthode sort (); si ce n'est pas que l'utilisation OrderBy.