In Jawad-Boulahfa/RadixSort: Radix sort algorithm in R and Rcpp
Projet M2 Algorithmique
Jawad Boulahfa, Kylliann De Santiago, Romain Brulé
M2 Data Science: Santé, Assurance, Finance
Université d'Evry Val d'Essonne
9 janvier 2021
Introduction
Le package R RadixSort a été réalisé dans le cadre du projet d'algorithmique.
Le but de ce dernier est d'une part de coder l'algorithme de tri radix sort à la fois en R et en Rcpp afin de comparer les performances des deux méthodes et d'autre part de comparer les performances de cet algorithme avec d'autres algorithmes de tri.
Ce fichier récapitule les simulations effectuées au cours de ce projet et les conclusions qui en ont été tirées.
Installation du package
Avant de commencer, on nettoie l'environnement de travail.
rm(list = ls())
Il faut avoir préalablement installé le package devtools.
Ensuite, il suffit de retirer le symbole "#" et d'exécuter la ligne correspondante pour installer le package RadixSort.
On peut alors l'utiliser comme n'importe quel autre package R via la commande: library(RadixSort).
#devtools::install_github("Jawad-Boulahfa/RadixSort")
library(RadixSort)
On charge aussi le package M2algorithmique (qu'il faut également avoir préalablement installé) dont on aura besoin lorsque l'on utilisera le heap sort.
#devtools::install_github("vrunge/M2algorithmique")
library(M2algorithmique)
Premier essai
On effectue un premier essai en triant un vecteur de taille 10 issu d'un tirage aléatoire (avec remise) d'entiers compris entre 1 et 10.
n <- 10
#V <- floor(runif(n, min=0, max=n))
V <- sample.int(n, replace = TRUE)
Vecteur à trier.
V
Radix sort avec la fonction codée en R.
radix_sort(V)
Radix sort avec la fonction codée en Rcpp.
radix_sort_Rcpp(V)
Heap sort avec la fonction codée en R.
heap_sort(V)
Heap sort avec la fonction codée en Rcpp.
heap_sort_Rcpp(V)
Quick sort avec la fonction codée en R.
quick_sort_opti(V)
Quick sort avec la fonction codée en Rcpp.
quick_sort_Rcpp_opti(V)
Algorithmes de tri à n fixé
Le but de cette partie est de comparer les temps d'exécution de plusieurs algorithmes de tri à $n$ fixé.
Plus précisément, on va comparer les performances du radix sort avec le heap sort et le quick sort.
Une simulation
Tout d'abord, on définit une fonction qui nous permettra d'exécuter une simulation (i.e. un tri de vecteur) selon l'algorithme de tri choisi et la taille $n$ du vecteur fixée par l'utilisateur.
On introduit également un paramètre "type" qui permet de choisir la forme du vecteur à trier.
one.simu <- function(n, type = "integer", func = "radix_sort", precision = 5)
{
### Choix du type de vecteur à trier ###
# Tire n nombres entiers aléatoires compris entre 1 et n
if(type == "integer")
{
V <- sample.int(n, replace = TRUE) # Cas moyen: entiers aléatoires compris entre 1 et $n$.
}
# Tire n nombres entiers aléatoires compris entre -n et n (sauf 0)
if(type == "negative integer")
{
sign <- runif(n,min=0,max=1)
sign[sign >= 0.5] <- 1
sign[sign < 0.5] <- -1
V <- sample.int(n, replace = TRUE)*sign
}
# Tire n nombres décimaux aléatoires compris entre 0 et n
if(type == "decimal")
{
V <- round(runif(n, min=0, max = n), precision)
}
# Tire n nombres décimaux aléatoires compris entre -n et n
if(type == "negative decimal")
{
sign <- runif(n,min=0,max=1)
sign[sign>=0.5] <- 1
sign[sign<0.5] <- -1
V <- round(runif(n, min=0, max = n)*sign, precision)
}
# Construit un vecteur contenant tout les nombres entiers de n à 1 (ordre décroissant)
if(type == "reverse")
{
V <- n:1
}
### Choix de l'algorithme de tri ###
# Ici, on calcule le temps d'exécution de l'algorithme de tri choisi
if(func == "radix_sort"){t <- system.time(radix_sort(V))[[1]]}
if(func == "radix_sort_Rcpp"){t <- system.time(radix_sort_Rcpp(V))[[1]]}
if(func == "radix_sort_decimal"){t <- system.time(radix_sort_decimal(V))[[1]]}
if(func == "radix_sort_Rcpp_decimal"){t <- system.time(radix_sort_Rcpp_decimal(V))[[1]]}
if(func == "heap_sort"){t <- system.time(heap_sort(V))[[1]]}
if(func == "heap_sort_Rcpp"){t <- system.time(heap_sort_Rcpp(V))[[1]]}
if(func == "quick_sort_opti"){t <- system.time(quick_sort_opti(V))[[1]]}
if(func == "quick_sort_Rcpp_opti"){t <- system.time(quick_sort_Rcpp_opti(V))[[1]]}
return(t)
}
n <- 10^4
On fait une première simulation pour chacun des algorithmes avec $n = r n$ afin d'illustrer le fonctionnement de one.simu.
Par défaut, le vecteur a trier est issu d'un tirage aléatoire (avec remise) d'entiers compris entre 1 et $n$.
one.simu(n = n, func = "radix_sort")
one.simu(n = n, func = "radix_sort_Rcpp")
one.simu(n = n, func = "heap_sort")
one.simu(n = n, func = "heap_sort_Rcpp")
one.simu(n = n, func = "quick_sort_opti")
one.simu(n = n, func = "quick_sort_Rcpp_opti")
On conclut que les algorithmes les plus rapides sont le radix sort (version Rcpp) et le heap sort (version Rcpp) sur ce premier essai. Le plus lent est le heap sort (version R).
On peut également noter un gain de temps considérable entre le heap sort (version R) et le heap sort (version Rcpp). Dans tout les cas, le code en Rcpp est toujours plus rapide que le code en R.
Simulations avec des nombres entiers naturels
On commence par s'intéresser aux performances de chaque algorithme dans le cas où les valeurs du vecteurs à trier sont issus d'un tirage aléatoire (avec remise) d'entiers compris entre 1 et $n$.
# Valeur de n (taille du vecteur à trier)
n <- 10^4
# Nombre de fois où on répète l'algorithme sur un vecteur de taille n
nbSimus <- 10
# Temps d'exécutions
t1 <- 0
t2 <- 0
t3 <- 0
t4 <- 0
t5 <- 0
t6 <- 0
# Simulations
for(i in 1:nbSimus){t1 <- t1 + one.simu(n = n, type = "integer", func = "radix_sort")}
for(i in 1:nbSimus){t2 <- t2 + one.simu(n = n, type = "integer", func = "radix_sort_Rcpp")}
for(i in 1:nbSimus){t3 <- t3 + one.simu(n = n, type = "integer", func = "heap_sort")}
for(i in 1:nbSimus){t4 <- t4 + one.simu(n = n, type = "integer", func = "heap_sort_Rcpp")}
for(i in 1:nbSimus){t5 <- t5 + one.simu(n = n, type = "integer", func = "quick_sort_opti")}
for(i in 1:nbSimus){t6 <- t6 + one.simu(n = n, type = "integer", func = "quick_sort_Rcpp_opti")}
On affiche les temps d'exécution pour effectuer r nbSimus simulations.
t1 # temps d'exécution du radix sort en R
t2 # temps d'exécution du radix sort en Rcpp
t3 # temps d'exécution du heap sort en R
t4 # temps d'exécution du heap sort en Rcpp
t5 # temps d'exécution du quick sort en R
t6 # temps d'exécution du quick sort en Rcpp
On remarque que heap sort (version R) est à nouveau le plus lent de tous.
Cependant, l'algorithme le plus rapide est le radix sort (version Rcpp) suivi du heap sort (version Rcpp) alors que sur notre premier essai, ces deux algorithmes avaient la même performance.
Concernant le quick sort, ce dernier est assez lent comparé aux autres que ce soit en R ou en Rcpp (r t6 secondes pour la version Rcpp).
Ainsi, effectuer davantage de simulations nous a permis de mieux comparer les algorithmes.
Calcul du gain en passant de R à Rcpp.
t1/t2 # radix sort gain R -> Rcpp
t3/t4 # heap sort gain R -> Rcpp
t5/t6 # quick sort gain R -> Rcpp
Le code est Rcpp est toujours bien plus rapide que celui en R.
Par exemple, le radix sort en Rcpp est r t1/t2 fois plus rapide qu'en R.
Comparaison des temps d'exécution en R.
t1/t3 # comparaison radix sort en R et heap sort en R
t1/t5 # comparaison radix sort en R et quick sort en R
t3/t5 # comparaison heap sort en R et quick sort en R
En R, le radix sort est plus rapide que le heap sort et le quick sort.
Enfin, le quick sort est environ r round(t3/t5, 2) fois plus rapide que le heap sort.
Comparaison des temps d'exécution en Rcpp.
t2/t4 # comparaison radix sort en Rcpp et heap sort en Rcpp
t2/t6 # comparaison radix sort en Rcpp et quick sort en Rcpp
t4/t6 # comparaison heap sort en Rcpp et quick sort en Rcpp
En Rcpp, c'est clairement le radix sort qui permet les meilleurs gains de temps.
Simulations avec des nombres entiers relatifs
On s'intéresse ici aux performances de chaque algorithme dans le cas où les valeurs du vecteurs à trier sont issus d'un tirage aléatoire (avec remise) d'entiers compris entre $-n$ et $n$.
# Valeur de n (taille du vecteur à trier)
n <- 10^4
# Nombre de fois où on répète l'algorithme sur un vecteur de taille n
nbSimus <- 10
# Temps d'exécutions
t1 <- 0
t2 <- 0
t3 <- 0
t4 <- 0
t5 <- 0
t6 <- 0
# Simulations
for(i in 1:nbSimus){t1 <- t1 + one.simu(n = n, type = "negative integer",
func = "radix_sort")}
for(i in 1:nbSimus){t2 <- t2 + one.simu(n = n, type = "negative integer",
func = "radix_sort_Rcpp")}
for(i in 1:nbSimus){t3 <- t3 + one.simu(n = n, type = "negative integer",
func = "heap_sort")}
for(i in 1:nbSimus){t4 <- t4 + one.simu(n = n, type = "negative integer",
func = "heap_sort_Rcpp")}
for(i in 1:nbSimus){t5 <- t5 + one.simu(n = n, type = "negative integer",
func = "quick_sort_opti")}
for(i in 1:nbSimus){t6 <- t6 + one.simu(n = n, type = "negative integer",
func = "quick_sort_Rcpp_opti")}
On affiche les temps d'exécution pour effectuer r nbSimus simulations.
t1 # temps d'exécution du radix sort en R
t2 # temps d'exécution du radix sort en Rcpp
t3 # temps d'exécution du heap sort en R
t4 # temps d'exécution du heap sort en Rcpp
t5 # temps d'exécution du quick sort en R
t6 # temps d'exécution du quick sort en Rcpp
On peut noter ici la grande efficacité du heap sort (version Rcpp) sur ces données.
Le radix sort (version Rcpp) est également très performant.
Calcul du gain en passant de R à Rcpp.
t1/t2 # radix sort gain R -> Rcpp
t3/t4 # heap sort gain R -> Rcpp
t5/t6 # quick sort gain R -> Rcpp
Comparaison des temps d'exécution en R.
t1/t3 # comparaison radix sort en R et heap sort en R
t1/t5 # comparaison radix sort en R et quick sort en R
t3/t5 # comparaison heap sort en R et quick sort en R
En R, le radix sort est plus rapide que le heap sort et le quick sort.
Enfin, le quick sort est environ r round(t3/t5, 2) fois plus rapide que le heap sort.
Comparaison des temps d'exécution en Rcpp.
t2/t4 # comparaison radix sort en Rcpp et heap sort en Rcpp
t2/t6 # comparaison radix sort en Rcpp et quick sort en Rcpp
t4/t6 # comparaison heap sort en Rcpp et quick sort en Rcpp
En Rcpp, c'est clairement le heap sort qui permet les meilleurs gains de temps ici contrairement aux simulations précédentes (avec les entiers naturels).
Il est intéressant de noter qu'avec des entiers relatifs, le heap sort (version Rcpp) est meilleur que le radix sort (version Rcpp) et le radix sort et meilleur que le quick sort (pour les deux versions).
Simulations avec des nombres décimaux positifs
On commence par s'intéresser aux performances de chaque algorithme dans le cas où les valeurs du vecteurs à trier sont issus d'un tirage aléatoire de nombres décimaux positifs compris entre 0 et $n$ (avec une précision de $10^{-5}$).
# Valeur de n (taille du vecteur à trier)
n <- 10^4
# Nombre de fois où on répète l'algorithme sur un vecteur de taille n
nbSimus <- 10
# Temps d'exécutions
t1 <- 0
t2 <- 0
t3 <- 0
t4 <- 0
t5 <- 0
t6 <- 0
# Simulations
for(i in 1:nbSimus){t1 <- t1 + one.simu(n = n, type = "decimal", func = "radix_sort_decimal")}
for(i in 1:nbSimus){t2 <- t2 + one.simu(n = n, type = "decimal", func = "radix_sort_Rcpp_decimal")}
for(i in 1:nbSimus){t3 <- t3 + one.simu(n = n, type = "decimal", func = "heap_sort")}
for(i in 1:nbSimus){t4 <- t4 + one.simu(n = n, type = "decimal", func = "heap_sort_Rcpp")}
for(i in 1:nbSimus){t5 <- t5 + one.simu(n = n, type = "decimal", func = "quick_sort_opti")}
for(i in 1:nbSimus){t6 <- t6 + one.simu(n = n, type = "decimal", func = "quick_sort_Rcpp_opti")}
On affiche les temps d'exécution pour effectuer r nbSimus simulations.
t1 # temps d'exécution du radix sort en R
t2 # temps d'exécution du radix sort en Rcpp
t3 # temps d'exécution du heap sort en R
t4 # temps d'exécution du heap sort en Rcpp
t5 # temps d'exécution du quick sort en R
t6 # temps d'exécution du quick sort en Rcpp
Calcul du gain en passant de R à Rcpp.
t1/t2 # radix sort gain R -> Rcpp
t3/t4 # heap sort gain R -> Rcpp
t5/t6 # quick sort gain R -> Rcpp
Comparaison des temps d'exécution en R.
t1/t3 # comparaison radix sort en R et heap sort en R
t1/t5 # comparaison radix sort en R et quick sort en R
t3/t5 # comparaison heap sort en R et quick sort en R
Comparaison des temps d'exécution en Rcpp.
t2/t4 # comparaison radix sort en Rcpp et heap sort en Rcpp
t2/t6 # comparaison radix sort en Rcpp et quick sort en Rcpp
t4/t6 # comparaison heap sort en Rcpp et quick sort en Rcpp
Cette fois-ci, le radix sort est r t2/t4 fois plus lent que le heap sort.
Là encore, le heap sort (version Rcpp) affiche les meilleures performances.
Malgré notre adaptation du radix sort pour le tri des nombres décimaux, ce dernier, quelque soit la version considérée, reste plus lent que le heap sort (version Rcpp).
Cependant, le radix sort reste meilleur que le quick sort (pour les deux versions).
Simulations avec des nombres décimaux signés
On commence par s'intéresser aux performances de chaque algorithme dans le cas où les valeurs du vecteurs à trier sont issus d'un tirage aléatoire de nombres décimaux signés compris entre $-n$ et $n$ (avec une précision de $10^{-5}$).
# Valeur de n (taille du vecteur à trier)
n <- 10^4
# Nombre de fois où on répète l'algorithme sur un vecteur de taille n
nbSimus <- 10
# Temps d'exécutions
t1 <- 0
t2 <- 0
t3 <- 0
t4 <- 0
t5 <- 0
t6 <- 0
# Simulations
for(i in 1:nbSimus){t1 <- t1 + one.simu(n = n, type = "negative decimal",
func = "radix_sort_decimal")}
for(i in 1:nbSimus){t2 <- t2 + one.simu(n = n, type = "negative decimal",
func = "radix_sort_Rcpp_decimal")}
for(i in 1:nbSimus){t3 <- t3 + one.simu(n = n, type = "negative decimal",
func = "heap_sort")}
for(i in 1:nbSimus){t4 <- t4 + one.simu(n = n, type = "negative decimal",
func = "heap_sort_Rcpp")}
for(i in 1:nbSimus){t5 <- t5 + one.simu(n = n, type = "negative decimal",
func = "quick_sort_opti")}
for(i in 1:nbSimus){t6 <- t6 + one.simu(n = n, type = "negative decimal",
func = "quick_sort_Rcpp_opti")}
On affiche les temps d'exécution pour effectuer r nbSimus simulations.
t1 # temps d'exécution du radix sort en R
t2 # temps d'exécution du radix sort en Rcpp
t3 # temps d'exécution du heap sort en R
t4 # temps d'exécution du heap sort en Rcpp
t5 # temps d'exécution du quick sort en R
t6 # temps d'exécution du quick sort en Rcpp
Comparaison des temps d'exécution.
t1/t2 # radix sort gain R -> Rcpp
t3/t4 # heap sort gain R -> Rcpp
t5/t6 # quick sort gain R -> Rcpp
Lorqu'on utilise le radix sort codé en R au lieu de celui codé en Rcpp, on multiplie par environ r round(t1/t2, 2) le temps d'exécution.
Lorqu'on utilise le heap sort codé en R au lieu de celui codé en Rcpp, on multiplie par environ r round(t3/t4, 2) le temps d'exécution.
Lorqu'on utilise le quick sort codé en R au lieu de celui codé en Rcpp, on multiplie par environ r round(t5/t2, 2) le temps d'exécution.
Ainsi, le code est Rcpp est toujours bien plus rapide que celui en R.
t1/t3 # comparaison radix sort en R et heap sort en R
t1/t5 # comparaison radix sort en R et quick sort en R
t3/t5 # comparaison heap sort en R et quick sort en R
t2/t4 # comparaison radix sort en Rcpp et heap sort en Rcpp
t2/t6 # comparaison radix sort en Rcpp et quick sort en Rcpp
t4/t6 # comparaison heap sort en Rcpp et quick sort en Rcpp
Les constatations sont ici globalement les mêmes que dans les simulations précédentes.
Cependant, on peut noter ici que le heap sort (version Rcpp) est encore plus efficace qu'habituellement ici.
Simulations dans le cas où le vecteur est trié dans l'ordre décroissant
On s'intéresse ici aux performances de chaque algorithme dans le cas où les valeurs du vecteurs à trier sont rangées dans l'ordre décroissant.
# Valeur de n (taille du vecteur à trier)
n <- 10^4
# Nombre de fois où on répète l'algorithme sur un vecteur de taille n
nbSimus <- 10
# Temps d'exécutions
t1 <- 0
t2 <- 0
t3 <- 0
t4 <- 0
t5 <- 0
t6 <- 0
# Simulations
for(i in 1:nbSimus){t1 <- t1 + one.simu(n = n, type = "reverse", func = "radix_sort")}
for(i in 1:nbSimus){t2 <- t2 + one.simu(n = n, type = "reverse", func = "radix_sort_Rcpp")}
for(i in 1:nbSimus){t3 <- t3 + one.simu(n = n, type = "reverse", func = "heap_sort")}
for(i in 1:nbSimus){t4 <- t4 + one.simu(n = n, type = "reverse", func = "heap_sort_Rcpp")}
for(i in 1:nbSimus){t5 <- t5 + one.simu(n = n, type = "reverse", func = "quick_sort_opti")}
for(i in 1:nbSimus){t6 <- t6 + one.simu(n = n, type = "reverse", func = "quick_sort_Rcpp_opti")}
On affiche les temps d'exécution pour effectuer r nbSimus simulations.
t1 # temps d'exécution du radix sort en R
t2 # temps d'exécution du radix sort en Rcpp
t3 # temps d'exécution du heap sort en R
t4 # temps d'exécution du heap sort en Rcpp
t5 # temps d'exécution du quick sort en R
t6 # temps d'exécution du quick sort en Rcpp
Comparaison des temps d'exécution.
t1/t2 # radix sort gain R -> Rcpp
t3/t4 # heap sort gain R -> Rcpp
t5/t6 # quick sort gain R -> Rcpp
t1/t3 # comparaison radix sort en R et heap sort en R
t1/t5 # comparaison radix sort en R et quick sort en R
t3/t5 # comparaison heap sort en R et quick sort en R
t2/t4 # comparaison radix sort en Rcpp et heap sort en Rcpp
t2/t6 # comparaison radix sort en Rcpp et quick sort en Rcpp
t4/t6 # comparaison heap sort en Rcpp et quick sort en Rcpp
Ici, le radix sort (version Rcpp) et le heap sort (version Rcpp) affichent les mêmes performances.
Toutes ces simulations nous ont données un aperçu des performances de nos algorithmes dans différents contextes. Si on compare uniquement les versions Rcpp de nos trois algorithmes de tri, on constate après ces simulations que le quick sort semble être le plus lent des trois.
Microbenchmark
Le but de cette partie est d'effectuer des simulations plus approfondies sur nos trois algorithmes de tri afin de mieux les comparer.
Pour cela, nous allons utiliser les packages microbenchmark et ggplot2.
library(microbenchmark)
library(ggplot2)
Comparaisons avec des entiers naturels
On commence par comparer les 3 algorithmes en même temps.
Sur cet exemple, avec un vecteur de taille $10^4$, on remarque que le radix sort en R est le moins bon des 3.
Le radix sort en Rcpp semble meilleur que le heap sort en Rcpp, mais pour confirmer cela, nous allons faire un second essai avec une plus grande taille de vecteur.
Concernant les versions R, le radix sort est clairement le meilleur des trois.
n <- 10^4
res <- microbenchmark(one.simu(n = n, type = "integer", func = "radix_sort"),
one.simu(n = n, type = "integer", func = "radix_sort_Rcpp"),
one.simu(n = n, type = "integer", func = "heap_sort"),
one.simu(n = n, type = "integer", func = "heap_sort_Rcpp"),
one.simu(n = n, type = "integer", func = "quick_sort_opti"),
one.simu(n = n, type = "integer", func = "quick_sort_Rcpp_opti"),
times = 50)
autoplot(res)
print(res)
On fait maintenant un second essai avec une plus grande taille pour le vecteur à trier ($n = 10^6$ ici) et uniquement les versions Rcpp. On remarque le radix sort est généralement meilleur que le heap sort et que le quick sort est le plus lent des trois. Ceci est cohérent avec les résultats précédents (partie Simulations avec des nombres entiers naturels).
n <- 10^6
res <- microbenchmark(one.simu(n = n, type = "integer", func = "radix_sort_Rcpp"),
one.simu(n = n, type = "integer", func = "heap_sort_Rcpp"),
one.simu(n = n, type = "integer", func = "quick_sort_Rcpp_opti"),
times = 50)
autoplot(res)
print(res)
Comparaisons avec des entiers relatifs
Les constatations sont identiques à celles des comparaisons précédentes (avec des nombres entiers naturels). On peut cependant noter que le tri s'effectue généralement plus lentement ici.
n <- 10^4
res <- microbenchmark(one.simu(n = n, type = "negative integer", func = "radix_sort"),
one.simu(n = n, type = "negative integer", func = "radix_sort_Rcpp"),
one.simu(n = n, type = "negative integer", func = "heap_sort"),
one.simu(n = n, type = "negative integer", func = "heap_sort_Rcpp"),
one.simu(n = n, type = "negative integer", func = "quick_sort_opti"),
one.simu(n = n, type = "negative integer", func = "quick_sort_Rcpp_opti"),
times = 50)
autoplot(res)
print(res)
Contrairement aux comparaisons précédentes (avec des nombres entiers naturels), ici le temps de tri maximal du radix sort est inférieur à celui du heap sort pour effectuer ce tri.
Hormis cela, les constatations sont les mêmes que précédemment.
n <- 10^6
res <- microbenchmark(one.simu(n = n, type = "negative integer", func = "radix_sort_Rcpp"),
one.simu(n = n, type = "negative integer", func = "heap_sort_Rcpp"),
one.simu(n = n, type = "negative integer", func = "quick_sort_Rcpp_opti"),
times = 50)
autoplot(res)
print(res)
Comparaisons avec des nombres décimaux non signés
Sur ce premier essai, le heap sort (version Rcpp) semble être meilleur que le radix (version Rcpp).
n <- 10^4
res <- microbenchmark(one.simu(n = n, type = "decimal", func = "radix_sort_decimal"),
one.simu(n = n, type = "decimal", func = "radix_sort_Rcpp_decimal"),
one.simu(n = n, type = "decimal", func = "heap_sort"),
one.simu(n = n, type = "decimal", func = "heap_sort_Rcpp"),
one.simu(n = n, type = "decimal", func = "quick_sort_opti"),
one.simu(n = n, type = "decimal", func = "quick_sort_Rcpp_opti"),
times = 50)
autoplot(res)
print(res)
En augmentant la taille des vecteurs à trier, la différence est bien plus flagrante: le heap sort est clairement le meilleur des trois.
n <- 10^6
res <- microbenchmark(one.simu(n = n, type = "decimal", func = "radix_sort_Rcpp_decimal"),
one.simu(n = n, type = "decimal", func = "heap_sort_Rcpp"),
one.simu(n = n, type = "decimal", func = "quick_sort_Rcpp_opti"),
times = 50)
autoplot(res)
print(res)
Comparaisons avec des nombres décimaux signés
n <- 10^4
res <- microbenchmark(one.simu(n = n, type = "negative decimal", func = "radix_sort_decimal"),
one.simu(n = n, type = "negative decimal", func = "radix_sort_Rcpp_decimal"),
one.simu(n = n, type = "negative decimal", func = "heap_sort"),
one.simu(n = n, type = "negative decimal", func = "heap_sort_Rcpp"),
one.simu(n = n, type = "negative decimal", func = "quick_sort_opti"),
one.simu(n = n, type = "negative decimal", func = "quick_sort_Rcpp_opti"),
times = 50)
autoplot(res)
print(res)
n <- 10^6
res <- microbenchmark(one.simu(n = n, type = "negative decimal", func = "radix_sort_Rcpp_decimal"),
one.simu(n = n, type = "negative decimal", func = "heap_sort_Rcpp"),
one.simu(n = n, type = "negative decimal", func = "quick_sort_Rcpp_opti"),
times = 50)
autoplot(res)
print(res)
Les constatations sont les mêmes que dans les comparaisons précédentes (avec des nombres décimaux positifs).
Comparaison dans le cas où le vecteur est trié dans l'ordre décroissant
Sur ce premier essai, c'est le radix sort (version Rcpp) qui semble être le meilleur suivi du heap sort (version Rcpp)
n <- 10^4
res <- microbenchmark(one.simu(n = n, type = "reverse", func = "radix_sort"),
one.simu(n = n, type = "reverse", func = "radix_sort_Rcpp"),
one.simu(n = n, type = "reverse", func = "heap_sort"),
one.simu(n = n, type = "reverse", func = "heap_sort_Rcpp"),
one.simu(n = n, type = "reverse", func = "quick_sort_opti"),
one.simu(n = n, type = "reverse", func = "quick_sort_Rcpp_opti"),
times = 50)
autoplot(res)
print(res)
Cependant, lorsqu'on augmente la taille des vecteurs à trier, on remarque c'est le heap sort qui reprend l'avantage et qui devient le meilleur des trois.
n <- 10^6
res <- microbenchmark(one.simu(n = n, type = "reverse", func = "radix_sort_Rcpp"),
one.simu(n = n, type = "reverse", func = "heap_sort_Rcpp"),
one.simu(n = n, type = "reverse", func = "quick_sort_Rcpp_opti"),
times = 50)
autoplot(res)
print(res)
Complexité
Le but de cette partie est d'évaluer la complexité du radix sort, du heap sort et du quick sort.
On évaluera cette complexité en utilisant des vecteurs de nombres entiers naturels.
Radix sort en R
On lance $nbRep = 100$ fois l'algorithme radix sort pour chaque valeur du vecteur vector_n de taille $nbSimus = 20$. On affiche le graphe du temps d'exécution moyen en fonction de la taille des données.
nbSimus <- 20
vector_n <- seq(from = 5000, to = 50000, length.out = nbSimus)
nbRep <- 100
res_radix <- data.frame(matrix(0, nbSimus, nbRep + 1))
colnames(res_radix) <- c("n", paste0("Rep",1:nbRep))
j <- 1
for(i in vector_n)
{
res_radix[j,] <- c(i, replicate(nbRep, one.simu(i, func = "radix_sort")))
#print(j)
j <- j + 1
}
res <- rowMeans(res_radix[,-1])
plot(vector_n, res, type = 'b', xlab = "data length", ylab = "mean time in seconds")
lm(log(res) ~ log(vector_n))
Radix sort en Rcpp
En Rcpp, on constate qu'on gagne énormément de temps par rapport au code R.
Cependant, on n'a plus du tout la tendance "linéaire" de la courbe.
nbSimus <- 20
vector_n <- seq(from = 5000, to = 50000, length.out = nbSimus)
nbRep <- 100
res_radix_rcpp <- data.frame(matrix(0, nbSimus, nbRep + 1))
colnames(res_radix_rcpp) <- c("n", paste0("Rep",1:nbRep))
j <- 1
for(i in vector_n)
{
res_radix_rcpp[j,] <- c(i, replicate(nbRep, one.simu(i, func = "radix_sort_Rcpp")))
#print(j)
j <- j + 1
}
res <- rowMeans(res_radix_rcpp[,-1])
plot(vector_n, res, type = 'b', xlab = "data length", ylab = "mean time in seconds")
lm(log(res) ~ log(vector_n))
Radix sort en R (version nombres décimaux)
On remarque que l'algorithme est bien plus lent ici comparé à la version optimisée pour les entiers naturels et relatifs.
Cela s'explique par le fait que celui-ci a été optimisé pour le tri des nombres décimaux.
nbSimus <- 20
vector_n <- seq(from = 5000, to = 50000, length.out = nbSimus)
nbRep <- 100
res_radix_rcpp <- data.frame(matrix(0, nbSimus, nbRep + 1))
colnames(res_radix_rcpp) <- c("n", paste0("Rep",1:nbRep))
j <- 1
for(i in vector_n)
{
res_radix_rcpp[j,] <- c(i, replicate(nbRep, one.simu(i, func = "radix_sort_decimal")))
#print(j)
j <- j + 1
}
res <- rowMeans(res_radix_rcpp[,-1])
plot(vector_n, res, type = 'b', xlab = "data length", ylab = "mean time in seconds")
lm(log(res) ~ log(vector_n))
Radix sort en Rcpp (version nombres décimaux)
En Rcpp, on constate à nouveau qu'on gagne énormément de temps par rapport au code R.
Cependant, on n'a plus du tout la tendance "linéaire" de la courbe.
nbSimus <- 20
vector_n <- seq(from = 5000, to = 50000, length.out = nbSimus)
nbRep <- 100
res_radix_rcpp <- data.frame(matrix(0, nbSimus, nbRep + 1))
colnames(res_radix_rcpp) <- c("n", paste0("Rep",1:nbRep))
j <- 1
for(i in vector_n)
{
res_radix_rcpp[j,] <- c(i, replicate(nbRep, one.simu(i, func = "radix_sort_Rcpp_decimal")))
#print(j)
j <- j + 1
}
res <- rowMeans(res_radix_rcpp[,-1])
plot(vector_n, res, type = 'b', xlab = "data length", ylab = "mean time in seconds")
lm(log(res) ~ log(vector_n))
Heap sort en Rcpp
Le heap sort est généralement plus lent que le radix sort ici, ce qui est cohérent avec les constatations des parties précédentes.
nbSimus <- 20
vector_n <- seq(from = 5000, to = 50000, length.out = nbSimus)
nbRep <- 100
res_heap_sort_rcpp <- data.frame(matrix(0, nbSimus, nbRep + 1))
colnames(res_heap_sort_rcpp) <- c("n", paste0("Rep",1:nbRep))
j <- 1
for(i in vector_n)
{
res_heap_sort_rcpp[j,] <- c(i, replicate(nbRep, one.simu(i, func = "heap_sort_Rcpp")))
#print(j)
j <- j + 1
}
res <- rowMeans(res_heap_sort_rcpp[,-1])
plot(vector_n, res, type = 'b', xlab = "data length", ylab = "mean time in seconds")
lm(log(res) ~ log(vector_n))
Quick sort en Rcpp
Le quick sort est généralement le plus lent des trois ici, ce qui est cohérent avec les constatations des parties précédentes.
nbSimus <- 20
vector_n <- seq(from = 5000, to = 50000, length.out = nbSimus)
nbRep <- 100
res_quick_sort_rcpp <- data.frame(matrix(0, nbSimus, nbRep + 1))
colnames(res_quick_sort_rcpp) <- c("n", paste0("Rep",1:nbRep))
j <- 1
for(i in vector_n)
{
res_quick_sort_rcpp[j,] <- c(i, replicate(nbRep, one.simu(i, func = "quick_sort_Rcpp_opti")))
#print(j)
j <- j + 1
}
res <- rowMeans(res_quick_sort_rcpp[,-1])
plot(vector_n, res, type = 'b', xlab = "data length", ylab = "mean time in seconds")
lm(log(res) ~ log(vector_n))
Jawad-Boulahfa/RadixSort documentation built on Jan. 28, 2021, 11:44 a.m.
R Package Documentation
Browse R Packages
We want your feedback!
Note that we can't provide technical support on individual packages. You should contact the package authors for that.
Projet M2 Algorithmique
Jawad Boulahfa, Kylliann De Santiago, Romain Brulé
M2 Data Science: Santé, Assurance, Finance
Université d'Evry Val d'Essonne
9 janvier 2021
Introduction
Le package R RadixSort a été réalisé dans le cadre du projet d'algorithmique.
Le but de ce dernier est d'une part de coder l'algorithme de tri radix sort à la fois en R et en Rcpp afin de comparer les performances des deux méthodes et d'autre part de comparer les performances de cet algorithme avec d'autres algorithmes de tri.
Ce fichier récapitule les simulations effectuées au cours de ce projet et les conclusions qui en ont été tirées.
Installation du package
Avant de commencer, on nettoie l'environnement de travail.
rm(list = ls())
Il faut avoir préalablement installé le package devtools.
Ensuite, il suffit de retirer le symbole "#" et d'exécuter la ligne correspondante pour installer le package RadixSort.
On peut alors l'utiliser comme n'importe quel autre package R via la commande: library(RadixSort).
#devtools::install_github("Jawad-Boulahfa/RadixSort") library(RadixSort)
On charge aussi le package M2algorithmique (qu'il faut également avoir préalablement installé) dont on aura besoin lorsque l'on utilisera le heap sort.
#devtools::install_github("vrunge/M2algorithmique") library(M2algorithmique)
Premier essai
On effectue un premier essai en triant un vecteur de taille 10 issu d'un tirage aléatoire (avec remise) d'entiers compris entre 1 et 10.
n <- 10 #V <- floor(runif(n, min=0, max=n)) V <- sample.int(n, replace = TRUE)
Vecteur à trier.
V
Radix sort avec la fonction codée en R.
radix_sort(V)
Radix sort avec la fonction codée en Rcpp.
radix_sort_Rcpp(V)
Heap sort avec la fonction codée en R.
heap_sort(V)
Heap sort avec la fonction codée en Rcpp.
heap_sort_Rcpp(V)
Quick sort avec la fonction codée en R.
quick_sort_opti(V)
Quick sort avec la fonction codée en Rcpp.
quick_sort_Rcpp_opti(V)
Algorithmes de tri à n fixé
Le but de cette partie est de comparer les temps d'exécution de plusieurs algorithmes de tri à $n$ fixé. Plus précisément, on va comparer les performances du radix sort avec le heap sort et le quick sort.
Une simulation
Tout d'abord, on définit une fonction qui nous permettra d'exécuter une simulation (i.e. un tri de vecteur) selon l'algorithme de tri choisi et la taille $n$ du vecteur fixée par l'utilisateur. On introduit également un paramètre "type" qui permet de choisir la forme du vecteur à trier.
one.simu <- function(n, type = "integer", func = "radix_sort", precision = 5) { ### Choix du type de vecteur à trier ### # Tire n nombres entiers aléatoires compris entre 1 et n if(type == "integer") { V <- sample.int(n, replace = TRUE) # Cas moyen: entiers aléatoires compris entre 1 et $n$. } # Tire n nombres entiers aléatoires compris entre -n et n (sauf 0) if(type == "negative integer") { sign <- runif(n,min=0,max=1) sign[sign >= 0.5] <- 1 sign[sign < 0.5] <- -1 V <- sample.int(n, replace = TRUE)*sign } # Tire n nombres décimaux aléatoires compris entre 0 et n if(type == "decimal") { V <- round(runif(n, min=0, max = n), precision) } # Tire n nombres décimaux aléatoires compris entre -n et n if(type == "negative decimal") { sign <- runif(n,min=0,max=1) sign[sign>=0.5] <- 1 sign[sign<0.5] <- -1 V <- round(runif(n, min=0, max = n)*sign, precision) } # Construit un vecteur contenant tout les nombres entiers de n à 1 (ordre décroissant) if(type == "reverse") { V <- n:1 } ### Choix de l'algorithme de tri ### # Ici, on calcule le temps d'exécution de l'algorithme de tri choisi if(func == "radix_sort"){t <- system.time(radix_sort(V))[[1]]} if(func == "radix_sort_Rcpp"){t <- system.time(radix_sort_Rcpp(V))[[1]]} if(func == "radix_sort_decimal"){t <- system.time(radix_sort_decimal(V))[[1]]} if(func == "radix_sort_Rcpp_decimal"){t <- system.time(radix_sort_Rcpp_decimal(V))[[1]]} if(func == "heap_sort"){t <- system.time(heap_sort(V))[[1]]} if(func == "heap_sort_Rcpp"){t <- system.time(heap_sort_Rcpp(V))[[1]]} if(func == "quick_sort_opti"){t <- system.time(quick_sort_opti(V))[[1]]} if(func == "quick_sort_Rcpp_opti"){t <- system.time(quick_sort_Rcpp_opti(V))[[1]]} return(t) }
n <- 10^4
On fait une première simulation pour chacun des algorithmes avec $n = r n$ afin d'illustrer le fonctionnement de one.simu.
Par défaut, le vecteur a trier est issu d'un tirage aléatoire (avec remise) d'entiers compris entre 1 et $n$.
one.simu(n = n, func = "radix_sort")
one.simu(n = n, func = "radix_sort_Rcpp")
one.simu(n = n, func = "heap_sort")
one.simu(n = n, func = "heap_sort_Rcpp")
one.simu(n = n, func = "quick_sort_opti")
one.simu(n = n, func = "quick_sort_Rcpp_opti")
On conclut que les algorithmes les plus rapides sont le radix sort (version Rcpp) et le heap sort (version Rcpp) sur ce premier essai. Le plus lent est le heap sort (version R). On peut également noter un gain de temps considérable entre le heap sort (version R) et le heap sort (version Rcpp). Dans tout les cas, le code en Rcpp est toujours plus rapide que le code en R.
Simulations avec des nombres entiers naturels
On commence par s'intéresser aux performances de chaque algorithme dans le cas où les valeurs du vecteurs à trier sont issus d'un tirage aléatoire (avec remise) d'entiers compris entre 1 et $n$.
# Valeur de n (taille du vecteur à trier) n <- 10^4 # Nombre de fois où on répète l'algorithme sur un vecteur de taille n nbSimus <- 10 # Temps d'exécutions t1 <- 0 t2 <- 0 t3 <- 0 t4 <- 0 t5 <- 0 t6 <- 0 # Simulations for(i in 1:nbSimus){t1 <- t1 + one.simu(n = n, type = "integer", func = "radix_sort")} for(i in 1:nbSimus){t2 <- t2 + one.simu(n = n, type = "integer", func = "radix_sort_Rcpp")} for(i in 1:nbSimus){t3 <- t3 + one.simu(n = n, type = "integer", func = "heap_sort")} for(i in 1:nbSimus){t4 <- t4 + one.simu(n = n, type = "integer", func = "heap_sort_Rcpp")} for(i in 1:nbSimus){t5 <- t5 + one.simu(n = n, type = "integer", func = "quick_sort_opti")} for(i in 1:nbSimus){t6 <- t6 + one.simu(n = n, type = "integer", func = "quick_sort_Rcpp_opti")}
On affiche les temps d'exécution pour effectuer r nbSimus simulations.
t1 # temps d'exécution du radix sort en R t2 # temps d'exécution du radix sort en Rcpp t3 # temps d'exécution du heap sort en R t4 # temps d'exécution du heap sort en Rcpp t5 # temps d'exécution du quick sort en R t6 # temps d'exécution du quick sort en Rcpp
On remarque que heap sort (version R) est à nouveau le plus lent de tous.
Cependant, l'algorithme le plus rapide est le radix sort (version Rcpp) suivi du heap sort (version Rcpp) alors que sur notre premier essai, ces deux algorithmes avaient la même performance.
Concernant le quick sort, ce dernier est assez lent comparé aux autres que ce soit en R ou en Rcpp (r t6 secondes pour la version Rcpp).
Ainsi, effectuer davantage de simulations nous a permis de mieux comparer les algorithmes.
Calcul du gain en passant de R à Rcpp.
t1/t2 # radix sort gain R -> Rcpp t3/t4 # heap sort gain R -> Rcpp t5/t6 # quick sort gain R -> Rcpp
Le code est Rcpp est toujours bien plus rapide que celui en R.
Par exemple, le radix sort en Rcpp est r t1/t2 fois plus rapide qu'en R.
Comparaison des temps d'exécution en R.
t1/t3 # comparaison radix sort en R et heap sort en R t1/t5 # comparaison radix sort en R et quick sort en R t3/t5 # comparaison heap sort en R et quick sort en R
En R, le radix sort est plus rapide que le heap sort et le quick sort.
Enfin, le quick sort est environ r round(t3/t5, 2) fois plus rapide que le heap sort.
Comparaison des temps d'exécution en Rcpp.
t2/t4 # comparaison radix sort en Rcpp et heap sort en Rcpp t2/t6 # comparaison radix sort en Rcpp et quick sort en Rcpp t4/t6 # comparaison heap sort en Rcpp et quick sort en Rcpp
En Rcpp, c'est clairement le radix sort qui permet les meilleurs gains de temps.
Simulations avec des nombres entiers relatifs
On s'intéresse ici aux performances de chaque algorithme dans le cas où les valeurs du vecteurs à trier sont issus d'un tirage aléatoire (avec remise) d'entiers compris entre $-n$ et $n$.
# Valeur de n (taille du vecteur à trier) n <- 10^4 # Nombre de fois où on répète l'algorithme sur un vecteur de taille n nbSimus <- 10 # Temps d'exécutions t1 <- 0 t2 <- 0 t3 <- 0 t4 <- 0 t5 <- 0 t6 <- 0 # Simulations for(i in 1:nbSimus){t1 <- t1 + one.simu(n = n, type = "negative integer", func = "radix_sort")} for(i in 1:nbSimus){t2 <- t2 + one.simu(n = n, type = "negative integer", func = "radix_sort_Rcpp")} for(i in 1:nbSimus){t3 <- t3 + one.simu(n = n, type = "negative integer", func = "heap_sort")} for(i in 1:nbSimus){t4 <- t4 + one.simu(n = n, type = "negative integer", func = "heap_sort_Rcpp")} for(i in 1:nbSimus){t5 <- t5 + one.simu(n = n, type = "negative integer", func = "quick_sort_opti")} for(i in 1:nbSimus){t6 <- t6 + one.simu(n = n, type = "negative integer", func = "quick_sort_Rcpp_opti")}
On affiche les temps d'exécution pour effectuer r nbSimus simulations.
t1 # temps d'exécution du radix sort en R t2 # temps d'exécution du radix sort en Rcpp t3 # temps d'exécution du heap sort en R t4 # temps d'exécution du heap sort en Rcpp t5 # temps d'exécution du quick sort en R t6 # temps d'exécution du quick sort en Rcpp
On peut noter ici la grande efficacité du heap sort (version Rcpp) sur ces données. Le radix sort (version Rcpp) est également très performant.
Calcul du gain en passant de R à Rcpp.
t1/t2 # radix sort gain R -> Rcpp t3/t4 # heap sort gain R -> Rcpp t5/t6 # quick sort gain R -> Rcpp
Comparaison des temps d'exécution en R.
t1/t3 # comparaison radix sort en R et heap sort en R t1/t5 # comparaison radix sort en R et quick sort en R t3/t5 # comparaison heap sort en R et quick sort en R
En R, le radix sort est plus rapide que le heap sort et le quick sort.
Enfin, le quick sort est environ r round(t3/t5, 2) fois plus rapide que le heap sort.
Comparaison des temps d'exécution en Rcpp.
t2/t4 # comparaison radix sort en Rcpp et heap sort en Rcpp t2/t6 # comparaison radix sort en Rcpp et quick sort en Rcpp t4/t6 # comparaison heap sort en Rcpp et quick sort en Rcpp
En Rcpp, c'est clairement le heap sort qui permet les meilleurs gains de temps ici contrairement aux simulations précédentes (avec les entiers naturels).
Il est intéressant de noter qu'avec des entiers relatifs, le heap sort (version Rcpp) est meilleur que le radix sort (version Rcpp) et le radix sort et meilleur que le quick sort (pour les deux versions).
Simulations avec des nombres décimaux positifs
On commence par s'intéresser aux performances de chaque algorithme dans le cas où les valeurs du vecteurs à trier sont issus d'un tirage aléatoire de nombres décimaux positifs compris entre 0 et $n$ (avec une précision de $10^{-5}$).
# Valeur de n (taille du vecteur à trier) n <- 10^4 # Nombre de fois où on répète l'algorithme sur un vecteur de taille n nbSimus <- 10 # Temps d'exécutions t1 <- 0 t2 <- 0 t3 <- 0 t4 <- 0 t5 <- 0 t6 <- 0 # Simulations for(i in 1:nbSimus){t1 <- t1 + one.simu(n = n, type = "decimal", func = "radix_sort_decimal")} for(i in 1:nbSimus){t2 <- t2 + one.simu(n = n, type = "decimal", func = "radix_sort_Rcpp_decimal")} for(i in 1:nbSimus){t3 <- t3 + one.simu(n = n, type = "decimal", func = "heap_sort")} for(i in 1:nbSimus){t4 <- t4 + one.simu(n = n, type = "decimal", func = "heap_sort_Rcpp")} for(i in 1:nbSimus){t5 <- t5 + one.simu(n = n, type = "decimal", func = "quick_sort_opti")} for(i in 1:nbSimus){t6 <- t6 + one.simu(n = n, type = "decimal", func = "quick_sort_Rcpp_opti")}
On affiche les temps d'exécution pour effectuer r nbSimus simulations.
t1 # temps d'exécution du radix sort en R t2 # temps d'exécution du radix sort en Rcpp t3 # temps d'exécution du heap sort en R t4 # temps d'exécution du heap sort en Rcpp t5 # temps d'exécution du quick sort en R t6 # temps d'exécution du quick sort en Rcpp
Calcul du gain en passant de R à Rcpp.
t1/t2 # radix sort gain R -> Rcpp t3/t4 # heap sort gain R -> Rcpp t5/t6 # quick sort gain R -> Rcpp
Comparaison des temps d'exécution en R.
t1/t3 # comparaison radix sort en R et heap sort en R t1/t5 # comparaison radix sort en R et quick sort en R t3/t5 # comparaison heap sort en R et quick sort en R
Comparaison des temps d'exécution en Rcpp.
t2/t4 # comparaison radix sort en Rcpp et heap sort en Rcpp t2/t6 # comparaison radix sort en Rcpp et quick sort en Rcpp t4/t6 # comparaison heap sort en Rcpp et quick sort en Rcpp
Cette fois-ci, le radix sort est r t2/t4 fois plus lent que le heap sort.
Là encore, le heap sort (version Rcpp) affiche les meilleures performances. Malgré notre adaptation du radix sort pour le tri des nombres décimaux, ce dernier, quelque soit la version considérée, reste plus lent que le heap sort (version Rcpp). Cependant, le radix sort reste meilleur que le quick sort (pour les deux versions).
Simulations avec des nombres décimaux signés
On commence par s'intéresser aux performances de chaque algorithme dans le cas où les valeurs du vecteurs à trier sont issus d'un tirage aléatoire de nombres décimaux signés compris entre $-n$ et $n$ (avec une précision de $10^{-5}$).
# Valeur de n (taille du vecteur à trier) n <- 10^4 # Nombre de fois où on répète l'algorithme sur un vecteur de taille n nbSimus <- 10 # Temps d'exécutions t1 <- 0 t2 <- 0 t3 <- 0 t4 <- 0 t5 <- 0 t6 <- 0 # Simulations for(i in 1:nbSimus){t1 <- t1 + one.simu(n = n, type = "negative decimal", func = "radix_sort_decimal")} for(i in 1:nbSimus){t2 <- t2 + one.simu(n = n, type = "negative decimal", func = "radix_sort_Rcpp_decimal")} for(i in 1:nbSimus){t3 <- t3 + one.simu(n = n, type = "negative decimal", func = "heap_sort")} for(i in 1:nbSimus){t4 <- t4 + one.simu(n = n, type = "negative decimal", func = "heap_sort_Rcpp")} for(i in 1:nbSimus){t5 <- t5 + one.simu(n = n, type = "negative decimal", func = "quick_sort_opti")} for(i in 1:nbSimus){t6 <- t6 + one.simu(n = n, type = "negative decimal", func = "quick_sort_Rcpp_opti")}
On affiche les temps d'exécution pour effectuer r nbSimus simulations.
t1 # temps d'exécution du radix sort en R t2 # temps d'exécution du radix sort en Rcpp t3 # temps d'exécution du heap sort en R t4 # temps d'exécution du heap sort en Rcpp t5 # temps d'exécution du quick sort en R t6 # temps d'exécution du quick sort en Rcpp
Comparaison des temps d'exécution.
t1/t2 # radix sort gain R -> Rcpp t3/t4 # heap sort gain R -> Rcpp t5/t6 # quick sort gain R -> Rcpp
Lorqu'on utilise le radix sort codé en R au lieu de celui codé en Rcpp, on multiplie par environ r round(t1/t2, 2) le temps d'exécution.
Lorqu'on utilise le heap sort codé en R au lieu de celui codé en Rcpp, on multiplie par environ r round(t3/t4, 2) le temps d'exécution.
Lorqu'on utilise le quick sort codé en R au lieu de celui codé en Rcpp, on multiplie par environ r round(t5/t2, 2) le temps d'exécution.
Ainsi, le code est Rcpp est toujours bien plus rapide que celui en R.
t1/t3 # comparaison radix sort en R et heap sort en R t1/t5 # comparaison radix sort en R et quick sort en R t3/t5 # comparaison heap sort en R et quick sort en R
t2/t4 # comparaison radix sort en Rcpp et heap sort en Rcpp t2/t6 # comparaison radix sort en Rcpp et quick sort en Rcpp t4/t6 # comparaison heap sort en Rcpp et quick sort en Rcpp
Les constatations sont ici globalement les mêmes que dans les simulations précédentes. Cependant, on peut noter ici que le heap sort (version Rcpp) est encore plus efficace qu'habituellement ici.
Simulations dans le cas où le vecteur est trié dans l'ordre décroissant
On s'intéresse ici aux performances de chaque algorithme dans le cas où les valeurs du vecteurs à trier sont rangées dans l'ordre décroissant.
# Valeur de n (taille du vecteur à trier) n <- 10^4 # Nombre de fois où on répète l'algorithme sur un vecteur de taille n nbSimus <- 10 # Temps d'exécutions t1 <- 0 t2 <- 0 t3 <- 0 t4 <- 0 t5 <- 0 t6 <- 0 # Simulations for(i in 1:nbSimus){t1 <- t1 + one.simu(n = n, type = "reverse", func = "radix_sort")} for(i in 1:nbSimus){t2 <- t2 + one.simu(n = n, type = "reverse", func = "radix_sort_Rcpp")} for(i in 1:nbSimus){t3 <- t3 + one.simu(n = n, type = "reverse", func = "heap_sort")} for(i in 1:nbSimus){t4 <- t4 + one.simu(n = n, type = "reverse", func = "heap_sort_Rcpp")} for(i in 1:nbSimus){t5 <- t5 + one.simu(n = n, type = "reverse", func = "quick_sort_opti")} for(i in 1:nbSimus){t6 <- t6 + one.simu(n = n, type = "reverse", func = "quick_sort_Rcpp_opti")}
On affiche les temps d'exécution pour effectuer r nbSimus simulations.
t1 # temps d'exécution du radix sort en R t2 # temps d'exécution du radix sort en Rcpp t3 # temps d'exécution du heap sort en R t4 # temps d'exécution du heap sort en Rcpp t5 # temps d'exécution du quick sort en R t6 # temps d'exécution du quick sort en Rcpp
Comparaison des temps d'exécution.
t1/t2 # radix sort gain R -> Rcpp t3/t4 # heap sort gain R -> Rcpp t5/t6 # quick sort gain R -> Rcpp
t1/t3 # comparaison radix sort en R et heap sort en R t1/t5 # comparaison radix sort en R et quick sort en R t3/t5 # comparaison heap sort en R et quick sort en R
t2/t4 # comparaison radix sort en Rcpp et heap sort en Rcpp t2/t6 # comparaison radix sort en Rcpp et quick sort en Rcpp t4/t6 # comparaison heap sort en Rcpp et quick sort en Rcpp
Ici, le radix sort (version Rcpp) et le heap sort (version Rcpp) affichent les mêmes performances.
Toutes ces simulations nous ont données un aperçu des performances de nos algorithmes dans différents contextes. Si on compare uniquement les versions Rcpp de nos trois algorithmes de tri, on constate après ces simulations que le quick sort semble être le plus lent des trois.
Microbenchmark
Le but de cette partie est d'effectuer des simulations plus approfondies sur nos trois algorithmes de tri afin de mieux les comparer.
Pour cela, nous allons utiliser les packages microbenchmark et ggplot2.
library(microbenchmark) library(ggplot2)
Comparaisons avec des entiers naturels
On commence par comparer les 3 algorithmes en même temps. Sur cet exemple, avec un vecteur de taille $10^4$, on remarque que le radix sort en R est le moins bon des 3. Le radix sort en Rcpp semble meilleur que le heap sort en Rcpp, mais pour confirmer cela, nous allons faire un second essai avec une plus grande taille de vecteur. Concernant les versions R, le radix sort est clairement le meilleur des trois.
n <- 10^4 res <- microbenchmark(one.simu(n = n, type = "integer", func = "radix_sort"), one.simu(n = n, type = "integer", func = "radix_sort_Rcpp"), one.simu(n = n, type = "integer", func = "heap_sort"), one.simu(n = n, type = "integer", func = "heap_sort_Rcpp"), one.simu(n = n, type = "integer", func = "quick_sort_opti"), one.simu(n = n, type = "integer", func = "quick_sort_Rcpp_opti"), times = 50) autoplot(res) print(res)
On fait maintenant un second essai avec une plus grande taille pour le vecteur à trier ($n = 10^6$ ici) et uniquement les versions Rcpp. On remarque le radix sort est généralement meilleur que le heap sort et que le quick sort est le plus lent des trois. Ceci est cohérent avec les résultats précédents (partie Simulations avec des nombres entiers naturels).
n <- 10^6 res <- microbenchmark(one.simu(n = n, type = "integer", func = "radix_sort_Rcpp"), one.simu(n = n, type = "integer", func = "heap_sort_Rcpp"), one.simu(n = n, type = "integer", func = "quick_sort_Rcpp_opti"), times = 50) autoplot(res) print(res)
Comparaisons avec des entiers relatifs
Les constatations sont identiques à celles des comparaisons précédentes (avec des nombres entiers naturels). On peut cependant noter que le tri s'effectue généralement plus lentement ici.
n <- 10^4 res <- microbenchmark(one.simu(n = n, type = "negative integer", func = "radix_sort"), one.simu(n = n, type = "negative integer", func = "radix_sort_Rcpp"), one.simu(n = n, type = "negative integer", func = "heap_sort"), one.simu(n = n, type = "negative integer", func = "heap_sort_Rcpp"), one.simu(n = n, type = "negative integer", func = "quick_sort_opti"), one.simu(n = n, type = "negative integer", func = "quick_sort_Rcpp_opti"), times = 50) autoplot(res) print(res)
Contrairement aux comparaisons précédentes (avec des nombres entiers naturels), ici le temps de tri maximal du radix sort est inférieur à celui du heap sort pour effectuer ce tri. Hormis cela, les constatations sont les mêmes que précédemment.
n <- 10^6 res <- microbenchmark(one.simu(n = n, type = "negative integer", func = "radix_sort_Rcpp"), one.simu(n = n, type = "negative integer", func = "heap_sort_Rcpp"), one.simu(n = n, type = "negative integer", func = "quick_sort_Rcpp_opti"), times = 50) autoplot(res) print(res)
Comparaisons avec des nombres décimaux non signés
Sur ce premier essai, le heap sort (version Rcpp) semble être meilleur que le radix (version Rcpp).
n <- 10^4 res <- microbenchmark(one.simu(n = n, type = "decimal", func = "radix_sort_decimal"), one.simu(n = n, type = "decimal", func = "radix_sort_Rcpp_decimal"), one.simu(n = n, type = "decimal", func = "heap_sort"), one.simu(n = n, type = "decimal", func = "heap_sort_Rcpp"), one.simu(n = n, type = "decimal", func = "quick_sort_opti"), one.simu(n = n, type = "decimal", func = "quick_sort_Rcpp_opti"), times = 50) autoplot(res) print(res)
En augmentant la taille des vecteurs à trier, la différence est bien plus flagrante: le heap sort est clairement le meilleur des trois.
n <- 10^6 res <- microbenchmark(one.simu(n = n, type = "decimal", func = "radix_sort_Rcpp_decimal"), one.simu(n = n, type = "decimal", func = "heap_sort_Rcpp"), one.simu(n = n, type = "decimal", func = "quick_sort_Rcpp_opti"), times = 50) autoplot(res) print(res)
Comparaisons avec des nombres décimaux signés
n <- 10^4 res <- microbenchmark(one.simu(n = n, type = "negative decimal", func = "radix_sort_decimal"), one.simu(n = n, type = "negative decimal", func = "radix_sort_Rcpp_decimal"), one.simu(n = n, type = "negative decimal", func = "heap_sort"), one.simu(n = n, type = "negative decimal", func = "heap_sort_Rcpp"), one.simu(n = n, type = "negative decimal", func = "quick_sort_opti"), one.simu(n = n, type = "negative decimal", func = "quick_sort_Rcpp_opti"), times = 50) autoplot(res) print(res)
n <- 10^6 res <- microbenchmark(one.simu(n = n, type = "negative decimal", func = "radix_sort_Rcpp_decimal"), one.simu(n = n, type = "negative decimal", func = "heap_sort_Rcpp"), one.simu(n = n, type = "negative decimal", func = "quick_sort_Rcpp_opti"), times = 50) autoplot(res) print(res)
Les constatations sont les mêmes que dans les comparaisons précédentes (avec des nombres décimaux positifs).
Comparaison dans le cas où le vecteur est trié dans l'ordre décroissant
Sur ce premier essai, c'est le radix sort (version Rcpp) qui semble être le meilleur suivi du heap sort (version Rcpp)
n <- 10^4 res <- microbenchmark(one.simu(n = n, type = "reverse", func = "radix_sort"), one.simu(n = n, type = "reverse", func = "radix_sort_Rcpp"), one.simu(n = n, type = "reverse", func = "heap_sort"), one.simu(n = n, type = "reverse", func = "heap_sort_Rcpp"), one.simu(n = n, type = "reverse", func = "quick_sort_opti"), one.simu(n = n, type = "reverse", func = "quick_sort_Rcpp_opti"), times = 50) autoplot(res) print(res)
Cependant, lorsqu'on augmente la taille des vecteurs à trier, on remarque c'est le heap sort qui reprend l'avantage et qui devient le meilleur des trois.
n <- 10^6 res <- microbenchmark(one.simu(n = n, type = "reverse", func = "radix_sort_Rcpp"), one.simu(n = n, type = "reverse", func = "heap_sort_Rcpp"), one.simu(n = n, type = "reverse", func = "quick_sort_Rcpp_opti"), times = 50) autoplot(res) print(res)
Complexité
Le but de cette partie est d'évaluer la complexité du radix sort, du heap sort et du quick sort. On évaluera cette complexité en utilisant des vecteurs de nombres entiers naturels.
Radix sort en R
On lance $nbRep = 100$ fois l'algorithme radix sort pour chaque valeur du vecteur vector_n de taille $nbSimus = 20$. On affiche le graphe du temps d'exécution moyen en fonction de la taille des données.
nbSimus <- 20 vector_n <- seq(from = 5000, to = 50000, length.out = nbSimus) nbRep <- 100 res_radix <- data.frame(matrix(0, nbSimus, nbRep + 1)) colnames(res_radix) <- c("n", paste0("Rep",1:nbRep)) j <- 1 for(i in vector_n) { res_radix[j,] <- c(i, replicate(nbRep, one.simu(i, func = "radix_sort"))) #print(j) j <- j + 1 } res <- rowMeans(res_radix[,-1]) plot(vector_n, res, type = 'b', xlab = "data length", ylab = "mean time in seconds")
lm(log(res) ~ log(vector_n))
Radix sort en Rcpp
En Rcpp, on constate qu'on gagne énormément de temps par rapport au code R. Cependant, on n'a plus du tout la tendance "linéaire" de la courbe.
nbSimus <- 20 vector_n <- seq(from = 5000, to = 50000, length.out = nbSimus) nbRep <- 100 res_radix_rcpp <- data.frame(matrix(0, nbSimus, nbRep + 1)) colnames(res_radix_rcpp) <- c("n", paste0("Rep",1:nbRep)) j <- 1 for(i in vector_n) { res_radix_rcpp[j,] <- c(i, replicate(nbRep, one.simu(i, func = "radix_sort_Rcpp"))) #print(j) j <- j + 1 } res <- rowMeans(res_radix_rcpp[,-1]) plot(vector_n, res, type = 'b', xlab = "data length", ylab = "mean time in seconds")
lm(log(res) ~ log(vector_n))
Radix sort en R (version nombres décimaux)
On remarque que l'algorithme est bien plus lent ici comparé à la version optimisée pour les entiers naturels et relatifs. Cela s'explique par le fait que celui-ci a été optimisé pour le tri des nombres décimaux.
nbSimus <- 20 vector_n <- seq(from = 5000, to = 50000, length.out = nbSimus) nbRep <- 100 res_radix_rcpp <- data.frame(matrix(0, nbSimus, nbRep + 1)) colnames(res_radix_rcpp) <- c("n", paste0("Rep",1:nbRep)) j <- 1 for(i in vector_n) { res_radix_rcpp[j,] <- c(i, replicate(nbRep, one.simu(i, func = "radix_sort_decimal"))) #print(j) j <- j + 1 } res <- rowMeans(res_radix_rcpp[,-1]) plot(vector_n, res, type = 'b', xlab = "data length", ylab = "mean time in seconds")
lm(log(res) ~ log(vector_n))
Radix sort en Rcpp (version nombres décimaux)
En Rcpp, on constate à nouveau qu'on gagne énormément de temps par rapport au code R. Cependant, on n'a plus du tout la tendance "linéaire" de la courbe.
nbSimus <- 20 vector_n <- seq(from = 5000, to = 50000, length.out = nbSimus) nbRep <- 100 res_radix_rcpp <- data.frame(matrix(0, nbSimus, nbRep + 1)) colnames(res_radix_rcpp) <- c("n", paste0("Rep",1:nbRep)) j <- 1 for(i in vector_n) { res_radix_rcpp[j,] <- c(i, replicate(nbRep, one.simu(i, func = "radix_sort_Rcpp_decimal"))) #print(j) j <- j + 1 } res <- rowMeans(res_radix_rcpp[,-1]) plot(vector_n, res, type = 'b', xlab = "data length", ylab = "mean time in seconds")
lm(log(res) ~ log(vector_n))
Heap sort en Rcpp
Le heap sort est généralement plus lent que le radix sort ici, ce qui est cohérent avec les constatations des parties précédentes.
nbSimus <- 20 vector_n <- seq(from = 5000, to = 50000, length.out = nbSimus) nbRep <- 100 res_heap_sort_rcpp <- data.frame(matrix(0, nbSimus, nbRep + 1)) colnames(res_heap_sort_rcpp) <- c("n", paste0("Rep",1:nbRep)) j <- 1 for(i in vector_n) { res_heap_sort_rcpp[j,] <- c(i, replicate(nbRep, one.simu(i, func = "heap_sort_Rcpp"))) #print(j) j <- j + 1 } res <- rowMeans(res_heap_sort_rcpp[,-1]) plot(vector_n, res, type = 'b', xlab = "data length", ylab = "mean time in seconds")
lm(log(res) ~ log(vector_n))
Quick sort en Rcpp
Le quick sort est généralement le plus lent des trois ici, ce qui est cohérent avec les constatations des parties précédentes.
nbSimus <- 20 vector_n <- seq(from = 5000, to = 50000, length.out = nbSimus) nbRep <- 100 res_quick_sort_rcpp <- data.frame(matrix(0, nbSimus, nbRep + 1)) colnames(res_quick_sort_rcpp) <- c("n", paste0("Rep",1:nbRep)) j <- 1 for(i in vector_n) { res_quick_sort_rcpp[j,] <- c(i, replicate(nbRep, one.simu(i, func = "quick_sort_Rcpp_opti"))) #print(j) j <- j + 1 } res <- rowMeans(res_quick_sort_rcpp[,-1]) plot(vector_n, res, type = 'b', xlab = "data length", ylab = "mean time in seconds")
lm(log(res) ~ log(vector_n))
R Package Documentation
Browse R Packages
We want your feedback!
Note that we can't provide technical support on individual packages. You should contact the package authors for that.
Embedding an R snippet on your website
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.