Narzędzie listy <T> .Sort() kontra Lista <T> .OrderBy() dla członka niestandardowej klasy kontenera

Question

Znaleźliśmy się z powrotem przez stary kod legacy ze starszej wersji 3.5 i znalazłem punkty, w których występuje całość pęczek list i słowników, które muszą być aktualizowane w zsynchronizowany sposób. Stwierdziłem, że mogę uczynić ten proces nieskończenie łatwiejszym zarówno do wykorzystania, jak i zrozumienia, poprzez zsumowanie tych niestandardowych klas nowych klas niestandardowych. Są jednak pewne punkty, w których doszedłem do obaw związanych z porządkowaniem zawartości tych nowych klas kontenerów za pomocą określonej właściwości wewnętrznej. Na przykład sortowanie według właściwości numeru ID jednej klasy.

Ponieważ klasy kontenerów oparte są przede wszystkim na ogólnym obiekcie List, moim pierwszym instynktem było napisanie klas wewnętrznych za pomocą IComparable i napisanie metody CompareTo, która porównuje właściwości. W ten sposób mogę po prostu zadzwonić pod numer items.Sort(), kiedy chcę wywołać sortowanie.

Zamiast tego zamiast tego zastanawiałem się zamiast używać items = items.OrderBy(Func). W ten sposób jest bardziej elastyczny, jeśli muszę sortować według dowolnej innej własności. Czytelność jest lepsza, ponieważ właściwość używana do sortowania będzie wyświetlana w kolejności z wywołaniem sortowania, zamiast konieczności wyszukiwania kodu IComparable. W rezultacie ogólna realizacja wydaje się czystsza.

Nie dbam o przedwczesną lub mikrooptymalizację, ale lubię konsystencję. Uważam, że najlepiej jest trzymać się jednego rodzaju implementacji w tylu przypadkach, ile jest to właściwe, i używać różnych implementacji tam, gdzie jest to konieczne. Czy warto przekonwertować mój kod, aby użyć LINQ OrderBy zamiast używać List.Sort? Czy lepszą praktyką jest pozostawanie przy implementacji IComparable dla tych niestandardowych kontenerów? Czy istnieją jakieś istotne mechaniczne korzyści oferowane przez którąkolwiek ścieżkę, którą powinienem rozważyć decyzję? Czy też ich funkcjonalność końcowa jest równoważna z tym, że po prostu staje się ona preferencją programisty?

Answer 1

Najważniejszą kwestią jest to, że sortowanie List<T>.Sort() jest na miejscu. Jeśli twoja lista jest wystawiona na zewnętrzny kod, zawsze będzie reprezentować ten sam obiekt do tego kodu. Jest to ważne, jeśli lista jest przechowywana w polu według kodu spoza klasy kontenera. Jeśli sortujesz z OrderBy(), za każdym razem otrzymasz nowe wyliczenie, zastępując poprzednie items. Każda wcześniej zapisana lista nie będzie reprezentować aktualnego stanu twojej klasy.

Biorąc pod uwagę wydajność, OrderBy będzie musiał powtórzyć całą listę, aby posortować elementy. Następnie wywołasz ToList(), aby utworzyć nową listę z tego wyliczenia, iterując po liście po raz drugi. Dodatkowo, ponieważ jest to wyliczenie, List użyje algorytmu podwojenia, zwiększając jego rozmiar, aż każdy element może do niego pasować. W przypadku dużej listy może to być sporo przydziałów i kopiowanie pamięci. Spodziewam się, że wydajność będzie znacznie gorsza niż List<T>.Sort().

Edit: Mały odniesienia:

internal class Program { 

    private static List<int> CreateList(int size) { 

     // use the same seed so that every list has the same elements 
     Random random = new Random(589134554); 

     List<int> list = new List<int>(size); 
     for (int i = 0; i < size; ++i) 
      list.Add(random.Next()); 
     return list; 
    } 

    private static void Benchmark(int size, bool output = true) { 
     List<int> list1 = CreateList(size); 
     List<int> list2 = CreateList(size); 

     Stopwatch stopwatch = Stopwatch.StartNew(); 
     list1.Sort(); 
     stopwatch.Stop(); 
     double elapsedSort = stopwatch.Elapsed.TotalMilliseconds; 
     if (output) 
      Console.WriteLine("List({0}).Sort(): {1}ms (100%)", size, elapsedSort); 

     stopwatch.Restart(); 
     list2.OrderBy(i => i).ToList(); 
     stopwatch.Stop(); 
     double elapsedOrderBy = stopwatch.Elapsed.TotalMilliseconds; 
     if (output) 
      Console.WriteLine("List({0}).OrderBy(): {1}ms ({2:.00%})", size, elapsedOrderBy, elapsedOrderBy/elapsedSort); 

    } 

    internal static void Main() { 

     // ensure linq library is loaded and initialized 
     Benchmark(1000, false); 

     Benchmark(10); 
     Benchmark(100); 
     Benchmark(1000); 
     Benchmark(10000); 
     Benchmark(100000); 
     Benchmark(1000000); 

     Console.ReadKey(); 
    } 
} 

wyjściowa (znormalizowane do List.Sort):

List(10).Sort(): 0,0025ms (100%) 
List(10).OrderBy(): 0,0157ms (628,00%) 
List(100).Sort(): 0,0068ms (100%) 
List(100).OrderBy(): 0,0294ms (432,35%) 
List(1000).Sort(): 0,0758ms (100%) 
List(1000).OrderBy(): 0,3107ms (409,89%) 
List(10000).Sort(): 0,8969ms (100%) 
List(10000).OrderBy(): 4,0751ms (454,35%) 
List(100000).Sort(): 10,8541ms (100%) 
List(100000).OrderBy(): 50,3497ms (463,88%) 
List(1000000).Sort(): 124,1001ms (100%) 
List(1000000).OrderBy(): 705,0707ms (568,15%) 

Answer 2

Jak powiedział Julien, Sort() prawdopodobnie będzie szybsze, jednak skoro wspomniałeś lepszą czytelność i elastyczność funkcji OrderBy() można osiągnąć również za pomocą metody Sort() (przynajmniej jeśli właściwość, którą chcesz oprzeć na sortowaniu, jest porównywalna)

items = items.OrderBy(x => x.Name).ToList(); 
items.Sort((x,y) => x.Name.CompareTo(y.Name)); // If x.Name is never null 
items.Sort((x,y) => String.Compare(x.Name, y.Name)); // null safe