Greg's Devblog Par un développeur, pour les développeurs

Algorithme du lièvre et de la tortue

En cours il y a quelques temps un prof nous a demandé si on savait comment détecter des cycles en utilisant un espace mémoire en O(1). Pour illustrer pourquoi on peut avoir envie de ça, imaginons que l'on cherche à trouver 2 valeurs qui vont avoir le même hashé (avec la méthode de votre choix).

On peut alors s'amuser à prendre 1 valeur au hasard, trouver son hashé, et ensuite utiliser cette nouvelle valeur comme valeur de départ, prendre son haché, etc... Là, on est sûr de trouver, au bout d'un temps potentiellement très long, une boucle (ou un cycle), comme sur l'image suivante (prise de wikipedia) :

La façon naïve de faire va être de stocker chacune des valeurs, et de comparer la nouvelle valeur avec toutes les valeurs précédentes. Si on veut éviter d'exploser en temps, on peut utiliser des énormes tables de hash. Sauf que voilà, il faut stocker toutes les valeurs, et on est donc en O(n) pour l'espace mémoire, n étant le nombre de valeurs avant qu'on ne cycle.

Je repose donc la question : comment peut-on effectuer le même traitement en O(1) pour l'espace mémoire ?
Pas forcément intuitive, l'algorithme est au final particulièrement simple et élégant. Il a été défini par Floyd, et on le connait sous le nom d'algorithme du lièvre et de la tortue.

On peut écrire les opérations que l'on fait pour avancer sur la chaine sous la forme a_i+1 = f(a_i), f étant la fonction qu'on utilise (fonction de hash dans l'exemple que j'ai donné). Mais au lieu d'itérer une seule fois sur la chaine, on va en fait lancer 2 itérations en parallèle :

• La tortue avance lentement, donc à chaque itération elle fait a_i+1 = f(a_i)
• Le lièvre est très rapide, il va donc avancer 2 par 2, avec b_i+1 = f(f(b₁))

De façon évidente, le lièvre va arriver dans le cycle avant la tortue, et va se retrouver à tourner dedans en attendant que la tortue n'arrive... Une fois que la tortue est dans le cycle, on a la garantie qu'elle va arriver à la même valeur que le lièvre au bout d'un temps donné, puisque qu'en fait le lièvre rattrape la tortue d'1 étape à chaque itération. Quel que soit l'écart entre les 2, une fois que la tortue arrive dans le cycle le lièvre sera sur le même noeud en au plus L itérations (L étant la taille du cycle).

Et du coup, on n'a besoin d'aucune mémoire supplémentaire pour savoir où est le cycle !
Le pseudo-code, pris de wikipedia, est le suivant :
mu := 0;
répéter
  mu := mu+1;
  x := f(x);
  y := f(f(y));
tant que x <> y
On peut difficilement faire plus simple...

Le seul défaut de cette méthode est la complexité : on reste en O(n), mais on va tout de même appeler 3*n fois la fonction f. Mais cette constante reste relativement faible par rapport au gain en mémoire (on passe de O(n) à O(1)...).

Plus d'informations sur wikipedia