février
2010
Un article de SpiceGuid
Le tas binaire est un tableau qui implémente un arbre pseudo-complet vérifiant la propriété de tas.
Un tableau est de taille fixe. Par conséquent un tas binaire est borné, on ne peut y insérer qu’un nombre fixe et limité d’éléments. Bien sûr on pourrait redimensionner le tableau dynamiquement, mais cela a un impact négatif sur le coût des opérations.
Qu’on prêche le style impératif ou le style fonctionnel est étrangé à l’affaire.
La bonne question c’est de savoir si on connait d’avance le nombre d’éléments à insérer ou non.
Si on le connait alors un tas binaire fera très bien l’affaire.
Si on ne le connait pas, alors autant opter tout de suite pour un arbre binaire, même si on veut garder un style impératif.
Ça serait exactement la même problématique avec un dictionnaire. On peut faire une recherche dichotomique dans un tableau trié. Ou alors on peut faire une recherche dans un arbre ordonnée.
Dans les deux cas l’algorithme de recherche est le même, il s’agit dune boucle qui à chaque étape découpe l’espace de recherche en deux moitiés dont une seule peut contenir l’élément recherché.
Le paradigme a bien un impact sur le programmeur mais c’est parce que le programmeur est trop attaché à la syntaxe.
En réalité le paradigme impacte plus fortement la façon de faire que la façon de penser.
L’expérience aussi est un facteur qui impacte la façon de faire.
C’est pourquoi je préfère parler de style plutôt que de paradigme.
Le tas de Braun
Un petit rappel de quelques définitions :
On l’appelle tas de Braun parce que l’insertion répétée dans l’arbre vide produit un arbre de Braun.
Un autre nom est heap-ordered binary tree mais c’est moins spécifique.
type 'a heap =
| E (* 'a empty heap *)
| N of 'a non_empty_heap
and 'a non_empty_heap =
{mutable l: 'a heap; mutable e: 'a; mutable r: 'a heap}
Remarques :
- on a un type tas non-vide, il n’y aura pas d’exceptions dans le code, la contrainte sur l’argument des fonctions find_max et remove_max sera exprimée par le type, la contrainte sur le résultat de insert également
- les champs sont mutables, c’est parce qu’on va utiliser le même type pour les deux styles de programmation, les algorithmes seront les mêmes, mais dans un cas on fera de la copie, dans l’autre on fera de la modification sur place
La fonction find_max est triviale :
Le style fonctionnel
On devrait dire le style immutable.
Je commence toujours par le style immutable parce que c’est plus lisible.
J’ai choisi un tas-max plutôt qu’un tas-min, pour un tas-min il n’y aura qu’à changer le signe où inverser le signe de la fonction compare.
let rec add x = function
| E ->
{l=E;e=x;r=E}
| N n ->
if compare n.e x > 0 then {l=N (add x n.r);e=n.e;r=n.l}
else {l=N (add n.e n.r);e=x;r=n.l}
let rec remove_max = function
| {l=E;r=t} | {r=E;l=t} ->
t
| {l=N l;e=e;r=N r} ->
if compare l.e r.e > 0 then N {l=remove_max l;e=l.e;r=N r}
else N {l=N l;e=r.e;r=remove_max r}
Le style impératif
On devrait dire le style mutable.
Je traduis à partir de la version en style immutable.
let rec insert x = function
| E ->
{l=E;e=x;r=E}
| N n ->
let nr = n.r in
n.r <- n.l;
if compare n.e x > 0 then n.l <- N (insert x nr)
else (n.l <- N (insert n.e nr); n.e <- x);
n
let rec delete_max h =
match h with
| {l=E;r=t} | {r=E;l=t} ->
t
| {l=N l;e=e;r=N r} ->
if compare l.e r.e > 0 then (h.e <- l.e; h.l <- delete_max l)
else (h.e <- r.e; h.r <- delete_max r);
N h
Autres opérations
Il faut mentionner qu’un tas de Braun offre des tas de possibilités de variantes et d’extensions qui seraient bien plus difficiles à implanter à l’aide d’un tas binaire.
Je ne vais pas être exhaustif sur ce point, je vais cependant en citer deux.
Il est également possible de supprimer un élément arbitraire dans un tas en le faissant percoler jusqu’à la racine puis en invoquant remove_max.
La fusion
Il est possible de fusionner deux tas de Braun en un seul tas.
let rec join ha hb =
match ha,hb with
| t,E | E,t ->
t
| N a,N b ->
if compare a.e b.e > 0 then N {l=join a.l a.r;e=a.e;r=hb}
else N {l=ha;e=b.e;r=join b.l b.r}
On peut accélérer l’opération de fusion à l’aide d’une technique dite de « structural bootstrapping ».
Grâce à cette technique il est possible de fusionner deux tas simplement en insérant l’un dans l’autre.
L’arbre tournoi
On peut modifier légèrement les opérations d’insertion et de suppression pour que le tas restitue l’ordre d’insertion quand on le parcourre dans l’ordre infixe.
Toutefois cette modification a un impact sur la performance, le tas n’est plus pseudo-complet comme un arbre de Braun.
Typiquement on insère les scores dans l’arbre tournoi, le gagnant est toujours à la racine.
Le parcourt infixe restitue la liste des scores dans l’ordre d’apparition des joueurs.
let rec add x = function
| E ->
{l=E;e=x;r=E}
| N n ->
if compare n.e x > 0 then {n with r=N (add x n.r)}
else {l=N n;e=x;r=E}
let rec remove_max = function
| {l=E;r=t} | {r=E;l=t} ->
t
| {l=N l;e=e;r=N r} as t ->
if compare l.e r.e > 0 then
N{l=l.l;e=l.e;r=remove_max {t with l=l.r}}
else
N{l=remove_max {t with r=r.l};e=r.e;r=r.r}
Conclusion
La chose à retenir c’est que ce n’est pas le fonctionnel qui force à changer de structure de données.
Ce qui force à changer de structure de données c’est le fait qu’un tableau n’est pas toujours la meilleure option. Utiliser une liste ou un arbre au lieu d’un tableau n’interdit pas le style mutable.
Il n’y a pas un paradigme impératif qui s’oppose à un paradigme impératif fonctionnel, il y a juste le style mutable et le style immutable qui sont deux façons d’implanter un même algorithme pour une même structure de données.
On peut d’ailleurs très bien adopter le style immutable avec un langage à objets si le ramasse-miettes est suffisamment efficace pour ça.