Niezadowalającą alternatywą byłoby zablokowanie każdego porównania do momentu oceny przyszłości. Jeśli ocena predykatu sortowania jest kosztowna, sortowanie zajmie dużo czasu. W rzeczywistości przekłada to prawdopodobnie program współbieżny na sekwencyjny; wszystkie korzyści z używania kontraktów terminowych zostaną utracone.
import scala.concurrent.duration._
implicit val executionContext = ExecutionContext.Implicits.global
val sortingPredicate: (Int, Int) => Future[Boolean] = (a, b) => Future{
Thread.sleep(20) // Assume this is a costly comparison
a < b
}
val unsorted = List(4, 2, 1, 5, 7, 3, 6, 8, 3, 12, 1, 3, 2, 1)
val sorted = unsorted.sortWith((a, b) =>
Await.result(sortingPredicate(a, b), 5000.millis) // careful: May throw an exception
)
println(sorted) // List(1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 6, 7, 8, 12)
Nie wiem, czy jest się z roztworu, który wykorzystuje pole asynchroniczny porównanie. Możesz jednak spróbować zaimplementować własny algorytm sortowania. Jeśli weźmiemy pod uwagę Quicksort, który działa przeciętnie w O(n log(n)), możemy faktycznie wykorzystać porównanie asynchroniczne dość łatwo.
Jeśli nie jesteś zaznajomiony z Quicksort algorytm zasadzie wykonuje następujące
- Wybierz element z kolekcji (zwanej Pivot)
- Porównaj pivot ze wszystkimi pozostałymi elementami. Utwórz kolekcję z elementami mniejszymi niż oś przestawna i jedną z elementami, które są większe niż oś przestawna.
- Porządkuj dwie nowe kolekcje i połącz je, umieszczając oś obrotu pośrodku.
Ponieważ w kroku 2 wykonano wiele niezależnych porównań, możemy jednocześnie dokonać porównania porównań.
Oto unoptimized realizacja:
object ParallelSort {
val timeout = Duration.Inf
implicit class QuickSort[U](elements: Seq[U]) {
private def choosePivot: (U, Seq[U]) = elements.head -> elements.tail
def sortParallelWith(predicate: (U, U) => Future[Boolean]): Seq[U] =
if (elements.isEmpty || elements.size == 1) elements
else if (elements.size == 2) {
if (Await.result(predicate(elements.head, elements.tail.head), timeout)) elements else elements.reverse
}
else {
val (pivot, other) = choosePivot
val ordering: Seq[(Future[Boolean], U)] = other map { element => predicate(element, pivot) -> element }
// This is where we utilize asynchronous evaluation of the sorting predicate
val (left, right) = ordering.partition { case (lessThanPivot, _) => Await.result(lessThanPivot, timeout) }
val leftSorted = left.map(_._2).sortParallelWith(predicate)
val rightSorted = right.map(_._2).sortParallelWith(predicate)
leftSorted ++ (pivot +: rightSorted)
}
}
}
które mogą być wykorzystane (sam przykład jak powyżej) w następujący sposób:
import ParallelSort.QuickSort
val sorted2 = unsorted.sortParallelWith(sortingPredicate)
println(sorted2) // List(1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 6, 7, 8, 12)
Zauważ, że czy to wdrożenie QuickSort jest szybciej lub wolniej niż Całkowicie sekwencyjny wbudowany algorytm sortowania bardzo zależy od kosztu porównania: im dłużej porównanie musi blokować, tym gorsze jest wspomniane wyżej rozwiązanie alternatywne. Na moim komputerze, biorąc pod uwagę kosztowne porównanie (20 milisekund) i powyższą listę, wbudowany algorytm sortowania działa w ~ 1200 ms, podczas gdy ten niestandardowy Quicksort działa w ~ 200 ms. Jeśli martwisz się o wydajność, prawdopodobnie chcesz wymyślić coś mądrzejszego. Edycja: Właśnie sprawdziłem, ile porównań zarówno wbudowany algorytm sortowania, jak i niestandardowy algorytm Quicksort wykonują: Podobno dla danej listy (i kilku innych list wpisywanych losowo) wbudowany algorytm wykorzystuje więcej porównań, więc poprawa wydajności dzięki równoległemu wykonaniu może nie być tak wielka. Nie wiem o większych listach, ale i tak musisz je profilować na swoich konkretnych danych.
Wstępne obliczanie kolejności wszystkich par wymaga porównań 'n^2', podczas gdy większość algorytmów sortowania działa w' n log (n) ', więc nie chciałbyś tego robić. –
To było moje podejrzenie! Zdecydowanie zły pomysł (TM). – jackweirdy