Scala Collection sortowane, sortWith i SortBy Wydajność

Question

Scala zawiera kilka metod w standardowej biblioteki do sortowania listy, na przykład, aby posortować listę lista , można użyć:

list.sorted 
list.sortWith(_<_) 
list.sortBy(x=>x) 

Choć mogą one być Najprostsze sposoby sortowania listy, zauważyłem, że w przypadku większych list mają znaczący wady wydajności.

Na przykład, aby posortować milion liczb całkowitych, posortowane zajmuje średnio 500 ms, podczas sortowania i sortowania zajmuje około 700 ms. Jest to porównywane do scala.util.Sorting.quickSort, które trwa około 120ms i java.util.Arrays.sort, które zajmuje około 100ms. W przypadku większych list, ta różnica wielu czynników jest obserwowana, gdy skalujemy dalej. Wzór jest pokazany w poniższej tabeli.

Co jest powodem tego opóźnienia w wydajności? I dlaczego nie są bardziej wydajne algorytmy/implementacje używane dla standardowych metod?

Answer 1

Należy zauważyć, że linie mają takie same nachylenie, ale są przesunięte względem siebie? W skali logarytmicznej obserwujemy stałą różnicę czynników. sorted i przyjaciele płacą koszt konwersji List do Array, sortowania (z java.util.Arrays.sort, w rzeczywistości), i konwersji z powrotem do List. scala.util.Sorting.quickSort i java.util.Arrays.sort działają bezpośrednio na tablicach. Współczynnik log n w wydajności Quicksorta n log n jest w dużej mierze nieistotny, więc przy liniowym czasie potrzebnym do utworzenia tablicy i wynikowej listy uzyskujemy stałą różnicę współczynników. Pięć razy gorsza wydajność może wyglądać okropnie, ale pamiętaj, że List ma komórkę cons dla każdego elementu, co powoduje ogromne ilości dostępu losowego podczas tworzenia Array, a następnie utworzenie nowego List wymaga czasu poświęconego na przydzielanie pamięci i, według wszelkiego prawdopodobieństwa, cykl zbierania śmieci lub dwa.

Dla list prymitywów jest jeszcze gorzej. List jest ogólna, więc wszelkie prymitywy muszą być w ramkach, co dodaje kolejną warstwę pośrednią. I niestety utworzony Array również posiada wartości w ramkach. W efekcie, ostatecznie sortujesz Array[java.lang.Integer], kiedy naprawdę chcesz sortować Array[Int].

Podsumowując: algorytmy sortowania są identyczne, ale istnieją uzasadnione powody, dla których zmienne tablice przewyższają niezmienne, pojedynczo połączone listy.