L'ART DE BIEN RANGER

Où l'on va voir que bien ranger des informations peut avoir des conséquences très intéressantes. On envisagera deux méthodes de rangement.

séquentiellement dans une file

On range séquentiellement 16 nombres aléatoires (par exemple de 0 à 15) au fur et à mesure de leur arrivée (la ligne basse de la figure 1). On cherche ensuite à localiser un de ces nombres pris au hasard. Pour cela, on teste le premier nombre de la file, si c'est le bon on a terminé, sinon on passe au suivant. Dans le pire des cas ce sera le dernier et on aura réalisé 16 tests ; en moyenne, il en faudra 8 (16/2).

dans un arbre binaire

On les range maintenant dans une structure d'arbre binaire (le triangle de la figure 1), en mémorisant à chaque embranchement d'un sous-arbre son intervalle de définition. Ce travail coute plus cher que le premier, mais localiser un nombre reviendra ensuite à tester l'appartenance à l'intervalle noté à chaque embranchement et prendre le bon chemin jusqu'au noeud terminal. Il y aura 4 tests à faire, soit la moitié de la technique précédente, ce qui est bien.

figure 1.

conséquences

On aura remarqué que 16 = 2⁴ et l'on devine que la règle générale reliant le nombre n de tests au nombre N de nombres est : N = 2ⁿ. Si l'on imagine maintenant que l'on a 2³² = 4 294 967 296, soit 4 milliards de nombres, il faudra réaliser en moyenne 2 milliards (2 147 483 648) tests avec la première méthode, et simplement ... 32 avec le seconde. C'est là l'un des avantages du rangement dans une structure d'arbre binaire.

Et c'est la raison de l'incroyable rapidité avec laquelle une adresse internet est trouvée parmi les 4 milliards distribuées (elles sont codées sur 32 bits, donc on peut en définir 2³²), ou le nombre d'occurences d'un môt est trouvé par un moteur de recherche comme celui de Google. Les robots de Google passent leur temps à scanner tous les fichiers accessibles sur internet et rangent les informations trouvées dans une structure qui ressemble à un énorme arbre binaire.

Demain, le codage des adresses internet se fera sur 64 bits ou même sur 128 bits, et on pourra adresser (virtuellement) 2⁶⁴ et 2¹²⁸, soit tous les grains de l'univers...

... à suivre. am_20051204