Structures de données purement fonctionnelles - Historique des versions

Dornel le 29 mai 2020 à 09:02

2020-05-29T09:02:22Z

@@ Ligne 334 : / Ligne 334 : @@
 === Tas binomial ===
-[[File:Schema_3.png|500px|thumb|right|Représentation des arbres binaires de rangs 0 à 3]]
+[[File:Schema_3.png|300px|thumb|right|Représentation des arbres binaires de rangs 0 à 3]]
 Les tas binomiaux sont des tas composés d'un type plus primitif appelé arbre binomial. Les arbres binomiaux sont défini inductivement comme suit :
@@ Ligne 441 : / Ligne 441 : @@
 === Arbre rouge / noir ===
 == Évolution du domaine de recherche ==

Dornel : /* Arbre rouge / noir */

2020-05-29T07:45:06Z

Arbre rouge / noir

← Version précédente		Version du 29 mai 2020 à 07:45
Ligne 440 :		Ligne 440 :

	=== Arbre rouge / noir ===		=== Arbre rouge / noir ===

			Précédemment, nous avons vu les arbres de recherche binaires. Bien que cette structure fonctionne bien avec des données aléatoires ou désordonnées, leur performance est grandement réduite avec des données ordonnées car toutes les opérations ont un temps d'exécution d'ordre allant jusqu'à O(n). Une solution à ce problème est de garder chaque arbre relativement équilibré. Ainsi, aucune opération n'a de temps d'exécution d'ordre excédant O(log n). Une famille d'arbres de recherche binaires équilibrés populaire est celle des arbres bicolores, ou arbres rouge-noir.

	== Évolution du domaine de recherche ==		== Évolution du domaine de recherche ==

Dornel : /* Sources et annexes */

2020-05-28T14:43:35Z

Sources et annexes

← Version précédente		Version du 28 mai 2020 à 14:43
Ligne 466 :		Ligne 466 :

	'''Annexes'''		'''Annexes'''

			* [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.39.5334&rep=rep1&type=pdf#page=7 Manufacturing Datatypes]

			* [https://www.researchgate.net/publication/221282345_Scrap_Your_Boilerplate_A_Practical_Design_Pattern_for_Generic_Programming Scrap your boilerplate: a practical design pattern for generic programming]

			* [https://archive.alvb.in/msc/03_infoafp/papers/2012-12-18_WerkCollege_FingerTreesRalfHinze.pdf Finger trees: a simple general-purpose data structure]

			* [https://www.microsoft.com/en-us/research/wp-content/uploads/2009/09/Parallel-Concurrent-ML.pdf Parallel Concurrent ML]

Dornel : /* Évolution du domaine de recherche */

2020-05-28T14:41:44Z

Évolution du domaine de recherche

← Version précédente		Version du 28 mai 2020 à 14:41
Ligne 442 :		Ligne 442 :

	== Évolution du domaine de recherche ==		== Évolution du domaine de recherche ==

			Après s'être penché en détail sur la thèse d'Okasaki, voici quelques articles plus récents en rapport avec le sujet permettant d'élargir la question.

			* '''Manufacturing Datatypes''' par Ralf Hinze, publié en 1999 et édité par Okasaki traitant d'une structure générale pour construire des structures de données purement fonctionnelles permettant de satisfaire des contraintes de taille ou de forme, notamment pour l'implémentation de matrices et de certains types d'arbres.

			* '''Scrap your boilerplate: a practical design pattern for generic programming''' de Ralf Lämmel et Simon Peyton-Jones proposant un modèle de métastructure, c'est-à-dire (une structure permettant de générer du code ?), afin de remédier à l'usage de code passe-partout, autrement dit du code répété à plusieurs reprises avec très peu de modifications.

			* '''Finger trees: a simple general-purpose data structure''' de Ralf Hinze et Ross Paterson introduisant une nouvelle structure : les arbres pointés 2-3 permettant d'accéder aux feuilles dans un laps de temps amorti constant. Cette structure peut servir de base pour plusieurs autres structures de données.

			* '''Parallel Concurrent ML''' de John Reppy, Claudio V. Russo et Yingqi Xiao présentant le langage fonctionnel concurrent CML (pour Concurrent ML), c'est-à-dire que le programme peut utiliser plusieurs processus simultanément, réduisant le temps d'exécution.

	== Sources et annexes ==		== Sources et annexes ==

Dornel : /* Tas binomial */

2020-05-28T12:25:21Z

Tas binomial

← Version précédente		Version du 28 mai 2020 à 12:25
Ligne 334 :		Ligne 334 :
	=== Tas binomial ===		=== Tas binomial ===

	[[File:Schema_3.png\|~~300px~~\|thumb\|right\|Représentation des arbres binaires de rangs 0 à 3]]		[[File:Schema_3.png\|500px\|thumb\|right\|Représentation des arbres binaires de rangs 0 à 3]]

	Les tas binomiaux sont des tas composés d'un type plus primitif appelé arbre binomial. Les arbres binomiaux sont défini inductivement comme suit :		Les tas binomiaux sont des tas composés d'un type plus primitif appelé arbre binomial. Les arbres binomiaux sont défini inductivement comme suit :

Dornel : /* Tas binomial */

2020-05-28T12:22:57Z

Tas binomial

@@ Ligne 365 : / Ligne 365 : @@
   let root (Node(_, x, _)) = x
   let rec insTree...
-  let insert = fun x ts -> insTree (Node(0, x, [])) ts
+  let insert = ...
   let rec merge...
@@ Ligne 378 : / Ligne 375 : @@
   let rec removeMinTree...
-  let findMin = fun ts -> let (t, _) = removeMinTree ts in root t
+  let findMin = ...
 end;;</pre>
-Les fonctions que nous allons étudier ici sont insTree, merge et removeMinTree.
+Les fonctions que nous allons étudier ici sont link, insert, merge, findMin et deleteMin.
 === Arbre rouge / noir ===

Dornel : /* Tas binomial */

2020-05-28T11:25:49Z

Tas binomial

← Version précédente		Version du 28 mai 2020 à 11:25
Ligne 348 :		Ligne 348 :

	Dans le code ci-dessous, on représente un nœud dans un arbre binomial comme un élément avec une liste de ses enfants. Par commodité, on note aussi le rang de chaque nœud.		Dans le code ci-dessous, on représente un nœud dans un arbre binomial comme un élément avec une liste de ses enfants. Par commodité, on note aussi le rang de chaque nœud.

			De plus, un tas binomial étant une liste d'arbres binomiaux ne pouvant comporter qu'un seul arbre d'un rang donné et un arbre binomial de rang r comportant 2<sup>r</sup> éléments, on constate alors que les arbres d'un tas binomial de taille n correspondent à la représentation binaire de n.

			Par exemple, la représentation binaire de 13 est 1101, donc un tas binomial de taille 13 contient un arbre de rang 0, un de rang 2 et un de rang 3 (de taille respective 1, 4 et 8).
			De plus, comme la représentation binaire de n contient au plus ⌊log(n + 1)⌋ bits à 1, un tas binomial de taille n contient au plus ⌊log(n + 1)⌋ arbres.

	<pre lang="OCaml">module BinomialHeap (O: ORDERED) = struct		<pre lang="OCaml">module BinomialHeap (O: ORDERED) = struct
Ligne 377 :		Ligne 382 :
	let deleteMin = fun ts -> let (Node(_, x, ts1), ts2) = removeMinTree ts in merge (rev ts1) ts2		let deleteMin = fun ts -> let (Node(_, x, ts1), ts2) = removeMinTree ts in merge (rev ts1) ts2
	end;;</pre>		end;;</pre>

			Les fonctions que nous allons étudier ici sont insTree, merge et removeMinTree.

			* '''insTree -

	=== Arbre rouge / noir ===		=== Arbre rouge / noir ===

Dornel : /* Tas binomial */

2020-05-28T09:10:18Z

Tas binomial

← Version précédente		Version du 28 mai 2020 à 09:10
Ligne 333 :		Ligne 333 :

	=== Tas binomial ===		=== Tas binomial ===

			[[File:Schema_3.png\|300px\|thumb\|right\|Représentation des arbres binaires de rangs 0 à 3]]

			Les tas binomiaux sont des tas composés d'un type plus primitif appelé arbre binomial. Les arbres binomiaux sont défini inductivement comme suit :

			* Un arbre binomial de rang 0 est un singleton de nœud ;
			* Un arbre binomial de rang r est formé en liant deux arbres binomiaux de rang r-1 tel qu'un des arbres devient l'enfant le plus à gauche de l'autre.

			De cette définition, on comprend qu'un arbre binomial de rang r contient exactement 2<sup>r</sup> nœuds.

			Il existe une deuxième définition équivalente des arbres binomiaux :

			* Un arbre binomial de rang r est un nœud ayant r enfants t<sub>1</sub> à t<sub>r</sub> où chaque enfant t<sub>i</sub> est un arbre binomial de rang r - i.

			Dans le code ci-dessous, on représente un nœud dans un arbre binomial comme un élément avec une liste de ses enfants. Par commodité, on note aussi le rang de chaque nœud.

			<pre lang="OCaml">module BinomialHeap (O: ORDERED) = struct
			type elem = O.t

			type tree = Node of (int * elem * tree list)
			type heap = tree list

			exception EmptyHeap

			let rank (Node(r, _, _)) = r
			let root (Node(_, x, _)) = x

			let link = fun (Node(r, x1, c1) as t1) (Node(_, x2, c2) as t2) ->
			if (O.leq x1 x2)
			then Node(r + 1, x1, t2 :: c1)
			else Node(r + 1, x2, t1 :: c2)

			let rec insTree...

			let insert = fun x ts -> insTree (Node(0, x, [])) ts

			let rec merge...

			let rec removeMinTree...

			let findMin = fun ts -> let (t, _) = removeMinTree ts in root t

			let deleteMin = fun ts -> let (Node(_, x, ts1), ts2) = removeMinTree ts in merge (rev ts1) ts2
			end;;</pre>

	=== Arbre rouge / noir ===		=== Arbre rouge / noir ===

Dornel : /* Sources et annexes */

2020-05-28T07:41:48Z

Sources et annexes

← Version précédente		Version du 28 mai 2020 à 07:41
Ligne 346 :		Ligne 346 :
	* [https://doc.lagout.org/programmation/Functional%20Programming/Chris_Okasaki-Purely_Functional_Data_Structures-Cambridge_University_Press%281998%29.pdf Purely functional data structures, Chris Okasaki]		* [https://doc.lagout.org/programmation/Functional%20Programming/Chris_Okasaki-Purely_Functional_Data_Structures-Cambridge_University_Press%281998%29.pdf Purely functional data structures, Chris Okasaki]

	* [https://fr.wikipedia.org/wiki/Programmation_fonctionnelle Programmation fonctionnelle (Wikipédia)]		* [https://fr.wikipedia.org/wiki/Programmation_fonctionnelle Programmation fonctionnelle (Wikipédia FR)]

			* [https://en.wikipedia.org/wiki/Leftist_tree Tas gaucher (Wikipédia EN)]

	'''Annexes'''		'''Annexes'''

Dornel : /* Tas gaucher */

2020-05-28T07:40:53Z

Tas gaucher

← Version précédente		Version du 28 mai 2020 à 07:40
Ligne 249 :		Ligne 249 :
	=== Tas gaucher ===		=== Tas gaucher ===

	[[Fichier:Schema_2.png\|~~300px~~\|thumb\|right\|Exemple de tas gaucher et illustration de la notion de rang.]]		[[Fichier:Schema_2.png\|150px\|thumb\|right\|Exemple de tas gaucher et illustration de la notion de rang.]]

	Un tas est une version d'arbre particulière. En effet, elle se caractérise par le fait que la valeur de chaque nœud ne peut être plus grand que n'importe laquelle de ses enfants. Cette caractéristique fait que l'élément le plus petit se trouve toujours à la racine.		Un tas est une version d'arbre particulière. En effet, elle se caractérise par le fait que la valeur de chaque nœud ne peut être plus grand que n'importe laquelle de ses enfants. Cette caractéristique fait que l'élément le plus petit se trouve toujours à la racine.
Ligne 257 :		Ligne 257 :
	Soit r le rang de la racine d'un tas gaucher de taille n. On peut en déduire que chaque nœud de profondeur inférieure ou égale à r-1 a exactement deux enfants, car sinon r aurait une valeur plus faible ou la propriété gauchère ne serait pas respectée. Ainsi, on peut affirmer que la taille d'un tas est donc d'au moins 2<sup>r</sup> - 1. De ce fait, on peut en déduire que le rang de la racine vaut au plus log(n + 1). Par conséquent, la colonne vertébrale droite d'un tas gaucher de taille n comporte au plus ⌊log(n + 1)⌋ éléments.		Soit r le rang de la racine d'un tas gaucher de taille n. On peut en déduire que chaque nœud de profondeur inférieure ou égale à r-1 a exactement deux enfants, car sinon r aurait une valeur plus faible ou la propriété gauchère ne serait pas respectée. Ainsi, on peut affirmer que la taille d'un tas est donc d'au moins 2<sup>r</sup> - 1. De ce fait, on peut en déduire que le rang de la racine vaut au plus log(n + 1). Par conséquent, la colonne vertébrale droite d'un tas gaucher de taille n comporte au plus ⌊log(n + 1)⌋ éléments.

			''Code de la structure tas gaucher''
	<pre lang="OCaml">module LeftistHeap (O: ORDERED) = struct		<pre lang="OCaml">module LeftistHeap (O: ORDERED) = struct
	type elem = O.t		type elem = O.t
Ligne 285 :		Ligne 286 :

	Afin de simplifier l'opération, on remarque que la colonne vertébrale droite d'un tas gaucher est ordonnée. On en déduit que le concept clé est de fusionner les colonnes vertébrales des deux tas comme on fusionnerait deux listes triées avant d'échanger les enfants le long de la branche afin de restaurer la propriété gauchère.		Afin de simplifier l'opération, on remarque que la colonne vertébrale droite d'un tas gaucher est ordonnée. On en déduit que le concept clé est de fusionner les colonnes vertébrales des deux tas comme on fusionnerait deux listes triées avant d'échanger les enfants le long de la branche afin de restaurer la propriété gauchère.

			Comme il a été démontré précédemment que la longueur de la colonne vertébrale est au plus logarithmique, on peut en déduire que merge a un temps d'exécution d'ordre O(log n).

	<pre lang="OCaml">let makeH = fun v a b ->		<pre lang="OCaml">let makeH = fun v a b ->
Ligne 307 :		Ligne 310 :
	* '''insert - Insère une valeur dans l'arbre'''		* '''insert - Insère une valeur dans l'arbre'''

	Une fois merge défini, il suffit d'établir que l'on veut fusionner le tas avec un tas d'une seule valeur.		Une fois merge défini, il suffit d'établir que l'on veut fusionner le tas avec un tas d'une seule valeur. Et puisque le temps d'exécution de merge est d'ordre O(log n), il en va de même pour insert.

	<pre lang="OCaml">let insert = fun v h -> (merge (Cons(1, Nil, v, Nil)) h)</pre>		<pre lang="OCaml">let insert = fun v h -> (merge (Cons(1, Nil, v, Nil)) h)</pre>
Ligne 322 :		Ligne 325 :
	* '''deleteMin - Supprime le minimum'''		* '''deleteMin - Supprime le minimum'''

	Similairement, le minimum étant à la racine, on peut établir que le supprimer revient à fusionner ses enfants.		Similairement, le minimum étant à la racine, on peut établir que le supprimer revient à fusionner ses enfants. De plus, merge ayant un temps d'exécution d'ordre O(log n), celui de deleteMin est le même.

	<pre lang="OCaml">let deleteMin = fun h ->		<pre lang="OCaml">let deleteMin = fun h ->

Structures de données purement fonctionnelles - Historique des versions

Dornel le 29 mai 2020 à 09:02

Dornel : /* Arbre rouge / noir */

Dornel : /* Sources et annexes */

Dornel : /* Évolution du domaine de recherche */

Dornel : /* Tas binomial */

Dornel : /* Tas binomial */

Dornel : /* Tas binomial */

Dornel : /* Tas binomial */

Dornel : /* Sources et annexes */

Dornel : /* Tas gaucher */

Dornel : /* Arbre rouge / noir */

Dornel : /* Sources et annexes */

Dornel : /* Évolution du domaine de recherche */

Dornel : /* Tas binomial */

Dornel : /* Tas binomial */

Dornel : /* Tas binomial */

Dornel : /* Tas binomial */

Dornel : /* Sources et annexes */

Dornel : /* Tas gaucher */