Sortowanie list w Scala

Przyglądając się zmaganiom Jacka Laskowskiego z taskassin i programowaniem w Scali postanowiłem podsumować różne sposoby sortowania listy obiektów w Scali.

W przypadku Jacka do posortowania mamy listę zadań zdefinowanych następująco (uprościłem klasę na potrzeby tego wpisu):

case class Task(label: String, due: DateTime)

oraz mamy zdefiniowaną listę obiektów:

val tasks = List(Task("t1", DateTime.now),
                 Task("t2", DateTime.now + 2.hours), 
                 Task("t3", DateTime.now - 2.hours))

Wyjaśnienie: DateTime oraz .hours pochodzą z biblioteki nscala-time opakowującej JodaTime pod kątem Scali.

Na pierwszy rzut oka widzimy, że klasa List oferuje nam trzy metody służące do sortowania:
.sorted - do sortowania obiektów ze zdefiniowaną cechą Ordered
.sortBy - do sortowania obiektów po wybranym polu
.sortWith - do sortowania obiektów po podanej funkcji porównującej

Oczywiście, wybór którą z nich wykorzystamy zależy (lub powienien zależeć) od konteksu biznesowego w którym powstaje nasza aplikacja. Przyjżyjmy się poszczególnym sytuacjom, w których chcielibyśmy sortować obiekty klasy Task:

Przypadek 1. Jeżeli sortowanie zadań będzie zawsze odbywać się jedynie/głównie po polu due, to wykorzystajmy obiektowość i rozszerzmy Task o właściwość Ordered[Task]:

case class Task(label: String, due: DateTime) extends Ordered[Task] {
  def compare(other: Task): Int = this.due.compareTo(other.due)
}

dzięki temu sortowanie listy zadań będzie można wykonać następująco:

val sortedTasks = tasks.sorted

Trudno wyobrazić sobie coś prostrzego z punktu widzenia programisty wykorzystującego obiekty klasy Task.

Przypadek 2.1. Inaczej musimy postąpić, jeżeli przyjmiemy, że zadania można sortować na kilka sposobów, np. dodatkowo po nazwie. W takiej sytuacji można przekazać do metody sorted obiekt klasy Ordering[Task] który zdefiniuje nam sposób porządkowania elementów:

 val sortedTasks = tasks.sorted(new Ordering[Task] {
      def compare(a: Task, b: Task): Int = a.due.compareTo(b.due)
    })

można też wykorzystać metodę upraszczającą tworzenie obiektu Ordering:

val sortedTasks = tasks.sorted(Ordering.fromLessThan[Task](_.due < _.due))

Przypadek 2.2. Powyższe rozwiązanie nie wydaje się być bardzo eleganckie, ale można je wykorzystać do stworzenia wygodnego sposobu sortowania. W tym celu w obiekcie towarzyszącym możemy zdefiniować konkretne sposoby porządkowania wykorzystując Ordering[task]:

case class Task(label: String, due: DateTime)

object Task {
  //pełna składnia dofiniowania funkcji anonimowej
  val orderingByDue = Ordering.fromLessThan((a:Task, b:Task) => a.due < b.due)
  //skrócona notacja sposób definiowania funcji anonimowej
  val orderingByLabel = Ordering.fromLessThan[Task](_.label < _.label) 
}

W takiej sytuacji sortowanie wygląda następująco:

val tasksSortedByDue = tasks.sorted(Task.orderingByDue)
val tasksSortedByLabel = tasks.sorted(Task.orderingByLabel)

Przypadek 3. Jeżeli jednak nie chcemy narzucać programiście jakiego sortowania powinien używać można wykorzystać metodę sortBy, której parametr wskazuje, którego pola klasy należy użyć do sortowania (przez przekazanie settera dla danego pola):

val sortedTasks = tasks.sortBy((t:Task) => t.due)

A jeszcze lepiej użyć skróconej i bardziej czytelnej formy:

val sortedTasks = tasks.sortBy(_.due)

Dodatkowo bardzo zaletą sortBy jest możliwość zdefiniowania większej ilości pól po których ma być sortowana kolekcja (np. sortowanie osób najpierw po nazwisku, a jeżeli są takie same to po imeniu). W tym celu należy przekazać tuple zawierające pola które nas interesują:

val sortedTasks = tasks.sortBy((x) => (x.label, x.due))

W tym przypadku zadania zostaną posortowane według nazwy, a jeżeli kilka zadań będzie miało tę samą nazwę, to zostaną one posortowanie po czasie w ramach tej grupy.

Przypadek 4.1. Jeżeli rozwiązanie z punktu 3. nie jest wystarczające (bo. np sortowanie jest bardziej skomplikowane) metoda sortBy, która przyjmuje funkcję według której zostaną posortowane elementy, będzie jak znalazł:

val sortedTasks = tasks.sortWith((a:Task, b:Task) => a.due < b.due)
val sortedTasks = tasks.sortWith(_.due < _.due)

Przypadek 4.2. Należy także dodać, że w tym przypadku możliwe jest (podobnie jak w przypadku 2.) zdefiniowanie funkcji przekazywanych do sortWith jako elementów obiektu towarzyszącego:

object Task {
  val compareByDue = (a:Task, b:Task) => a.due < b.due
}

I wykorzystanie jej w ten sposób:

val sortedTasks = tasks.sortWith(Task.compareByDue)

Algorytm sortowania Przyglądając się sposobom sortowania list w Scali zacząłem zastanawiać się nad algorytmami wykorzystanymi do sortowania.

Sortowanie sekwencji przez wykorzystanie metod sorted, sortBy i sortWith wykorzystuje algorytm sortowania dostarczany przez JDK, a w szczególności metodę java.util.Arrays.sort(...). Scala przepisuje listę (lub dowolną sekwencję) do zwykłej tablicy i to na niej wykonywane jest sortowanie. Następnie na podstawie tej tablicy tworzona jest sekwencja odpowiedniego typu (np. List).

Metoda sortująca dostarczana przez JDK do sortowania tablicy obiektów wykorzystuje zmodyfikowany algorytm mergesort, który gwarantuje stabilność sortowania oraz złożoność obliczeniową O(n) = n log(n). Dodatkowo w przypadku gdy elementy są już częściowo posortowane wydajność tego algorytmu jest dużo większa.

Należy także zaznaczyć, że java.util.Arrays.sort(...) w przypadku tablic prymitywów wykorzystuje zoptymalizowany algorytm quicksort (inaczej niż w przypadku tablic obiektów, ponieważ w przypadku prymitywów nie musi być on stabilny), jednak aby móc wykorzystać tę możliwość z poziomu Scali należy wywołać tę metodę bezpośrednio, gdyż interfejsy Scali zawsze wywołają metodę dla tablicy obiektów.

Podsumowanie. Osobiście skłaniałbym się ku metodom 1. oraz 2.2. ponieważ umożliwiają zdefiniowanie kontekstu biznesowego, którego programista nie będzie musiał odkrywać za każdym razem, gdy będzie chciał posortować kolekcję (oczywiście mowa o bardzie skomplikowanych przypadkach niż ten w taskassin). Dodatkowo wydaje się że definiują właściwości klasy Task, a nie zestaw zachowań (jak to jest w przypadku pozostałych metod), które mogą jej dotyczyć.

Oczywiście zdaję sobie sprawę, że nie są to wszystkie możliwości sortowania list jakie oferuje Scala, ale myślę, że przedstawiłem te najbardziej użyteczne.