Demande :
- La question est en deux parties. La première est conceptuelle, elle compare la programmation fonctionnelle et impérative du point de vue du cosy. impérative du point de vue du coût de l'immuabilité. La seconde, sur les spécificités de Java/scala.
- Quicksort est enseigné et généralement mis en œuvre comme un tri en mémoire. Il n'y a aucun doute là-dessus. Mais comment implémenter une telle chose d'une manière PUREment fonctionnelle ? Plus précisément en Scala ?
Question :
Je viens d'un milieu fortement impératif (C++, Java). J'ai exploré la programmation fonctionnelle, plus particulièrement Scala. Comme je suis novice en programmation fonctionnelle, j'ai pensé que ce serait une bonne idée de poser cette question ici maintenant.
Certains des concepts de la programmation fonctionnelle (je suis sûr que j'en oublie beaucoup) :
- Fonctionne comme des citoyens de première classe.
- Les fonctions n'ont pas d'effets secondaires et donc objets immuables .
- La concussion devient facile grâce à 2)
Même si la modernité JVMs sont extrêmement efficaces pour la création d'objets et collecte des déchets est très peu coûteux pour les objets de courte durée, il est probablement encore mieux de minimiser la création d'objets, non ? Au moins dans une application monofilaire où la concurrence et le verrouillage ne sont pas un problème. Comme Scala est un hybride, je sais que je peux écrire du code impératif avec des objets mutables si nécessaire. Mais, en tant que personne qui a passé beaucoup d'années à essayer de réutiliser des objets et de minimiser l'allocation. J'aimerais avoir une bonne compréhension de la contre école de pensée.
Dans un cas précis, j'ai été un peu surpris par ce bout de code dans le document ce tutoriel par Ted Neward (semble être un nom éminent dans la communauté Scala). Il propose une version Java de quicksort et donne ensuite une implémentation Scala soignée de la même chose.
Voici ma tentative d'évaluation comparative des implémentations. Je n'ai pas fait de profilage détaillé. Mais je pense que la version Scala est plus lente car le nombre d'objets alloués est linéaire (un par appel de récursion). Y a-t-il une chance que les optimisations des appels de queue puissent entrer en jeu ? Si j'ai raison, Scala supporte les optimisations de tail call pour les appels auto-récursifs. Donc, cela ne devrait que l'aider. J'utilise Scala 2.8.
Version Java
public class QuickSortJ {
public static void sort(int[] xs) {
sort(xs, 0, xs.length -1 );
}
static void sort(int[] xs, int l, int r) {
int pivot = xs[(l+r)/2];
int a = l; int b = r;
while (a <= b){
while (xs[a] < pivot) { a = a + 1; }
while (xs[b] > pivot) { b = b - 1; }
if (a <= b) {
swap(xs, a, b);
a = a + 1;
b = b - 1;
}
}
if (l < b) sort(xs, l, b);
if (b < r) sort(xs, a, r);
}
static void swap(int[] arr, int i, int j) {
int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
}Version du scanner
object QuickSortS {
def sort(xs: Array[Int]): Array[Int] =
if (xs.length <= 1) xs
else {
val pivot = xs(xs.length / 2)
Array.concat(
sort(xs filter (pivot >)),
xs filter (pivot ==),
sort(xs filter (pivot <)))
}
}Code Scala pour comparer les implémentations
import java.util.Date
import scala.testing.Benchmark
class BenchSort(sortfn: (Array[Int]) => Unit, name:String) extends Benchmark {
val ints = new Array[Int](100000);
override def prefix = name
override def setUp = {
val ran = new java.util.Random(5);
for (i <- 0 to ints.length - 1)
ints(i) = ran.nextInt();
}
override def run = sortfn(ints)
}
val benchImmut = new BenchSort( QuickSortS.sort , "Immutable/Functional/Scala" )
val benchMut = new BenchSort( QuickSortJ.sort , "Mutable/Imperative/Java " )
benchImmut.main( Array("5"))
benchMut.main( Array("5"))Résultats
Temps en millisecondes pour cinq passages consécutifs
Immutable/Functional/Scala 467 178 184 187 183
Mutable/Imperative/Java 51 14 12 12 12
