Dizionari

La seconda struttura dati Python è il dizionario.

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)\).

Tabella 3: Efficienza delle Operazioni sui Dizionari
operation Big-O Efficiency
copy O(n)
get item O(1)
set item O(1)
delete item O(1)
contains (in) O(1)
iteration 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.

../_images/listvdict.png

Figura 4: Comparing the in Operator for Python Lists and Dictionaries

Aggiornamenti o approfondimenti possono essere consultati su Time Complexity Wiki.

Next Section - Esercizi