collections - Tipi di dato contenitore

Scopo Tipi di dato contenitore
Versione Python 2.4 e superiore

Il modulo collections include tipi di dato contenitore oltre ai tipi builtin list e dict.

Counter

Counter è un contenitore che tiene traccia di quante volte vengono aggiunti valori equivalenti. Può essere usato per implementare gli stessi algoritmi per i quali vengono comunemente usate in altri linguaggi le strutture dati multiset e bag

Inizializzazione

Counter supporta tre forme di inizializzazione. Il suo costruttore può essere chiamato con una sequenza di elementi, un dizionario contenente chiavi e conteggi, oppure usando argomenti keyword che mappano nomi stringa a conteggi.

import collections

print collections.Counter(['a', 'b', 'c', 'a', 'b', 'b'])
print collections.Counter({'a':2, 'b':3, 'c':1})
print collections.Counter(a=2, b=3, c=1)

Il risultato di tutte e tre le forme di inizializzazione è il medesimo.

$ python collections_counter_init.py

Counter({'b': 3, 'a': 2, 'c': 1})
Counter({'b': 3, 'a': 2, 'c': 1})
Counter({'b': 3, 'a': 2, 'c': 1})

Un Counter vuoto può essere costruito senza argomenti e popolato tramite il metodo update()

import collections

c = collections.Counter()
print 'Iniziale  :', c

c.update('abcdaab')
print 'Sequenza  :', c

c.update({'a':1, 'd':5})
print 'Dizionario:', c

Invece che essere sostituiti, i valori del contatore sono incrementati in base ai nuovi dati. In questo esempio il contatore per a passa da 3 a 4

$ python collections_counter_update.py

Iniziale  : Counter()
Sequenza  : Counter({'a': 3, 'b': 2, 'c': 1, 'd': 1})
Dizionario: Counter({'d': 6, 'a': 4, 'b': 2, 'c': 1})

Accedere ai Contatori

Una volta che un Counter viene popolato, i suoi valori possono essere recuperati usando l'API dei dizionari.

import collections

c = collections.Counter('abcdaab')

for letter in 'abcde':
    print '%s : %d' % (letter, c[letter])

Counter non solleva una eccezione KeyError in caso di chiavi non presenti. Se un valore non è stato passato in entrata (come la e in questo esempio) il suo contatore sarà 0.

$ python collections_counter_get_values.py

a : 3
b : 2
c : 1
d : 1
e : 0

Il metodo elements() ritorna un iteratore che fornisce tutti gli elementi noti a Counter.

import collections

c = collections.Counter('estramamente')
c['z'] = 0
print c
print list(c.elements())

L'ordine degli elementi non è garantito, e gli elementi con contatore minore di zero non sono inclusi

$ python collections_counter_elements.py

Counter({'e': 3, 'a': 2, 'm': 2, 't': 2, 'n': 1, 's': 1, 'r': 1, 'z': 0})
['a', 'a', 'e', 'e', 'e', 'm', 'm', 'n', 's', 'r', 't', 't']

Si usi most_common() per produrre una sequenza dei n valori di input presenti più frequentemente e dei loro rispettivi contatori.

import collections

c = collections.Counter()
with open('/usr/share/dict/words', 'rt') as f:
    for line in f:
        c.update(line.rstrip().lower())

print 'Più comuni:'
for letter, count in c.most_common(3):
    print '%s: %7d' % (letter, count)

In questo esempio si contano le lettere che appaiono in tutte le parole del dizionario di sistema (per i sistemi operativi Unix ed OS-X - n.d.t.) per generare una distribuzione di frequenza, quindi vengono stampate le tre lettere più comuni. Tralasciando l'argomento per most_common(), viene generata una lista di tutti gli elementi, in ordine di frequenza.

$ python collections_counter_most_common.py

Più comuni:
s:   90113
e:   88833
i:   66986

Aritmetica

Le istanze di Counter supportano l'aritmetica e le operazioni sugli insiemi per l'aggregazione dei risultati.

import collections

c1 = collections.Counter(['a', 'b', 'c', 'a', 'b', 'b'])
c2 = collections.Counter('alfabeto')

print 'C1:', c1
print 'C2:', c2

print '\nContatori combinati:'
print c1 + c2

print '\nSottrazione:'
print c1 - c2

print '\nIntersezione (considerando i minimi positivi):'
print c1 & c2

print '\nUnione (considerando i massimi):'
print c1 | c2

Ogni volta che viene prodotto un nuovo Counter tramite una operazione, vengono tralasciati tutti gli elementi con contatore a zero e negativo. Il contatore per a è lo stesso in c1 e c2, quindi la sottrazione lo porta a zero

$ python collections_counter_arithmetic.py

C1: Counter({'b': 3, 'a': 2, 'c': 1})
C2: Counter({'a': 2, 'b': 1, 'e': 1, 'f': 1, 'l': 1, 'o': 1, 't': 1})

Contatori combinati:
Counter({'a': 4, 'b': 4, 'c': 1, 'e': 1, 'f': 1, 'l': 1, 'o': 1, 't': 1})

Sottrazione:
Counter({'b': 2, 'c': 1})

Intersezione (considerando i minimi positivi):
Counter({'a': 2, 'b': 1})

Unione (considerando i massimi):
Counter({'b': 3, 'a': 2, 'c': 1, 'e': 1, 'f': 1, 'l': 1, 'o': 1, 't': 1})

defaultdict

Il dictionary standard include il metodo setdefault() per recuperare un valore ed impostare un valore predefinito se detto valore non esiste. Di contro, defaultdict consente al chiamante di specificare in anticipo il valore predefinito, quando il contenitore viene inizializzato .

import collections

def default_factory():
    return 'valore predefinito'

d = collections.defaultdict(default_factory, foo='bar')
print d
print d['foo']
print d['bar']

La cosa funziona bene fintanto che è appropriato che tutte le chiavi usino lo stesso valore predefinito. Può essere particolarmente utile se il valore predefinito è un tipo usato per aggregare od accumulare valori, tipo list, set, od anche interi. La documentazione della libreria standard comprende diversi esempi per l'uso di defaultdict in questo modo.

$ python collections_defaultdict.py

d: defaultdict(, {'foo': 'bar'})
foo => bar
bar => valore predefinito

Deque

Una coda ad accesso da entrambe le estremità, o deque, consente l'aggiunta e la rimozione di elementi da entrambe le estremità. I più comunemente usati stack e queue sono forme degeneri di deque, dove input ed output viene ristretto ad un solo estremo.

import collections

d = collections.deque('abcdefg')
print 'Deque:', d
print 'Lunghezza:', len(d)
print 'Estremo sx:', d[0]
print 'Estremo dx:', d[-1]

d.remove('c')
print 'rimuovo(c):', d

Visto che le deque sono un tipo di contenitore di sequenze, supportano alcune delle operazioni che supportano le liste, come ad esempio l'esaminare il contenuto con __getitem__(), il determinare la lunghezza, e la rimozione di elementi all'interno confrontandone l'identità .

$ python collections_deque.py
Deque: deque(['a', 'b', 'c', 'd', 'e', 'f', 'g'])
Lunghezza: 7
Estremo sx: a
Estremo dx: g
rimuovo(c): deque(['a', 'b', 'd', 'e', 'f', 'g'])

Inserimento

Una deque può essere incrementata da entrambi gli estremi, detti 'left' (sinistra) e 'right' (destra) nell'implementazione di Python.

import collections

# Aggiungo da destra
d = collections.deque()
d.extend('abcdefg')
print 'extend    :', d
d.append('h')
print 'append    :', d

# Aggiungo da sinistra
d = collections.deque()
d.extendleft('abcdefg')
print 'extendleft:', d
d.appendleft('h')
print 'appendleft:', d

Si noti che extendleft() itera attraverso il suo input ed esegue l'equivalente di un appendleft() per ogni elemento. Il risultato finale è che la deque contiene la sequenza di input in ordine inverso.

$ python collections_deque_populating.py
extend    : deque(['a', 'b', 'c', 'd', 'e', 'f', 'g'])
append    : deque(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'])
extendleft: deque(['g', 'f', 'e', 'd', 'c', 'b', 'a'])
appendleft: deque(['h', 'g', 'f', 'e', 'd', 'c', 'b', 'a'])

Estrazione

Allo stesso modo, gli elementi della deque possono essere estratti da entrambi o da uno degli estremi, a seconda dell'algoritmo che si sta applicando.

import collections

print 'Da destra  :'
d = collections.deque('abcdefg')
while True:
    try:
        print d.pop()
    except IndexError:
        break

print 'Da sinistra:'
d = collections.deque('abcdefg')
while True:
    try:
        print d.popleft()
    except IndexError:
        break

Si usi pop() per rimuovere un elemento dall'estremità destra della deque e popleft() per estrarlo dall'estremità sinistra.

$ python collections_deque_consuming.py
Da destra  :
g
f
e
d
c
b
a
Da sinistra:
a
b
c
d
e
f
g

Visto che le deque sono thread-safe se ne possono estrarre i contenuti da entrambi gli estremi allo stesso tempo in thread separati.

import collections
import threading
import time

candle = collections.deque(xrange(11))

def burn(direction, nextSource):
    while True:
        try:
            next = nextSource()
        except IndexError:
            break
        else:
            print '%8s: %s' % (direction, next)
            time.sleep(0.1)
    print '%8s fatto' % direction
    return

left = threading.Thread(target=burn, args=('Sinistra', candle.popleft))
right = threading.Thread(target=burn, args=('Destra', candle.pop))

left.start()
right.start()

left.join()
right.join()

I thread in questo esempio lavorano su di una estremità, estraendo elementi fino a che deque non si esaurisce.

$ python collections_deque_both_ends.py
    Sinistra: 0
   Destra: 10
    Sinistra: 1
   Destra: 9
    Sinistra: 2
   Destra: 8
    Sinistra: 3
   Destra: 7
    Sinistra: 4
   Destra: 6
    Sinistra: 5
   Destra fatto
    Sinistra fatto

Rotazione

Un'altra utile capacità di deque è di ruotare in entrambe le direzioni, per saltare qualche elemento.

import collections

d = collections.deque(xrange(10))
print 'Normale           :', d
d = collections.deque(xrange(10))
d.rotate(2)
print 'Rotazione destra  :', d
d = collections.deque(xrange(10))
d.rotate(-2)
print 'Rotazione sinistra :', d

Ruotando deque verso destra (usando una rotazione positiva) si prendono gli elementi dall'estremità destra e si spostano verso l'estremità sinistra. Ruotando verso sinistra (con un valore negativo) si prendono gli elementi dall'estremità sinistra e si spostano verso l'estremità destra. Potrebbe essere d'aiuto immaginare gli elementi nella deque come se fossero incisi lungo il margine di un disco di selezione dei numeri di un vecchio telefono.

$ python collections_deque_rotate.py
Normale            : deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
Rotazione destra   : deque([8, 9, 0, 1, 2, 3, 4, 5, 6, 7])
Rotazione sinistra : deque([2, 3, 4, 5, 6, 7, 8, 9, 0, 1])

namedtuple

La tuple standard usa indici numerici per accedere ai propri membri.

bob = ('Bob', 30, 'maschio')
print 'Rappresentazione:', bob

jane = ('Jane', 29, 'femmina')
print '\nCampo riferito da indice:', jane[0]

print '\nCampi riferiti da indice:'
for p in [ bob, jane ]:
    print '%s ha %d anni, %s' % p

Il che rende le tuple efficaci contenitori per semplici utilizzi.

$ python collections_tuple.py

Rappresentazione: ('Bob', 30, 'maschio')

Campo riferito da indice: Jane

Campi riferiti da indice:
Bob ha 30 anni, maschio
Jane ha 29 anni, femmina

D'altro canto, ricordare quale indice dovrebbe essere usato per ciascun valore potrebbe portare ad errori, specialmente se la tuple ha molti campi ed è costruita in una parte del codice molto lontana da quella in cui viene usata. namedtuple assegna nomi, assieme ad indici numerici, ad ogni membro.

Definizione

Le istanze di namedtuple hanno la stessa efficienza rispetto all'uso della memoria rispetto alle normali tuple visto che non hanno dizionari costruiti per ogni istanza. Ciascun tipo di namedtuple viene rappresentato dalla sua propria classe, creata dalla funzione di factory di namedtuple. Gli argomenti sono il nome della nuova classe ed una stringa che contiene i nomi degli element.

import collections

Persona = collections.namedtuple('Persona', 'nome anni genere')

print 'Tipo di Persona:', type(Persona)

bob = Persona(nome='Bob', anni=30, genere='maschio')
print 'Rappresentazione:', bob

jane = Persona(nome='Jane', anni=29, genere='femmina')
print '\nCampo riferito da indice:', jane.nome

print '\nCampi riferiti da indice:'
for p in [ bob, jane ]:
    print '%s ha %d anni, %s' % p

Come illustrato dall'esempio, è possibile accedere ai campi della namedtuple sia usando la notazione con punto (oggetto.attributo) che utilizzando gli indici posizionali delle tuple standard.

$ python collections_named_tuple_person.py
Tipo di Persona: 

Rappresentazione: Persona(nome='Bob', anni=30, genere='maschio')

Campo riferito da indice: Jane

Campi riferiti da indice:
Bob ha 30 anni, maschio
Jane ha 29 anni, femmina

Nomi di Campo non Validi

Durante l'elaborazione dei nomi, dei valori non validi causano eccezioni ValueError.

import collections

try:
    collections.namedtuple('Persona', 'nome class anni genere')
except ValueError, err:
    print err

try:
    collections.namedtuple('Person', 'nome anni genere anni')
except ValueError, err:
    print err

I nomi non sono validi se sono ripetuti o sono in conflitto con parole riservate del linguaggio.

$ python collections_namedtuple_bad_fields.py

Type names and field names cannot be a keyword: 'class'
Encountered duplicate field name: 'anni'

In situazioni dove una namedtuple viene creata in base a valori al di fuori del controllo del programma (tipo la rappresentazione delle righe ritornate da una ricerca in un database, dove lo schema non è noto in anticipo), si imposti l'opzione rename a True in modo che i campi vengano rinominati.

import collections

with_class = collections.namedtuple('Persona', 'nome class anni genere', rename=True)
print with_class._fields

two_ages = collections.namedtuple('Persona', 'nome anni genere anni', rename=True)
print two_ages._fields

Il campo chiamato class diventa _1 ed il campo duplicato anni diventa _3.

$ python collections_namedtuple_rename.py

('nome', '_1', 'anni', 'genere')
('nome', 'classe', 'genere', 'anni')

OrderedDict

Un OrderedDict è una classe derivata da dictionary che ricorda l'ordine nel quale viene aggiunto il suo contenuto.

import collections

print 'Dizionario normale:'
d = {}
d['a'] = 'A'
d['b'] = 'B'
d['c'] = 'C'
d['d'] = 'D'
d['e'] = 'E'

for k, v in d.items():
    print k, v

print '\nDiz. ordinato (OrderedDict):'
d = collections.OrderedDict()
d['a'] = 'A'
d['b'] = 'B'
d['c'] = 'C'
d['d'] = 'D'
d['e'] = 'E'

for k, v in d.items():
    print k, v

Un dizionario normale (dict) non tiene traccia dell'ordine di inserimento, e la sua iterazione produce valori in ordine arbitrario. In un dizionario ordinato OrderedDict, al contrario, l'ordine in cui gli elementi vengono inseriti viene conservato ed usato quando viene creato un iteratore.

$ python collections_ordereddict_iter.py

Dizionario normale:
a A
c C
b B
e E
d D

Diz. ordinato (OrderedDict):
a A
b B
c C
d D
e E

Uguaglianza

Un dizionario normale cerca all'interno del suo contenuto verificando una uguaglianza. Un dizionario ordinato OrderedDict considera anche l'ordine nel quale sono stati aggiunti gli elementi.

import collections

print 'dict       :',
d1 = {}
d1['a'] = 'A'
d1['b'] = 'B'
d1['c'] = 'C'
d1['d'] = 'D'
d1['e'] = 'E'

d2 = {}
d2['e'] = 'E'
d2['d'] = 'D'
d2['c'] = 'C'
d2['b'] = 'B'
d2['a'] = 'A'

print d1 == d2

print 'OrderedDict:',

d1 = collections.OrderedDict()
d1['a'] = 'A'
d1['b'] = 'B'
d1['c'] = 'C'
d1['d'] = 'D'
d1['e'] = 'E'

d2 = collections.OrderedDict()
d2['e'] = 'E'
d2['d'] = 'D'
d2['c'] = 'C'
d2['b'] = 'B'
d2['a'] = 'A'

print d1 == d2

In questo caso, visto che i dizionari ordinati sono stati creati da valori in diverso ordine, sono considerati diversi.

$ python collections_ordereddict_equality.py

dict       : True
OrderedDict: False

Vedere anche:

collezioni
La documentazione della libreria standard per questo modulo.
WikiPedia: Deque
Una discussione sulla struttura dati della deque.
Ricette di Deque
Esempi dell'uso di deque in algoritmi dalla documentazione della libreria standard.
esempi di defaultdict
Esempi dell'uso di defaultdict dalla documentazione della libreria standard
James Tauber: Evoluzione dei dizionari predefiniti in Python
Discussione su come defaultdict si confronta con altri metodi di inizializzazione di dizionari.