Programmation 2: TP 6

Introduction

La mémoization est une technique d'optimisation qui consiste à conserver les résultats d'une opération d'un appel à l'autre. L'objectif est donc d'accumuler les résultats déjà établis dans une structure (impérative) pour éviter de les recalculer au besoin.

On utilise souvent la mémoization sur des structures construites par saturation ou fermeture transitive: lorsque l'appartenance à la structure est définie à l'aide d'une relation initiale et d'une définition récursive.

Pour ce TP vous devrez lire (en partie du moins) la documentation des modules Hashtbl[1] et Set[2] (notamment les détails sur le foncteur Set.Make.)

Premier exemple: memoization d'une fonction récursive

Il relativement simple de mémoizer une fonction simple en OCaml: on crée une fonction dans laquelle on conserve une table des valeurs déjà rencontrées et si le résultat n'est pas dans la table, on le calcule avec la fonction d'origine et on l'ajoute à la table avant de renvoyer le résultat.

À l'aide de l'ordre supérieur et des tables de hash prédéfinies, on obtient facilement une fonction de memoization générique:

let memo f =
  let h = Hashtbl.create 101 in (* on choisit un nombre premier adéquate *)
    fun x ->
      try Hashtbl.find h x with
	  Not_found ->
	    let y = f x in
	      Hashtbl.add h x y;
	      y

Cette fonction est un générateur de fonction, on devra l'appliquer à la fonction à mémoizer pour obtenir la version efficace avec sa table associée.

let ma_fonction x = (* fonction lourde à calculer *)
(* version avec mémoization *)
let ma_fonction_rapide = memo ma_fonction

Seulement, sur une fonction récursive, on ne profite pas de la mémoization lors du calcul de la fonction récursive. Il nous faut donc écrire un opérateur de point fixe (une fonction qui simule le calcul récursif.)

Pour ça, il faut passer par une forme particulière de récursivité: la continuation. Il s'agit ici d'une variante simple de cette technique (qui nécessite normalement un support particulier dans le langage.) Le principe est le suivant, la fonction récursive par continuation prend en paramètre la fonction permettant de faire la suite du travail.

Voici un exemple avec factorielle:

(* opérateur de point fixe *)
let mu f =
  let rec aux x = f aux x in
    aux
 
(* factorielle par contination *)
let cont_fact fact = function
    0|1 -> 1
  | n -> n * fact (n-1)
 
(* application *)
let x = mu cont_fact 5

Bien évidement, ce principe n'a que peut d'intéret dans l'exemple courrant. Mais, combiner avec les techniques de mémoization, il nous permet d'appliquer la mémoization aux fonctions récursives.

• Exercice: écrire une version de la fonction memo sur le même principe que la fonction mu.

val memo : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b

Appliquer à la version suivante de Fibonacci, on obtient un calcul de fibonacci presque linéaire (pour les premières éxécutions) et qui tend vers du temps constant après de nombreuses utilisation.

let cont_fibo next = function
  | 0 | 1 as x -> x
  | x -> next (x-1) + next (x-2)
 
let fibo = memo cont_fibo

Vous pouvez évaluer l'efficacité de notre mémoization en ajoutant dans votre fonction de mémoization un affichage à chaque fois que la valeur demandée n'est pas dans la table de hash.

Memoization avancée: relation transitive

Cloture transitive

Une relation transitive est une application dans un ensemble dans lui même, définie à l'aide d'une relation initiale (le noyeau de notre relation) et d'une définition récursive. Supposons que R₀ soit notre relation initiale, alors la relation R peut être définie par:

La relation R est la cloture transitive de la relation R₀.

Utilisation de la memoization

En fonction de la nature de R₀, sa colture transitive n'est pas forcément finie et même si elle est finie, son calcul complet peut s'avérer très couteux. Dans ce cas là, on préfère travailler par mémoization: à chaque fois que l'on cherche si un coupe (x,y) appartient à R, si c'est le cas on l'ajoute au noyeau de R.

On va donc représenter notre relation à l'aide d'une structure modifiable nous permettant de sauver les résultats intermédiaires.

Il existe deux possibilités pour stocker la relation: stocker les couples qui lui appartiennent ou choisir de stocker les couples sous forme d'association entre un élément et tous ceux avec qui il est relié. Cette deuxième solution est la plus adaptée à notre problème.

Construction des relations

Les relations que nous allons construire contiendront des couples de string.

Pour notre relation, nous avons besoin de deux choses: la structure globale contenant l'association entre une clef et les élément qui lui sont associés, et justement l'ensemble des éléments associés à une clef. Pour le second, nous choisirons d'utiliser le module Set d'OCaml, pour ça il nous faut construire une version pour les chaînes de caractères:

module StringSet = Set.Make(String)

Une relation sera représentée à l'aide d'une table de Hash, nous utiliserons la fonction suivante pour récupérer l'ensemble des éléments en relation avec un autre:

let get_succ x r =
  try Hashtbl.find r x with Not_found -> StringSet.empty

Ensuite, nous utiliserons pour la mise à jour de la relation la fonction suivante:

let extend r a b =
  Hashtbl.replace r a (StringSet.add x (get_succ a r))

Pour constuire notre table de hash, il nous faut une taille de départ, en général, on choisit une valeur de même ordre de grandeur que la taille des données à stocker. On choisit également un nombre premier pour miniser les collisions. Nous allons commencer par écrire une petite fonction qui trouve le prochain nombre premier depuis un entier donné.

• Exercice: écrire la fonction suivante:

val next_prime: int -> int

next_prime n renvoie le plus petit nombre premier supérieur ou égal à n

• Exercice: écrire la fonction suivante

val make : ('a * StringSet.elt) list -> ('a, StringSet.t) Hashtbl.t

make [(a1,b1); ...; (an,bn)] construit une relation à partir de la liste de couple en paramètre.

• Exercice: écrire la fonction suivante

val print_rel : (string, StringSet.t) Hashtbl.t -> unit

print_rel r affiche une relation sur la sortie standard sous la forme:

d : [ a; b; ]
a : [ b; ]
b : [ c; ]
c : [ d; ]

Note: utilisez les fonctions Hashtbl.iter, StringSet.iter et Printf.printf.

Relation transitive sans mémoization

Dans un premier temps, nous allons construire la fonction correspondant à notre relation transitive sans mémoization.

L'algorithme est simple: soit (a,b) est dans le noyau de la relation (les couples stockés), soit il existe un c tel que (a,c) est dans le noyau (c appartient aux successeurs de a) et (c,b) appartient à la relation.

On a une simple définition récursive, il suffit de traduire tout ça en OCaml. Pour ça, nous avons à notre disposition les opérations suivantes: StringSet.mem x s (vrai si x appartient à s), StringSet.exists f s (renvoie vrai s'il existe un élément x de s, tel que f x renvoie vrai.)

L'algorithme le plus approprié ici correspondra à une forme de parcours en profondeur (notre relation est en fait un graphe !), nous choisirons la profondeur (qui peut également être vu comme un algorithme avec backtracking) car c'est l'algorithme qui nous permettra de stocker le plus de résultats intermédiaires dans la version avec mémoization (et donc celui qui sera, à terme, le plus performant.)

Attention, dans ce type de parcours (nous sommes pas dans un arbre) il faut faire attention aux circuits: en effet, prennons le noyau de relation suivante {(a,b);(b,c);(c,d);(c,b)} si on le parcours comme un simple arbre, on va partir en boucle infini entre b et c. Pour pallier à ce problème, il nous faut marquer les valeurs déjà rencontrées. Pour ça, nous auront besoin d'un autre ensemble.

Au final, l'algorithme ressemble à:

is_in a b r:

• renvoie vrai si b est dans get_succ a r
• sinon: on parcours l'ensemble des successeurs c de a:
  • si c est marqué on continue sur le suivant
  • sinon, on marque c, et on teste si is_in c b r, si c'est le cas on renvoie vrai, sinon on continue sur le suivant.

Pour garder les éléments marqués, on utilisera un ensemble du module StringSet et pour continuer sur le suivant si le résultat est faux, on s'appuiera sur la fonction StringSet.exists.

• Exercice: écrire la fonction suivante:

val is_in :
  StringSet.elt ->
  StringSet.elt -> (StringSet.elt, StringSet.t) Hashtbl.t -> bool

is_in a b r renvoie vrai si (a,b) est dans la relation transitive dont le noyau est r.

Avec mémoization

On va maintenant modifier (enfin, réécrire, pour pouvoir les comparer) la fonction qui teste l'appartenance à la relation. Mais cette fois-ci, on va stocker les résultats intermédiaires dans le noyau de la relation. On étendra la relation (avec extend) lorsque:

• is_in a b r renvoie vrai et que b n'est pas successeur de a
• pour toutes les valeurs intermédiaires, c, rencontrées on étendra la relation en ajoutant c aux successeurx de a.

• Exercice: écrire la fonction suivante:

val is_in_memo :
  StringSet.elt ->
  StringSet.elt -> (StringSet.elt, StringSet.t) Hashtbl.t -> bool

Astuce: lorsque l'on veut renvoyer un booléen et faire une action si celui-ci est vrai, on peut se passer de if ... then ... en j

ouant avec l'opérateur &&:

let test_affiche printer f x = f x && (printer x ; true)

si f x renvoie vrai, alors le deuxième membre (qui renvoie toujours vrai) est évalué (et l'affichage a lieu) sinon, l'affichage n'a pas lieu.

Tester !

Pour tester, voici une fonction qui lit dans un channel d'entrée ligne par ligne des couples de string. Le format est simple sur chaque ligne nous avons deux string séparées par un espace (qui doit être le seul espace de la ligne.)

let read_pair cin =
  let l = input_line cin in
  let p = String.index l ' ' in
    (String.sub l 0 p, String.sub l (p+1) ((String.length l) - (p+1)))  
 
let rec from_file cin =
  try 
    let p = read_pair cin in p :: from_file cin
  with _ -> []

Vous pouvez utiliser cette fonction sur l'entrée standard (stdin) ou sur un fichier ouvert avec open_in. De plus, la fonction read_pair peut également servir pour lire des paires à tester.

Un exemple de fichier possible en entrée:

a b
a g
b c
c d
d e
f a
g h
h i
i j
j k
b g
k f
e l
l b

Pour finir, regrouper l'ensemble du code et écrivez une fonction main qui construit la relation d'origine via from_file et make et tester quelques couples avec les deux fonctions.

Pour bien voir la différence entre la version avec mémoization et sans, il faut:

• tester plusieurs couples d'affiler
• afficher le nombre de valeurs marquées (le nombre d'élément dans un ensemble est disponible avec StringSet.cardinal)

Normalement, la première recherche sera identique dans les deux cas, après la version avec mémoization devrait tester de moins en moins de valeurs.

Vous pouvez également afficher la relation après la recherche pour voir les éléments ajoutés à chaque fois.

NB: Sujet emprunte a l'EPITA (2010)