Scala - ordinamento basato sul predicato dei risultati futuri

Question

Ho una matrice di oggetti che desidero ordinare, in cui il predicato per l'ordinamento è asincrono. Scala ha una funzione di libreria standard o di terze parti per l'ordinamento basato su un predicato con la firma del tipo di (T, T) -> Future[Bool] anziché solo (T, T) -> Bool?

In alternativa, esiste un altro modo per strutturare questo codice? Ho considerato di trovare tutte le permutazioni a 2 coppie degli elementi di lista, eseguendo il predicato su ogni coppia e archiviando il risultato in un Map((T, T), Bool) o una struttura in tal senso, e quindi l'ordinamento su di esso - ma ho il sospetto che avrà molti più confronti eseguito anche solo un ingenuo algoritmo di ordinamento.

Answer 1

Se il predicato è asincrona si può scegliere di ottenere un risultato asincrona troppo e di evitare le discussioni di blocco utilizzando Await

Se si desidera ordinare un List[(T,T)] secondo un futuro predicato booleano, il più facile a ordinare una List[(T,T,Boolean)]

Quindi dato un hai un List[(T,T)] e un predicato (T, T) -> Future[Bool], come puoi ottenere un List[(T,T,Boolean)]? O piuttosto un Future[List[(T,T,Boolean)]] come si desidera mantenere il comportamento asincrono.

val list: List[(T,T)] = ... 
val predicate = ... 
val listOfFutures: List[Future[(T,T,Boolean]] = list.map { tuple2 => 
    predicate(tuple2).map(bool => (tuple2._1, tuple2._2, bool) 
} 
val futureList: Future[List[(T,T,Boolean)]] = Future.sequence(listOfFutures) 
val futureSortedResult: Future[List[(T,T)]] = futureList.map { list => 
    list.sort(_._3).map(tuple3 => (tuple3._1,tuple3._2)) 
} 

Questa è pseudo-codice, non ho compilo esso e non può, ma si ottiene l'idea.

La chiave è Future.sequence, molto utile, che permette in qualche modo di trasformare Monad1[Monad2[X]]-Monad2[Monad1[X]] meno di notare che se qualcuno del vostro futuro predicato falliscono, l'operazione di ordinamento globale sarà anche un fallimento.

---

Se si desidera migliorare le prestazioni, può essere una soluzione migliore per "batch" la chiamata al servizio di restituzione del Future[Boolean]. Ad esempio invece di (T, T) -> Future[Bool] forse puoi progettare un servizio (se lo possiedi ovviamente) come List[(T, T)] -> Future[List[(T,T,Bool)] in modo da poter ottenere tutto ciò che ti serve in una singola chiamata asincrona.

Answer 2

Un'alternativa non così soddisfacente sarebbe quella di bloccare ogni confronto fino a quando il futuro non viene valutato. Se la valutazione del predicato di smistamento è costosa, l'ordinamento richiederà molto tempo. In realtà, questo si traduce semplicemente in un programma possibilmente concorrente in uno sequenziale; tutti i benefici derivanti dall'uso dei future andranno persi.

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) 

---

Non so se c'è un out della soluzione di dialogo che utilizza il confronto asincrono. Tuttavia, potresti provare a implementare il tuo algoritmo di ordinamento. Se consideriamo Quicksort, che viene eseguito in media in O(n log(n)), possiamo effettivamente utilizzare il confronto asincrono in modo piuttosto semplice.

Se non hai familiarità con Quicksort, l'algoritmo fa sostanzialmente il seguente

1. selezionare un elemento di raccolta (chiamato Pivot)
2. Confrontare il perno con tutti gli elementi rimanenti. Crea una raccolta con elementi inferiori al pivot e uno con elementi maggiori del pivot.
3. Ordinare le due nuove raccolte e concatenarle, mettendo il perno nel mezzo.

Poiché il passaggio 2 esegue molti confronti indipendenti, è possibile valutare i confronti contemporaneamente.

Ecco un'implementazione non ottimizzato:

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) 
     } 
    } 

} 

che può essere utilizzato (stesso esempio di sopra) come segue:

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) 

Si noti che se questa implementazione del Quicksort è più veloce o più lento rispetto l'algoritmo di ordinamento integrato completamente sequenziale dipende molto dal costo di un confronto: quanto più un confronto deve essere bloccato, tanto peggio è la soluzione alternativa sopra menzionata. Sulla mia macchina, dato un confronto costoso (20 millisecondi) e l'elenco precedente, l'algoritmo di ordinamento incorporato viene eseguito in ~ 1200 ms mentre questo Quicksort personalizzato viene eseguito in ~ 200 ms. Se sei preoccupato per le prestazioni, probabilmente vorrai inventare qualcosa di più intelligente. Modifica: Ho appena controllato quanti confronti, l'algoritmo di ordinamento integrato e l'algoritmo Quicksort personalizzato eseguono: Apparentemente, per l'elenco fornito (e alcuni altri elenchi che ho digitato a caso) l'algoritmo incorporato utilizza più confronti, quindi i miglioramenti delle prestazioni grazie all'esecuzione parallela potrebbero non essere grandiosi. Non so di liste più grandi, ma dovresti comunque indicarle sui tuoi dati specifici.