Comparaison C # et OrderBy

Je peux trier une liste en utilisant Trier ou Trier par. Lequel est le plus rapide? Les deux travaillent-ils sur le 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);
    }
}

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, une fois compilé en mode Release, ce programme imprime:

Sort: 1162ms
OrderBy: 1269ms

METTRE À JOUR:

Comme suggéré par @Stefan, voici les résultats du tri d'une grande liste moins de fois:

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 semble que OrderBy fonctionne mieux.

UPDATE2:

Et en utilisant 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

Still OrderBy est plus rapide

Non, ce n'est pas le même algorithme. Pour commencer, le LINQ OrderByest documenté comme stable (c'est-à-dire que si deux éléments ont le même Name, ils apparaîtront dans leur ordre d'origine).

Cela dépend également de la mise en mémoire tampon de la requête ou de l'itération plusieurs fois (LINQ-to-Objects, à moins que vous ne tamponniez le résultat, sera réorganisé par foreach).

Pour la OrderByrequête, je serais également tenté d'utiliser:

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

(pour l' {yourchoice}un des CurrentCulture, Ordinalou InvariantCulture).

List<T>.Sort

Cette méthode utilise Array.Sort, qui utilise l'algorithme QuickSort. Cette implémentation effectue un tri instable; autrement dit, si deux éléments sont égaux, leur ordre peut ne pas être conservé. En revanche, un tri stable préserve l'ordre des éléments égaux.

Enumerable.OrderBy

Cette méthode effectue un tri stable; autrement dit, si les clés de deux éléments sont égales, l'ordre des éléments est conservé. En revanche, un tri instable ne préserve pas l'ordre des éléments qui ont la même clé. Trier; autrement dit, si deux éléments sont égaux, leur ordre peut ne pas être conservé. En revanche, un tri stable préserve l'ordre des éléments égaux.

La réponse de Darin Dimitrov montre que OrderByc'est légèrement plus rapide que List.Sortface à des entrées déjà triées. J'ai modifié son code pour qu'il trie à plusieurs reprises les données non triées, et OrderByest dans la plupart des cas légèrement plus lent.

De plus, le OrderBytest utilise ToArraypour forcer l'énumération de l'énumérateur Linq, mais cela renvoie évidemment un type ( Person[]) qui est différent du type d'entrée ( List<Person>). J'ai donc relancé le test en utilisant ToListplutôt que ToArrayet j'ai obtenu une différence encore plus grande:

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

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

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

Comparer

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

L'option 2 peut avoir des performances supérieures, car elle n'appelle la CalculateSalaryméthode que n fois, alors que l' Sortoption peut appeler CalculateSalaryjusqu'à 2 n fois log ( n ) , en fonction du succès de l'algorithme de tri.

En un mot :

Trier par liste / tableau ():

• Tri instable.
• Fait sur place.
• Utilisez Introsort / Quicksort.
• La comparaison personnalisée est effectuée en fournissant un comparateur. Si la comparaison est coûteuse, elle peut être plus lente que OrderBy () (qui permet d'utiliser des clés, voir ci-dessous).

OrderBy / ThenBy ():

• Tri stable.
• Pas en place.
• Utilisez Quicksort. Quicksort n'est pas une sorte stable. Voici l'astuce: lors du tri, si deux éléments ont la même clé, il compare leur ordre initial (qui a été stocké avant le tri).
• Permet d'utiliser des clés (en utilisant des lambdas) pour trier les éléments sur leurs valeurs (par exemple:) x => x.Id. Toutes les clés sont extraites avant le tri. Cela peut entraîner de meilleures performances que l'utilisation de Sort () et d'un comparateur personnalisé.

Sources: MDSN , source de référence et référentiel dotnet / coreclr (GitHub).

Certaines des instructions répertoriées ci-dessus sont basées sur l'implémentation actuelle du framework .NET (4.7.2). Cela pourrait changer à l'avenir.

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

J'ai aussi recherché orderby, mais je n'ai trouvé aucune information, même dans la bibliothèque msdn. si vous n'avez pas les mêmes valeurs et le tri lié à une seule propriété, je préfère utiliser la méthode Sort (); sinon, utilisez OrderBy.

Je veux juste ajouter que orderby est bien plus utile.

Pourquoi? Parce que je peux faire ceci:

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

Pourquoi un comparateur compliqué? Triez simplement en fonction d'un champ. Ici, je trie en fonction de TotalBalance.

Très facile.

Je ne peux pas faire ça avec tri. Je me demande pourquoi. Faites bien avec orderBy.

Quant à la vitesse, c'est toujours O (n).