Tri rapide dans Scala vs java.util.Arrays.sort

Question

Voici une implémentation de tri rapide dans Scala. En comparant le temps d'exécution de quickSortRecursive à java.util.Arrays.sort(), j'ai trouvé java.util.Arrays.sort plus rapide d'un ordre de grandeur sur les grands tableaux. Quelqu'un peut-il faire allusion à la raison de cette différence de performance?

def quickSortRecursive(list: Array[Int])(low: Int=0, high: Int=list.length-1): Unit = { 
    if (low<high) { 
    swap(list,Random.nextInt(high),high) 
    val pivot = partition(list, low, high) 
    quickSortRecursive(list)(low, pivot-1) 
    quickSortRecursive(list)(pivot+1, high) 
    } 
} 

private def partition(list: Array[Int], low: Int, high: Int): Int = { 
    val pivot = list(high) 
    var lowhigh = low 
    for (i <- low until high) { 
    if (list(i) < pivot) { 
     swap(list, lowhigh, i); 
     lowhigh += 1; 
    } 
    } 
    swap(list, lowhigh, high); 
    lowhigh 
} 

private def swap(list: Array[Int], i: Int, j: Int): Unit = { 
    val tmp = list(i) 
    list(i) = list(j) 
    list(j) = tmp 
} 

Answer 1

Vous comapared une implémentation hautement optimisé d'un algorithme de tri générique (java.util.Arrays.sort) à une mise en œuvre sans optimisation Roulotté main (votre code Scala).

Ainsi, il est lié à être plus lent.

Quel résultat visez-vous? Pour une bonne comparaison, vous pouvez essayer de comparer les différents algorithmes de tri fournis par la bibliothèque standard Scala avec ceux fournis par la distribution standard Java. Ou vous pouvez implémenter votre Quicksort en Java et Scala et comparer les résultats.