Python: set o list per cercare? `in` da 1 ms a 0,00006 ms

x in lista scorre la lista elemento per elemento (O(n)). x in insieme calcola un hash e salta al punto giusto (O(1) in media). Con pochi elementi non si nota; con molti sì.

Le misure

lista = list(range(100_000))
insieme = set(lista)
chiavi = dict.fromkeys(lista)
ultimo = 99_999          # caso peggiore per la lista

Python 3.12.15, miglior tempo su 5 serie da 200 ricerche:

• ultimo in lista: circa 974 µs
• ultimo in insieme: circa 0,06 µs
• ultimo in chiavi (dict): circa 0,06 µs

Il set è circa 16.000 volte più veloce in questo caso. Il prezzo è la memoria: sys.getsizeof dà circa 781 KiB per la lista e 4096 KiB per il set (la lista contiene solo puntatori, il set anche la tabella hash).

Intersezioni: la trappola del set nel ciclo

Voglio gli elementi di a (5.000) presenti in b (5.000, con metà in comune):

[x for x in a if x in b]          # b è una lista: ~151 ms
[x for x in a if x in set(b)]     # set ricreato a ogni giro: ~411 ms (peggio!)
sb = set(b)
[x for x in a if x in sb]         # set creato una volta: ~0,17 ms
set(a) & sb                       # operatore: ~0,19 ms

Convertire in set dentro la condizione ricostruisce il set a ogni iterazione: è più lento della lista. Il set va creato una volta, fuori dal ciclo.

Quando la lista resta la scelta giusta

• Pochi elementi (decine): la differenza è trascurabile e la lista è più semplice.
• Serve l'ordine o i duplicati, o l'indicizzazione (lista[3]): il set non li offre.
• Gli elementi devono essere hashable: nel set non entrano liste o dict, solo tipi immutabili (numeri, stringhe, tuple di immutabili).
• Una sola ricerca: costruire il set costa O(n), come la scansione. Conviene solo se cerchi più volte.

Deduplicare mantenendo l'ordine

list(set(x)) toglie i duplicati ma non garantisce l'ordine. Dai dizionari (che ricordano l'ordine di inserimento) arriva il trucco:

list(dict.fromkeys([3, 1, 3, 2, 1]))   # [3, 1, 2]

Attenzione: l'ordine con cui un set stampa i suoi elementi non va mai considerato affidabile, anche se con piccoli interi sembra ordinato.

Regola pratica

Se fai in ripetuto su una collezione grande che non cambia, usa un set (o un dict se ti servono anche i valori). Crealo una volta, fuori dal ciclo.

Codice di verifica: verifica/set_vs_list.py nel sorgente del sito.