list.sort performances IComparer

Question

Je suis en train de trier une paire de tableaux int (int [] a; int [] b;)

Si je Array.Sort (a, b), alors la performance est génial.

Cependant, je préférerais utiliser une liste <> et charger les paires int dans une structure. Je peux obtenir ceci pour fonctionner en utilisant Array.Sort() avec une surcharge qui fournit un comparateur simple pour la structure mais c'est environ 4 fois plus lent que le Array.Sort (a, b)

Est-ce normal?

Answer 1

Cela semble réaliste; vous introduisez plus de complexité (plus de recherches etc, plus de méthodes virtuelles, plus de contrôles de gamme), donc ça ne peut que ralentir (l'accès au tableau est très direct et très rapide).

Il semble que vous puissiez l'obtenir un peu plus rapidement (mais pas aussi rapidement que le tableau) en implémentant un IComparer<T> au lieu de l'approche déléguée; (modifier) et plus rapide à nouveau en utilisant IComparable<T>:

Array.Sort: 2241ms 
List.Sort (delegate): 8714ms 
List.Sort (interface): 6976ms 
List.Sort (comparable): 5456ms 

Avec code:

using System; 
using System.Collections.Generic; 
using System.Diagnostics; 

struct MyStruct : IComparable<MyStruct> 
{ 
    private readonly int key, value; 
    public int Key { get { return key; } } 
    public int Value { get { return value; } } 
    public MyStruct(int key, int value) 
    { 
     this.key = key; 
     this.value = value; 
    } 
    public int CompareTo(MyStruct other) 
    { 
     return key.CompareTo(other.key); 
    } 
} 
static class Program 
{ 
    static void Main() 
    { 
     const int SIZE = 10000000; 
     int[] a = new int[SIZE], b = new int[SIZE]; 
     Random rand = new Random(); 
     for(int i = 0 ; i < SIZE ; i++) { 
      a[i] = rand.Next(); 
      b[i] = i; 
     } 
     var list = new List<MyStruct>(SIZE); 
     for (int i = 0; i < SIZE; i++) 
     { 
      list.Add(new MyStruct(a[i], b[i])); 
     } 
     var list2 = new List<MyStruct>(list); 
     var list3 = new List<MyStruct>(list); 

     var watch = Stopwatch.StartNew(); 
     Array.Sort(a, b); 
     watch.Stop(); 
     Console.WriteLine("Array.Sort: " + watch.ElapsedMilliseconds + "ms"); 

     watch = Stopwatch.StartNew(); 
     list.Sort((x, y) => x.Key.CompareTo(y.Key)); 
     watch.Stop(); 
     Console.WriteLine("List.Sort (delegate): " + watch.ElapsedMilliseconds + "ms"); 

     watch = Stopwatch.StartNew(); 
     list2.Sort(MyComparer.Default); 
     watch.Stop(); 
     Console.WriteLine("List.Sort (interface): " + watch.ElapsedMilliseconds + "ms"); 

     watch = Stopwatch.StartNew(); 
     list3.Sort(); 
     watch.Stop(); 
     Console.WriteLine("List.Sort (comparable): " + watch.ElapsedMilliseconds + "ms"); 
    } 
    sealed class MyComparer : IComparer<MyStruct> 
    { 
     private MyComparer() { } 
     public static readonly MyComparer Default = new MyComparer(); 
     public int Compare(MyStruct x, MyStruct y) 
     { 
      return x.Key.CompareTo(y.Key); 
     } 
    } 
}