Un tableau de de noms, et un dictionnaire des mêmes noms

L'estimation, avant toute mesure. Dans un tableau, une recherche infructueuse parcourt les $n$ cases, une recherche fructueuse en parcourt $n/2$ en moyenne : $10000$ recherches dans $1000000$ de noms, c'est de l'ordre de $5\times 10^9$ comparaisons. Dans un dictionnaire, chaque recherche calcule une position et compare une poignée de clés : le total reste de l'ordre de $10000$ opérations. Le rapport attendu n'est pas un facteur deux ou dix — il est de l'ordre de $n/2$, soit cinq cent mille.

import time, random

def mesurer_recherches(n, essais):
    noms = ["nom%d" % i for i in range(n)]
    annuaire = {nom: i for i, nom in enumerate(noms)}
    cibles = [random.choice(noms) for _ in range(essais)]

    t0 = time.perf_counter()
    for c in cibles:
        c in annuaire
    t_dict = time.perf_counter() - t0

    t0 = time.perf_counter()
    for c in cibles:
        c in noms
    t_tab = time.perf_counter() - t0
    return t_dict, t_tab

La mesure. Sur $2000$ recherches (la version à $10000$ dans un million de noms demande plusieurs minutes côté tableau — c'est déjà un résultat) :

Ce que dit la colonne du milieu, et c'est là l'essentiel. Quand $n$ est multiplié par $100$, le temps du tableau est multiplié par $100$ — il suit la taille. Le temps du dictionnaire ne bouge pas : mesuré, il varie d'un facteur $2$ d'une exécution à l'autre — autant dire du bruit, quand le tableau, lui, est exactement cent fois plus lent. Ce n'est pas « le dictionnaire est plus rapide », c'est « le dictionnaire ne ralentit pas ». Sur dix millions d'entrées, le tableau serait cent fois plus lent encore, et le dictionnaire toujours au même prix.

Une précaution de mesure. Les cibles sont tirées avant les deux boucles et réutilisées telles quelles : sans cela on comparerait deux jeux de recherches différents, et un tirage plus favorable au tableau fausserait tout. Mesurer, c'est d'abord s'assurer qu'on mesure la même chose deux fois.