Scala ParArray tri

Question

Comment trier dans l'ordre croissant une collection ParArray tels que

ParArray(1,3,2) 

ou bien, les collections parallèles peuvent être plus appropriés à cet effet?

Mise à jour

Comment mettre en œuvre un algorithme parallèle sur ParArray qui peut se révéler plus efficace que la coulée à une collection non parallèle pour le tri séquentiel?

Answer 1

Comment mettre en œuvre un algorithme parallèle sur ParArray qui peut se révéler plus efficace que coulée à une collection non parallèle pour le tri séquentiel ?

Ma première obvervation serait qu'il ne semble pas être la peine beaucoup de performance pour « convertir » tableaux parallèles à séquentiel et arrière:

def time[R](block: => R): R = { 
    val t0 = System.nanoTime() 
    val result = block // call-by-name 
    val t1 = System.nanoTime() 
    val diff: Long = t1 - t0 
    println(s"Elapsed time: ${diff * 1.0/1E9}s") 
    result 
} 

def main(args: Array[String]): Unit = { 
    val size: Int = args.headOption.map(_.toInt).getOrElse(1000000) 
    val input = Array.fill(size)(Random.nextInt()) 
    val arrayCopy: Array[Int] = Array.ofDim(size) 
    input.copyToArray(arrayCopy) 
    time { input.sorted } 
    val parArray = arrayCopy.par 
    val result = time { parArray.seq.sorted.toArray.par } 
} 

donne

> run 1000000 
[info] Running Runner 1000000 
Elapsed time: 0.344659236s 
Elapsed time: 0.321363896s 

Pour tous Array tailles J'ai testé les résultats sont très similaires et généralement en faveur de la seconde expression. Donc, au cas où vous craigniez que la conversion en collections séquentielles et en arrière tue les gains de performance que vous avez obtenus sur d'autres opérations - je ne pense pas que vous devriez l'être. Quand il s'agit d'utiliser les collections parallèles de Scala pour réaliser un tri parallèle qui, dans certains cas, fonctionnerait mieux que la configuration par défaut, je ne pense pas qu'il existe une bonne façon de le faire, mais cela ne ferait pas mal d'essayer: Ce que je pensais devoir travailler serait de diviser le tableau d'entrée en autant de sous-réseaux que vous avez de cœurs dans votre ordinateur (de préférence sans copie inutile) et de trier les parties simultanément. Ensuite, on pourrait fusionner (comme dans merge sort) les parties ensemble. Voici comment le code pourrait ressembler à:

val maxThreads = 8 //for simplicity we're not configuring the thread pool explicitly 
val groupSize:Int = size/maxThreads + 1 
val ranges: IndexedSeq[(Int, Int)] = (0 until maxThreads).map(i => (i * groupSize, (i + 1) * groupSize)) 
time { 
    //parallelizing sorting for each range 
    ranges.par.foreach {case (from, to) => 
    input.view(from, to).sortWith(_ < _) 
    } 
    //TODO merge the parts together 
} 

Malheureusement il y a this old bug qui nous empêche de faire quoi que ce soit amusant avec vue. Il ne semble pas y avoir de mécanisme intégré Scala (autre que des vues) pour trier juste une partie d'une collection. C'est pourquoi j'ai essayé de coder mon propre algorithme de tri de fusion avec la signature de def mergeSort(a: Array[Int], r: Range): Unit pour l'utiliser comme je l'ai décrit ci-dessus. Malheureusement, il semble être plus de 4 fois moins efficace que la méthode scala Array.sorted donc je ne pense pas qu'il pourrait être utilisé pour gagner en efficacité par rapport à l'approche séquentielle standard.Si je comprends bien votre situation, votre jeu de données tient dans la mémoire, donc utiliser quelque chose comme Hadoop et MapReduce serait prématuré. Ce que vous pourriez essayer serait Apache Spark - à part ajouter une dépendance, vous n'aurez pas besoin de configurer un cluster ou d'installer quoi que ce soit pour que Spark utilise tous les cœurs de votre machine dans une configuration de base. Ses RDD sont idéologiquement similaires aux collections parallèles de Scala, mais avec des fonctionnalités supplémentaires. Et ils (in a way) prennent en charge le tri parallèle.

Answer 2

Il n'existe aucun algorithme de tri parallèle disponible dans la bibliothèque standard Scala. Pour cette raison, la collection parallèle ne fournit pas les méthodes sorted, sortBy ou sortWith. Vous devrez convertir en une classe séquentielle appropriée (par exemple avec toArray) avant le tri.

Answer 3

Si vos données peuvent être stockées en mémoire, le tri simple dans le tri par mémoire est assez rapide. Si vous avez besoin de charger beaucoup de données à partir du disque ou de HDFS, alors vous pouvez faire le tri sur un système distribué comme hadoop ou spark.

Answer 4

Si vous construisez votre projet Scala contre Java 8, il y a le new Arrays.parallelSort vous pouvez utiliser:

def sort[T <: Comparable](parArray: ParArray[T])(implicit c: ClassTag[T]): ParArray[T] = { 
    var array = new Array[T](parArray.size) // Or, to prevent copying, var array = parArray.seq.array.asInstanceOf[Array[T]] might work? 
    parArray.copyToArray(array) 
    java.util.Arrays.parallelSort(array) 
    ParArray.createFromCopy(array) 
} 

Answer 5

def parallelSort[A : Ordering](seq: ParIterable[A]): TreeSet[A] = { 
    seq.aggregate[TreeSet[A]](TreeSet.empty[A])(
    (set, a) => set + a, 
    (set, set) => set ++ set) 
}