Je me suis souvent posé la question de savoir si une list ou une tuple était préférable pour vérifier la présence d'un élément dans une séquence.
En fin de compte, voici quelques benchmarks qui aideront à aiguiller mes (vos ?) prochains choix.

Les tests se dérouleront sur Python 3.6.5, les résultats exprimés en secondes et le module timeit sera nécessaire :

from timeit import repeat

Chaque benchmark retournera un dictionnaire des résultats et je me servirai de cette fonction pour trier et formater l'affichage :

def display(results):
    print('\nRésultats :')
    longest = len(max(results, key=len))

    best = None
    for benchmark in sorted(results, key=results.get):
        score = results[benchmark]
        line = f'{benchmark:.<{longest}} {score:.6f}'
        if best is None:
            best = score
        else:
            coef = score / best
            line += f' x{coef:.2f}'.rjust(8)
        print(line)

Test 1

Simulation d'une recherche d'un élément dans une séquence définie en amont dans le code.

benchmarks = {
    'list': 'seq = list(range(1000))',
    'tuple': 'seq = tuple(range(1000))',
    'set': 'seq = set(range(1000))',
    'iterator': 'seq = range(1000)',
    'frozenset': 'seq = frozenset(range(1000))',
    'dict': 'seq = {n: None for n in range(1000)}',
}

Lorsque l'élément est trouvé dans la séquence :

>>> def bench(setup):
....    return repeat('999 in seq', setup, number=100000)[1]

>>> results = {nature: bench(setup) for nature, setup in benchmarks.items()}
>>> display(results)

Résultats :
frozenset 0.003175
set...... 0.003211   x1.01
dict..... 0.003798   x1.20
iterator. 0.006976   x2.20
tuple.... 0.956433 x301.21
list..... 1.116894 x351.74

Et lorsque l'élément n'est pas trouvé dans la séquence :

>>> def bench(setup):
....    return repeat('1001 in seq', setup, number=100000)[1]

>>> results = {nature: bench(setup) for nature, setup in benchmarks.items()}
>>> display(results)

Résultats :
set...... 0.002064
frozenset 0.002110   x1.02
dict..... 0.002311   x1.12
iterator. 0.004139   x2.01
tuple.... 0.912069 x441.85
list..... 0.923535 x447.41

Constations :

  • set et frozenset se valent.
  • dict garde la tête haute.
  • list et tuple sont à la ramasse.

Test 2

Simulation d'une recherche d'un élément dans une séquence définie dans la condition.

benchmarks = {
    'list': '"zorro" in ["alice", "bob"]',
    'tuple': '"zorro" in ("alice", "bob")',
    'set': '"zorro" in {"alice", "bob"}',
    'set(list)': '"zorro" in set(["alice", "bob"])',
    'set(tuple)': '"zorro" in set(("alice", "bob"))',
    'frozenset(list)': '"zorro" in frozenset(["alice", "bob"])',
    'frozenset(tuple)': '"zorro" in frozenset(("alice", "bob"))',
    'frozenset(set)': '"zorro" in frozenset({"alice", "bob"})',
    'dict': '"zorro" in {"alice": None, "bob": None}',
}

>>> def bench(test):
....    return repeat(test, number=100000)[1]

>>> results = {nature: bench(setup) for nature, setup in benchmarks.items()}
>>> display(results)

Résultats :
set............. 0.001947
tuple........... 0.004413   x2.27
list............ 0.004745   x2.44
dict............ 0.007554   x3.88
frozenset(tuple) 0.016834   x8.65
set(tuple)...... 0.017246   x8.86
frozenset(set).. 0.018460   x9.48
frozenset(list). 0.020513  x10.54
set(list)....... 0.021509  x11.05

Constation :

  • set explose tout.

Conclusion

set semble être la meilleure solution. En plus de ça, son utilisation est agréable à lire :

if x in {a, b, c}:
    pass

Historique

  • 2018-07-08 : Suppression de l'utilisation de ljust() dans la f-string.