5. Strutture Dati

Questo capitolo descrive alcune cose che hai già imparato in maggiore dettaglio, e aggiunge anche alcune nuove cose.

5.1. Più sulle Liste

Il tipo di dato lista ha alcuni metodi aggiuntivi. Ecco tutti i metodi degli oggetti lista:

list.append(x)

Add an item to the end of the list. Similar to a[len(a):] = [x].

list.extend(iterable)

Extend the list by appending all the items from the iterable. Similar to a[len(a):] = iterable.

list.insert(i, x)

Inserisce un elemento in una posizione specificata. Il primo argomento è l’indice dell’elemento prima del quale inserire, quindi a.insert(0, x) inserisce all’inizio della lista, e a.insert(len(a), x) è equivalente a a.append(x).

list.remove(x)

Rimuove il primo elemento dalla lista il cui valore è uguale a x. Solleva una ValueError se non c’è un tale elemento.

list.pop([i])

Rimuove l’elemento nella posizione specificata nella lista e lo restituisce. Se non viene specificato un indice, a.pop() rimuove e restituisce l’ultimo elemento della lista. Solleva un IndexError se la lista è vuota o l’indice è fuori dal range della lista.

list.clear()

Remove all items from the list. Similar to del a[:].

list.index(x[, start[, end]])

Restituisce l’indice zero-based del primo elemento nella lista il cui valore è uguale a x. Solleva una ValueError se non c’è un tale elemento.

Gli argomenti opzionali start e end sono interpretati come nella notazione delle slice e sono usati per limitare la ricerca a una particolare sottosequenza della lista. L’indice restituito è calcolato rispetto all’inizio della sequenza completa piuttosto che all’argomento start.

list.count(x)

Restituisce il numero di volte che x appare nella lista.

list.sort(*, key=None, reverse=False)

Ordina gli elementi della lista in loco (gli argomenti possono essere usati per la personalizzazione dell’ordinamento, vedere sorted() per la loro spiegazione).

list.reverse()

Inverte gli elementi della lista in loco.

list.copy()

Return a shallow copy of the list. Similar to a[:].

Un esempio che utilizza la maggior parte dei metodi della lista:

>>> fruits = ['orange', 'apple', 'pear', 'banana', 'kiwi', 'apple', 'banana']
>>> fruits.count('apple')
2
>>> fruits.count('tangerine')
0
>>> fruits.index('banana')
3
>>> fruits.index('banana', 4)  # Find next banana starting at position 4
6
>>> fruits.reverse()
>>> fruits
['banana', 'apple', 'kiwi', 'banana', 'pear', 'apple', 'orange']
>>> fruits.append('grape')
>>> fruits
['banana', 'apple', 'kiwi', 'banana', 'pear', 'apple', 'orange', 'grape']
>>> fruits.sort()
>>> fruits
['apple', 'apple', 'banana', 'banana', 'grape', 'kiwi', 'orange', 'pear']
>>> fruits.pop()
'pear'

Avrai notato che metodi come insert, remove o sort che modificano solo la lista non stampano alcun valore di ritorno – ritornano il default None. [1] Questo è un principio di design per tutte le strutture dati mutabili in Python.

Un’altra cosa che potresti notare è che non tutti i dati possono essere ordinati o confrontati. Per esempio, [None, 'hello', 10] non può essere ordinata perché gli interi non possono essere confrontati con le stringhe e None non può essere confrontato con altri tipi. Inoltre, ci sono alcuni tipi che non hanno una relazione di ordinamento definita. Ad esempio, 3+4j < 5+7j non è un confronto valido.

5.1.1. Usare le Liste come Pile

The list methods make it very easy to use a list as a stack, where the last element added is the first element retrieved («last-in, first-out»). To add an item to the top of the stack, use append(). To retrieve an item from the top of the stack, use pop() without an explicit index. For example:

>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

5.1.2. Usare le Liste come Code

È anche possibile usare una lista come una coda, dove il primo elemento aggiunto è il primo elemento recuperato («first-in, first-out»); tuttavia, le liste non sono efficienti per questo scopo. Mentre gli append e i pop dalla fine della lista sono veloci, fare inserzioni o pop dall’inizio di una lista è lento (perché tutti gli altri elementi devono essere spostati di uno).

Per implementare una coda, usa collections.deque che è stata progettata per avere append e pop veloci da entrambi i lati. Per esempio:

>>> from collections import deque
>>> queue = deque(["Eric", "John", "Michael"])
>>> queue.append("Terry")           # Terry arrives
>>> queue.append("Graham")          # Graham arrives
>>> queue.popleft()                 # The first to arrive now leaves
'Eric'
>>> queue.popleft()                 # The second to arrive now leaves
'John'
>>> queue                           # Remaining queue in order of arrival
deque(['Michael', 'Terry', 'Graham'])

5.1.3. Comprensioni di Lista

Le comprensioni di lista forniscono un modo conciso per creare liste. Le applicazioni comuni sono creare nuove liste dove ogni elemento è il risultato di alcune operazioni applicate a ciascun membro di un’altra sequenza o iterabile, o creare una sottosequenza di quegli elementi che soddisfano una certa condizione.

Per esempio, supponiamo di voler creare una lista di quadrati, come:

>>> squares = []
>>> for x in range(10):
...     squares.append(x**2)
...
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

Nota che questo crea (o sovrascrive) una variabile chiamata x che esiste ancora dopo che il ciclo è completo. Possiamo calcolare la lista dei quadrati senza effetti collaterali usando:

squares = list(map(lambda x: x**2, range(10)))

oppure, equivalentemente:

squares = [x**2 for x in range(10)]

il che è più conciso e leggibile.

Una comprensione di lista consiste di parentesi contenenti un’espressione seguita da una clausola for, quindi zero o più clausole for o if. Il risultato sarà una nuova lista risultante dalla valutazione dell’espressione nel contesto delle clausole for e if che la seguono. Per esempio, questa listcomp combina gli elementi di due liste se non sono uguali:

>>> [(x, y) for x in [1,2,3] for y in [3,1,4] if x != y]
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

e equivale a:

>>> combs = []
>>> for x in [1,2,3]:
...     for y in [3,1,4]:
...         if x != y:
...             combs.append((x, y))
...
>>> combs
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

Nota come l’ordine delle istruzioni for e if sia lo stesso in entrambi questi snippet.

Se l’espressione è una tupla (per es. il (x, y) nell’esempio precedente), deve essere racchiusa tra parentesi.

>>> vec = [-4, -2, 0, 2, 4]
>>> # create a new list with the values doubled
>>> [x*2 for x in vec]
[-8, -4, 0, 4, 8]
>>> # filter the list to exclude negative numbers
>>> [x for x in vec if x >= 0]
[0, 2, 4]
>>> # apply a function to all the elements
>>> [abs(x) for x in vec]
[4, 2, 0, 2, 4]
>>> # call a method on each element
>>> freshfruit = ['  banana', '  loganberry ', 'passion fruit  ']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']
>>> # create a list of 2-tuples like (number, square)
>>> [(x, x**2) for x in range(6)]
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)]
>>> # the tuple must be parenthesized, otherwise an error is raised
>>> [x, x**2 for x in range(6)]
  File "<stdin>", line 1
    [x, x**2 for x in range(6)]
     ^^^^^^^
SyntaxError: did you forget parentheses around the comprehension target?
>>> # flatten a list using a listcomp with two 'for'
>>> vec = [[1,2,3], [4,5,6], [7,8,9]]
>>> [num for elem in vec for num in elem]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Le comprensioni di lista possono contenere espressioni complesse e funzioni nidificate:

>>> from math import pi
>>> [str(round(pi, i)) for i in range(1, 6)]
['3.1', '3.14', '3.142', '3.1416', '3.14159']

5.1.4. Comprensioni di Lista Nidificate

L’espressione iniziale in una comprensione di lista può essere qualsiasi espressione arbitraria, inclusa un’altra comprensione di lista.

Considera il seguente esempio di una matrice 3x4 implementata come una lista di 3 liste di lunghezza 4:

>>> matrix = [
...     [1, 2, 3, 4],
...     [5, 6, 7, 8],
...     [9, 10, 11, 12],
... ]

La seguente comprensione di lista trasporrà righe e colonne:

>>> [[row[i] for row in matrix] for i in range(4)]
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

Come abbiamo visto nella sezione precedente, la comprensione di lista interna è valutata nel contesto del for che la segue, quindi questo esempio è equivalente a:

>>> transposed = []
>>> for i in range(4):
...     transposed.append([row[i] for row in matrix])
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

che, a sua volta, è lo stesso di:

>>> transposed = []
>>> for i in range(4):
...     # the following 3 lines implement the nested listcomp
...     transposed_row = []
...     for row in matrix:
...         transposed_row.append(row[i])
...     transposed.append(transposed_row)
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

Nel mondo reale, dovresti preferire le funzioni built-in a strutture di controllo complesse. La funzione zip() farebbe un ottimo lavoro per questo caso d’uso:

>>> list(zip(*matrix))
[(1, 5, 9), (2, 6, 10), (3, 7, 11), (4, 8, 12)]

Vedi Spacchettamento delle Liste di Argomenti per dettagli sull’asterisco in questa riga.

5.2. L’istruzione del

There is a way to remove an item from a list given its index instead of its value: the del statement. This differs from the pop() method which returns a value. The del statement can also be used to remove slices from a list or clear the entire list (which we did earlier by assignment of an empty list to the slice). For example:

>>> a = [-1, 1, 66.25, 333, 333, 1234.5]
>>> del a[0]
>>> a
[1, 66.25, 333, 333, 1234.5]
>>> del a[2:4]
>>> a
[1, 66.25, 1234.5]
>>> del a[:]
>>> a
[]

del può anche essere usato per cancellare variabili intere:

>>> del a

Fare riferimento al nome a d’ora in poi è un errore (almeno finché un altro valore non viene assegnato ad esso). Troveremo altri usi per del più avanti.

5.3. Tuple e Sequenze

Abbiamo visto che liste e stringhe hanno molte proprietà comuni, come le operazioni di indicizzazione e slicing. Sono due esempi di tipi di dati sequenza (vedi Tipi di Sequenza — list, tuple, range). Poiché Python è un linguaggio in evoluzione, possono essere aggiunti altri tipi di dati sequenza. Esiste anche un altro tipo di dati sequenza standard: la tupla.

Una tupla consiste in un numero di valori separati da virgole, ad esempio:

>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # Tuples may be nested:
>>> u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))
>>> # Tuples are immutable:
>>> t[0] = 88888
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>> # but they can contain mutable objects:
>>> v = ([1, 2, 3], [3, 2, 1])
>>> v
([1, 2, 3], [3, 2, 1])

Come vedi, in uscita le tuple sono sempre racchiuse tra parentesi, in modo che le tuple annidate siano interpretate correttamente; possono essere inserite con o senza parentesi, anche se spesso le parentesi sono comunque necessarie (se la tupla fa parte di un’espressione più grande). Tuttavia, non è possibile assegnare ai singoli elementi di una tupla, mentre è possibile creare tuple che contengono oggetti mutabili, come le liste.

Sebbene le tuple possano sembrare simili alle liste, vengono spesso utilizzate in situazioni diverse e per scopi diversi. Le tuple sono immutable, e di solito contengono una sequenza eterogenea di elementi che sono accessibili tramite unpacking (vedi più avanti in questa sezione) o indicizzazione (o anche per attributo nel caso di namedtuples). Le liste sono mutable, e i loro elementi sono di solito omogenei e sono accessibili iterando sulla lista.

Un problema speciale è la costruzione di tuple contenenti 0 o 1 elemento: la sintassi presenta alcune peculiarità per accogliere questi casi. Le tuple vuote sono costruite da una coppia di parentesi vuota; una tupla con un solo elemento è costruita seguendo un valore con una virgola (non è sufficiente racchiudere un singolo valore tra parentesi). Brutto, ma efficace. Ad esempio:

>>> empty = ()
>>> singleton = 'hello',    # <-- note trailing comma
>>> len(empty)
0
>>> len(singleton)
1
>>> singleton
('hello',)

L’istruzione t = 12345, 54321, 'hello!' è un esempio di tuple packing: i valori 12345, 54321 e 'hello!' sono racchiusi insieme in una tupla. L’operazione inversa è anche possibile:

>>> x, y, z = t

Questo è chiamato, appropriatamente, sequence unpacking e funziona per qualsiasi sequenza sul lato destro. Lo sequence unpacking richiede che ci siano tante variabili sul lato sinistro del segno di uguale quante sono gli elementi nella sequenza. Nota che l’assegnazione multipla è davvero solo una combinazione di tuple packing e sequence unpacking.

5.4. Insiemi

Python include anche un tipo di dato per gli insiemi. Un insieme è una collezione non ordinata senza elementi duplicati. Gli usi principali includono il controllo dell’appartenenza e l’eliminazione degli elementi duplicati. Gli oggetti set supportano anche operazioni matematiche come unione, intersezione, differenza e differenza simmetrica.

Le parentesi graffe o la funzione set() possono essere utilizzate per creare insiemi. Nota: per creare un insieme vuoto devi utilizzare set(), non {}; quest’ultimo crea un dizionario vuoto, una struttura dati che discuteremo nella sezione successiva.

Ecco una breve dimostrazione:

>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
>>> print(basket)                      # show that duplicates have been removed
{'orange', 'banana', 'pear', 'apple'}
>>> 'orange' in basket                 # fast membership testing
True
>>> 'crabgrass' in basket
False

>>> # Demonstrate set operations on unique letters from two words
>>>
>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a                                  # unique letters in a
{'a', 'r', 'b', 'c', 'd'}
>>> a - b                              # letters in a but not in b
{'r', 'd', 'b'}
>>> a | b                              # letters in a or b or both
{'a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'}
>>> a & b                              # letters in both a and b
{'a', 'c'}
>>> a ^ b                              # letters in a or b but not both
{'r', 'd', 'b', 'm', 'z', 'l'}

Analogamente alle list comprehensions, sono supportate anche le set comprehensions:

>>> a = {x for x in 'abracadabra' if x not in 'abc'}
>>> a
{'r', 'd'}

5.5. Dizionari

Another useful data type built into Python is the dictionary (see Tipi di Mapping — dict). Dictionaries are sometimes found in other languages as «associative memories» or «associative arrays». Unlike sequences, which are indexed by a range of numbers, dictionaries are indexed by keys, which can be any immutable type; strings and numbers can always be keys. Tuples can be used as keys if they contain only strings, numbers, or tuples; if a tuple contains any mutable object either directly or indirectly, it cannot be used as a key. You can’t use lists as keys, since lists can be modified in place using index assignments, slice assignments, or methods like append() and extend().

È meglio pensare a un dizionario come a un insieme di coppie chiave: valore, con il requisito che le chiavi siano uniche (all’interno di un dizionario). Una coppia di parentesi crea un dizionario vuoto: {}. Inserendo una lista di coppie chiave:valore separate da virgole dentro le parentesi si aggiungono le coppie iniziali al dizionario; questo è anche il modo in cui i dizionari vengono scritti in uscita.

Le principali operazioni su un dizionario sono memorizzare un valore con una chiave e estrarre il valore data la chiave. È anche possibile eliminare una coppia chiave:valore con del. Se memorizzi usando una chiave già in uso, il vecchio valore associato a quella chiave viene dimenticato. È un errore estrarre un valore usando una chiave inesistente.

Eseguendo list(d) su un dizionario si ottiene una lista di tutte le chiavi utilizzate nel dizionario, in ordine di inserimento (se la vuoi ordinata, basta usare sorted(d)). Per controllare se una singola chiave è nel dizionario, usa la parola chiave in.

Ecco un piccolo esempio usando un dizionario:

>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'jack': 4098, 'sape': 4139, 'guido': 4127}
>>> tel['jack']
4098
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'jack': 4098, 'guido': 4127, 'irv': 4127}
>>> list(tel)
['jack', 'guido', 'irv']
>>> sorted(tel)
['guido', 'irv', 'jack']
>>> 'guido' in tel
True
>>> 'jack' not in tel
False

Il costruttore dict() costruisce dizionari direttamente da sequenze di coppie chiave-valore:

>>> dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])
{'sape': 4139, 'guido': 4127, 'jack': 4098}

Inoltre, le dict comprehensions possono essere utilizzate per creare dizionari da espressioni di chiave e valore arbitrarie:

>>> {x: x**2 for x in (2, 4, 6)}
{2: 4, 4: 16, 6: 36}

Quando le chiavi sono semplici stringhe, a volte è più facile specificare le coppie utilizzando gli argomenti per parola chiave:

>>> dict(sape=4139, guido=4127, jack=4098)
{'sape': 4139, 'guido': 4127, 'jack': 4098}

5.6. Tecniche di Looping

Quando si scorre un dizionario, è possibile recuperare contemporaneamente la chiave e il valore corrispondente usando il metodo items().

>>> knights = {'gallahad': 'the pure', 'robin': 'the brave'}
>>> for k, v in knights.items():
...     print(k, v)
...
gallahad the pure
robin the brave

Quando si scorre una sequenza, è possibile recuperare contemporaneamente l’indice di posizione e il valore corrispondente usando la funzione enumerate().

>>> for i, v in enumerate(['tic', 'tac', 'toe']):
...     print(i, v)
...
0 tic
1 tac
2 toe

Per scorrere due o più sequenze contemporaneamente, le voci possono essere abbinate con la funzione zip().

>>> questions = ['name', 'quest', 'favorite color']
>>> answers = ['lancelot', 'the holy grail', 'blue']
>>> for q, a in zip(questions, answers):
...     print('What is your {0}?  It is {1}.'.format(q, a))
...
What is your name?  It is lancelot.
What is your quest?  It is the holy grail.
What is your favorite color?  It is blue.

Per scorrere una sequenza al contrario, specifica prima la sequenza in direzione avanti e poi chiama la funzione reversed().

>>> for i in reversed(range(1, 10, 2)):
...     print(i)
...
9
7
5
3
1

Per scorrere una sequenza in ordine ordinato, usa la funzione sorted() che restituisce una nuova lista ordinata lasciando invariata la sorgente.

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for i in sorted(basket):
...     print(i)
...
apple
apple
banana
orange
orange
pear

Usare set() su una sequenza elimina gli elementi duplicati. L’uso di sorted() in combinazione con set() su una sequenza è un modo idiomatico di scorrere gli elementi unici della sequenza in ordine ordinato.

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for f in sorted(set(basket)):
...     print(f)
...
apple
banana
orange
pear

A volte è allettante modificare una lista mentre la stai scorrendo; tuttavia, è spesso più semplice e sicuro creare una nuova lista invece.

>>> import math
>>> raw_data = [56.2, float('NaN'), 51.7, 55.3, 52.5, float('NaN'), 47.8]
>>> filtered_data = []
>>> for value in raw_data:
...     if not math.isnan(value):
...         filtered_data.append(value)
...
>>> filtered_data
[56.2, 51.7, 55.3, 52.5, 47.8]

5.7. Maggiori informazioni sulle Condizioni

Le condizioni utilizzate nelle istruzioni while e if possono contenere qualsiasi operatore, non solo confronti.

Gli operatori di confronto in e not in sono test di appartenenza che determinano se un valore è (o non è) in un contenitore. Gli operatori is e is not confrontano se due oggetti sono davvero lo stesso oggetto. Tutti gli operatori di confronto hanno la stessa priorità, che è inferiore a quella di tutti gli operatori numerici.

I confronti possono essere concatenati. Ad esempio, a < b == c verifica se a è minore di b e inoltre se b è uguale a c.

I confronti possono essere combinati usando gli operatori booleani and e or, e il risultato di un confronto (o di qualsiasi altra espressione booleana) può essere negato con not. Questi hanno una priorità inferiore rispetto agli operatori di confronto; tra di loro, not ha la priorità più alta e or la più bassa, in modo che A and not B or C sia equivalente a (A and (not B)) or C. Come sempre, le parentesi possono essere utilizzate per esprimere la composizione desiderata.

Gli operatori booleani and e or sono i cosiddetti operatori short-circuit: i loro argomenti vengono valutati da sinistra a destra, e la valutazione si arresta non appena l’esito è determinato. Ad esempio, se A e C sono veri ma B è falso, A and B and C non valuta l’espressione C. Quando vengono utilizzati come un valore generale e non come booleani, il valore restituito di un operatore short-circuit è l’ultimo argomento valutato.

È possibile assegnare il risultato di un confronto o di un’altra espressione booleana a una variabile. Ad esempio,

>>> string1, string2, string3 = '', 'Trondheim', 'Hammer Dance'
>>> non_null = string1 or string2 or string3
>>> non_null
'Trondheim'

Nota che in Python, a differenza del C, l’assegnazione dentro espressioni deve essere fatta esplicitamente con l’operatore detto walrus operator :=. Questo evita una comune classe di problemi incontrati nei programmi C: digitare = in un’espressione quando si intendeva ==.

5.8. Confronto tra Sequenze e Altri Tipi

Gli oggetti sequenza possono essere tipicamente confrontati con altri oggetti dello stesso tipo di sequenza. Il confronto usa l’ordinamento lessicografico: prima vengono confrontati i primi due elementi, e se differiscono questo determina il risultato del confronto; se sono uguali, vengono confrontati i due successivi, e così via, fino a quando una delle due sequenze è esaurita. Se gli elementi da confrontare sono essi stessi sequenze dello stesso tipo, il confronto lessicografico viene effettuato ricorsivamente. Se tutti gli elementi di due sequenze sono uguali tra di loro, le sequenze sono considerate uguali. Se una sequenza è una sottosequenza iniziale dell’altra, la sequenza più corta è considerata la minore. L’ordinamento lessicografico per le stringhe utilizza il numero del punto di codice Unicode per ordinare i singoli caratteri. Alcuni esempi di confronti tra sequenze dello stesso tipo:

(1, 2, 3)              < (1, 2, 4)
[1, 2, 3]              < [1, 2, 4]
'ABC' < 'C' < 'Pascal' < 'Python'
(1, 2, 3, 4)           < (1, 2, 4)
(1, 2)                 < (1, 2, -1)
(1, 2, 3)             == (1.0, 2.0, 3.0)
(1, 2, ('aa', 'ab'))   < (1, 2, ('abc', 'a'), 4)

Nota che confrontare oggetti di tipi diversi con < o > è legale a condizione che gli oggetti abbiano metodi di confronto appropriati. Ad esempio, i tipi numerici misti sono confrontati in base al loro valore numerico, quindi 0 è uguale a 0.0, ecc. Altrimenti, invece di fornire un ordinamento arbitrario, l’interprete alzerà un’eccezione TypeError.

Note a piè di pagina