Dizionari¶

La seconda struttura dati Python è il dizionario.

• Nei dizionari, accediamo agli elementi della collezione tramite una chiave invece che con la posizione.
• Ottenere un valore o invocare get o modificare/aggiungere un valore con il set costa \(O(1)\).
• Controllare se una chiave è nel dizionario costa \(O(1)\).

L’efficienza di tutte le operazioni è mostrata in Tabella 3. La complessità riportate si riferisce al caso medio. In rari casi, le operazioni get, set possono costare \(O(n)\).

Di seguito, confermiamo sperimentalmente che il metodo contains per controllare se un elemento è nella collezione per le liste costa \(O(n)\) mentre per i dizionari costa \(O(1)\). Nel caso del dizionario, i valori della collezione sono le chiavi.

Il codice seguente implementa il confronto.

Listing 6

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import timeit
import random

for i in range(10000,1000001,20000):
    t = timeit.Timer("random.randrange(%d) in x"%i,
                     "from __main__ import random,x")
    x = list(range(i))
    lst_time = t.timeit(number=1000)
    x = {j:None for j in range(i)}
    d_time = t.timeit(number=1000)
    print("%d,%10.3f,%10.3f" % (i, lst_time, d_time))

Figura 4 riassume il risultato.

Figura 4: Confronto per l’operatore in nelle liste e nei dizionari

Aggiornamenti o approfondimenti possono essere consultati su Time Complexity Wiki.