QuickSort non può essere applicato a ArrayBuffer per eseguire l'ordinamento In posto in Scala

Question

Sono poco confuso con QuickSort in Scala. Secondo le specifiche, QuickSort può essere applicato solo alla matrice, ma non a ArrayBuffer. E QuickSort eseguirà l'ordinamento in Place i.e. cambierà la matrice originale.

val intArray = Array(7,1,4,6,9)   //> intArray : Array[Int] = Array(7, 1, 4, 6, 9) 
Sorting.quickSort(intArray) 
intArray.mkString("<"," and ",">")  //> res4: String = <1 and 4 and 6 and 7 and 9> 

Ora non riesco a capire perché lo stesso non possa fare con ArrayBuilder. C'è qualche ragione dietro a questo? e Se voglio ordinare un ArrayBuilder con QuickSort Algorithm, qual è l'opzione fornita da scala? Grazie per tutto l'aiuto.

Answer 1

Credo che la risposta alla tua domanda può essere trovata esaminando il codice sorgente di Scala, per determinare che cosa comportamento si può ottenere dal costruito nelle funzioni che vengono con ArrayBuffer: sortWith, sortby, ecc ..

Queste funzioni derivano dalla definizione di tratto "SeqLike" (puoi esaminare il codice sorgente sfogliando quella classe in ScalaDoc e facendo clic sul link accanto alla fonte: "Seqlike" nella parte superiore della documentazione ..

la maggior parte del codice relativo all'ordinamento viene semplicemente espulsa da questa funzione:

def sorted[B >: A](implicit ord: Ordering[B]): Repr = { 
    val len = this.length 
    val arr = new ArraySeq[A](len) 
    var i = 0 
    for (x <- this.seq) { 
     arr(i) = x 
     i += 1 
    } 
    java.util.Arrays.sort(arr.array, ord.asInstanceOf[Ordering[Object]]) 
    val b = newBuilder 
    b.sizeHint(len) 
    for (x <- arr) b += x 
    b.result() 
    } 

Che fondamentalmente fa una copia dell'array e lo ordina utilizzando Java.util.Arrays.Sort. Quindi la prossima domanda diventa: "Cosa sta facendo java qui?" Ero curioso e l'API descriveva:

Nota di implementazione: L'algoritmo di ordinamento è un Quicksort Dual-Pivot di Vladimir Yaroslavskiy, Jon Bentley e Joshua Bloch. Questo algoritmo offre prestazioni O (n log (n)) su molti set di dati che fanno sì che altri quicksorts degradino a prestazioni quadratiche, e in genere è più veloce rispetto alle implementazioni Quicksort tradizionali (one-pivot).

Quindi penso che la risposta di base è che scala si basa molto su Java incorporato nel quicksorting, e si può fare uso di una qualsiasi funzione Seq (ordinati, sortWith, sortby) con migliori prestazioni o uguale a funzioni di matrice Quicksort. Potresti ottenere un po 'di successo nelle prestazioni nella fase di "copia", ma le classi sono solo dei puntatori (non clonazione degli oggetti) in modo da non perdere molto se non hai milioni di elementi.