In vrunge/M2algorithmique: Example of an Rcpp package for M2 Data Science students

\noindent\hrulefill

Description du problème et objectif

Nous étudions dans ce document le problème de recherche du plus court chemin entre deux noeuds d'un graphe. Un graphe $\mathcal{G}$ est composé d'un ensemble de sommets $V$ et d'arrêtes $E$ qui sont des triplets de type $(v_1,v_2, c)$ qui exprime le coût positif $c$ de relier le sommet $v_1$ au sommet $v_2$ (ou inversement, l'arrête n'est ici par orientée).

La page wikipédia du tri rassemble de nombreux algorithmes de tri avec leurs avantages et inconvénients respectifs. La complexité du problème de tri (par comparaison) est de $O(n \log n)$ pour un vecteur de longueur $n$. Cela signifie que, théoriquement, aucun algorithme ne pourra jamais être plus rapide que cette borne asymptotique. Le radix sort et quelques autres algorithmes sont en temps $O(n)$ mais demandent des hypothèses supplémentaires sur les données (ce n'est plus un tri par comparaison).

Dans ce document, nous concentrons notre attention sur deux algorithmes de tri:

1) le tri par insertion, de complexité $O(n^2)$

2) le tri par tas (heap sort), de complexité $O(n \log(n))$. Des détails sur le tri par tas sont donnés dans le lien, en particulier les animations donnent une bonne idée du fonctionnement d'un tas.

Nous avons donc ici deux méthodes l'une naïve, l'autre plus évoluée. Nos objectifs sont alors:

a) d'implémenter ces algorithmes en R et en C++ et évaluer le gain de temps;

b) de confirmer les complexités théoriques trouvées sur le papier (ce n'est pas fait dans ce document mais a été fait dans le cours) par des simulations intensives.

---

À noter que le (b) se termine toujours par l'évaluation d'une pente sur une régression linéaire en échelle log-log. Cela donne une évaluation de la valeur $x$ dans la complexité de type $O(n^x)$ ou $O(n^x \log^y(n))$.

Nous allons ajouter une étape en plus. En effet, l'évaluation de la complexité se fait sur des données simulées, issues d'une certaine distribution de probabilité. Nous souhaitons étudier le temps d'exécution dans un cas plus favorable à l'algorithme d'insertion.

---

Un premier exemple

Le package se télécharge ainsi :

devtools::install_github("vrunge/M2algorithmique")

et ses fonctions sont rendues disponibles sur Rstudio ainsi :

library(M2algorithmique)

On simule un petit exemple d'un vecteur v de taille 100

n <- 100
v <- sample(n)

On teste les 4 algorithmes implémentés avec des noms explicites :

• insertion_sort
• heap_sort
• insertion_sort_Rcpp
• heap_sort_Rcpp

Cela donne :

v
insertion_sort(v)
heap_sort(v)
insertion_sort_Rcpp(v)
heap_sort_Rcpp(v)

---

Comparaison R avec C++

vrunge/M2algorithmique documentation built on April 5, 2025, 4:06 a.m.