C# sortować wydajność sortowania

Question

tylko krótka notatka, to nie jest praca domowa. Próbuję odświeżyć moje algorytmy. Mam zabawy z mergesort w C# i pisałem rekurencyjnej metody, które można sortować w oparciu o rodzajowych:

class SortAlgorithms 
{ 

    public T[] MergeSort<T> (T[] unsortedArray) where T : System.IComparable<T> 
    { 
     T[] left, right; 
     int middle = unsortedArray.Length/2; 

     left = new T[middle]; 
     right = new T[unsortedArray.Length - middle]; 

     if (unsortedArray.Length <= 1) 
      return unsortedArray; 

     for (int i = 0; i < middle; i++) 
     { 
      left[i] = unsortedArray[i]; 
     } 

     for (int i = middle; i < unsortedArray.Length; i++) 
     { 
      right[i - middle] = unsortedArray[i]; 
     } 

     left = MergeSort(left); 

     right = MergeSort(right); 


     return Merge<T>(left, right); 
    } 

    private T[] Merge<T> (T[] left, T[] right) where T : System.IComparable<T> 
    { 
     T[] result = new T[left.Length + right.Length]; 

     int currentElement = 0; 

     while (left.Length > 0 || right.Length > 0) 
     { 
      if (left.Length > 0 && right.Length > 0) 
      { 
       if (left[0].CompareTo(right[0]) < 0) 
       { 
        result[currentElement] = left[0]; 
        left = left.Skip(1).ToArray(); 
        currentElement++; 
       } 
       else 
       { 
        result[currentElement] = right[0]; 
        right = right.Skip(1).ToArray(); 
        currentElement++; 
       } 
      } 
      else if (left.Length > 0) 
      { 
       result[currentElement] = left[0]; 
       left = left.Skip(1).ToArray(); 
       currentElement++; 
      } 
      else if (right.Length > 0) 
      { 
       result[currentElement] = right[0]; 
       right = right.Skip(1).ToArray(); 
       currentElement++; 
      } 
     } 

     return result; 
    } 
} 

To działa, ale to jest strasznie powolna. Użyłem System.Diagnostic.StopWatch do sprawdzenia wydajności w stosunku do Array.Sort (który używa algorytmu QuickSort) do porównania z moim MergeSort i różnica jest tak znacząca Zastanawiam się, czy może wprowadzam to źle. Wszelkie komentarze?

Answer 1

Nie jestem programistą C#, ale czy problemem może być użycie takich instrukcji?

left = left.Skip(1).ToArray(); 

Może to zostać zaimplementowane w sposób wymuszający głęboką kopię podstawowej tablicy. Jeśli tak, spowodowałoby to spadek wydajności scalania z O (n) do O (n), natychmiastowo obniżając wydajność wynikowego sortowania scalającego z O (n log n) do O (n).

(Jest tak z powodu zmian nawrotów z

T = (1) O (1)

T (n) ≤ 2T (n/2) + O (n)

który ma rozwiązanie T (n) = O (n log n) do

T = (1) O (1)

T (n) ≤ 2T (n/2) + O (n)

który ma rozwiązanie T (n) = O (N)).

Answer 2

Jesteś stale alokacji pamięci w postaci pośrednich tablic. Zastanów się nad ponownym użyciem oryginalnej tablicy.

Answer 3

Jako pozostałe dwie odpowiedzi powiedziały, że tworzysz nowe tablice w całym miejscu, poświęcając na to mnóstwo czasu i pamięci (prawdopodobnie zgaduję, że większość czasu i prawie wszystkie twoje wykorzystanie pamięci).

Na to jeszcze raz dodam, że wszystkie pozostałe rekordy są równe wolniejsze od iteracji, i używają więcej przestrzeni stosu (może nawet powodując przepełnienie z wystarczająco dużym problemem, w którym iteracja nie byłaby).

Jednak. Merge-sort nadaje się również do podejścia wielowątkowego, ponieważ możesz mieć różne wątki obsługujące różne części pierwszej partii partycjonowania.

Stąd gdyby ja grając z tego, moi Kolejne dwa eksperymenty byłyby:

1. Do pierwszego bitu podziału, zamiast dzwonić MergeSort rekurencyjnie, chciałbym rozpocząć nowy wątek aż takie czas, w którym miałem wątek na rdzeń działający (czy powinienem to zrobić na fizyczny rdzeń lub wirtualny rdzeń w przypadku hiperwątkowości, sam jest czymś, z czym eksperymentowałem).
2. Po wykonaniu tego, spróbuję ponownie napisać metodę rekursywną, aby zrobić to samo bez wywołań rekursywnych.

Po sprawa ToArray() została rozpatrzona, widząc, jak wielowątkowe podejście, że najpierw podzielić pracę wśród optymalnej liczby rdzeni, a następnie miał każdy rdzeń zrobić swoją pracę iteracyjnie, może być rzeczywiście bardzo interesujące.

Answer 4

Po pierwsze, oto link do usprawnione rozwiązania z podobnym pytaniem: Java mergesort, should the "merge" step be done with queues or arrays?

Twoje rozwiązanie jest powolny, ponieważ jesteś wielokrotnie przydzielania nowych subarrays. Alokacja pamięci jest znacznie droższa niż w przypadku większości innych operacji (masz koszt alokacji, koszt zbierania i utratę pamięci podręcznej). Zwykle nie jest to problemem, ale jeśli próbujesz zakodować ścisłą rutynę sortowania, liczy się to. W przypadku sortowania scalonego potrzebujesz tylko jednej tablicy docelowej i jednej tablicy tymczasowej.

Rozwinięcie nici do parallelise jest wciąż o rząd wielkości droższe. Więc nie rozwidlaj, chyba że masz ogromną ilość danych do posortowania.

Jak już wspomniałem w powyższej odpowiedzi, jednym ze sposobów przyspieszenia sortowania scalania jest wykorzystanie istniejącego porządku w tablicy wejściowej.