Realizzare contenitori su array e liste

Nelle prove pratiche si parte dall'interfaccia di un ADTUn ADT è definito dalle operazioni e dal loro comportamento, non dalla rappresentazione; interfaccia e implementazione; realizzazione in Python con le classi e in C con header e tipo opaco; esempio di un ADT Frazione.Tipi di dato astratti → (pila, coda, dizionario, insieme, coda con priorità) e se ne scrive l'implementazione, spesso con un costo richiesto ("find in $O(\log n)$", "tutte le operazioni in $O(1)$"). Si sceglie la rappresentazione guardando quali operazioni devono essere veloci (Complessità computazionaleCosto di un algoritmo in funzione della dimensione dell'input; caso peggiore, migliore e medio; notazione O-grande e classi di crescita; come contare i passi di cicli e ricorsioni; costo delle operazioni Python.Complessità computazionale →).

Array parzialmente riempito

Un array ha capacità fissa. Si tengono due numeri: la capacità (len(a)) e la lunghezza logica n (quanti posti sono occupati): gli elementi validi sono a[0..n-1]. Quando n == capacità si raddoppia: si crea un array di capacità doppia e si copiano gli elementi.

class Vettore:
    def __init__(self, cap=2):
        self._a = [None] * cap       # array "grezzo" di capacità fissa
        self._n = 0                  # lunghezza logica

    def append(self, x):
        if self._n == len(self._a):                      # pieno: raddoppia
            nuovo = [None] * (2 * len(self._a))
            for i in range(self._n):
                nuovo[i] = self._a[i]
            self._a = nuovo
        self._a[self._n] = x
        self._n += 1

Costo: una append che ridimensiona costa $O(n)$, ma succede dopo $1, 2, 4, 8, \dots$ inserimenti; in $m$ inserimenti le copie totali sono $1 + 2 + 4 + \dots < 2m$, quindi $O(1)$ ammortizzato per inserimento. Con un incremento costante (capacità $+1$ o $+10$) le copie sono invece $O(m^2)$ in totale. È il meccanismo di list in Python e di realloc in C (Gestione della memoria in CSegmenti di memoria di un processo (codice, dati statici, stack, heap); durata delle variabili; allocazione dinamica con malloc, calloc, realloc e free; errori classici: memory leak, dangling pointer, double free, buffer overflow; strumenti di controllo.Gestione della memoria in C →).

Dizionario su array ordinato

Un dizionario associa un valore a una chiave unica: inserisci (sostituisce se la chiave c'è), cerca, cancella. Tenendo le chiavi ordinate in un array si può usare la ricerca binariaRicerca lineare su sequenze qualsiasi in O(n); ricerca binaria su sequenze ordinate in O(log n), versione iterativa e ricorsiva, invariante e errori di indice; modulo bisect.Ricerca lineare e binaria →:

from bisect import bisect_left

class Dizionario:
    def __init__(self):
        self._k, self._v = [], []

    def _posto(self, k):
        i = bisect_left(self._k, k)
        return i, (i < len(self._k) and self._k[i] == k)

    def inserisci(self, k, v):
        i, trovata = self._posto(k)
        if trovata:
            self._v[i] = v
        else:
            self._k.insert(i, k)
            self._v.insert(i, v)

    def cerca(self, k):
        i, trovata = self._posto(k)
        if not trovata:
            raise KeyError(k)
        return self._v[i]

    def cancella(self, k):
        i, trovata = self._posto(k)
        if not trovata:
            raise KeyError(k)
        del self._k[i], self._v[i]

    def __len__(self):
        return len(self._k)


d = Dizionario()
for nome, num in [("Zeno", 3), ("Ada", 1), ("Mia", 2), ("Ada", 9)]:
    d.inserisci(nome, num)
print(d._k, d._v, len(d))        # ['Ada', 'Mia', 'Zeno'] [9, 2, 3] 3
print(d.cerca("Mia"))            # 2
d.cancella("Mia")
print(len(d))                    # 2

Costi: cerca $O(\log n)$; inserisci e cancella $O(n)$ per gli spostamenti (la ricerca del posto è comunque $O(\log n)$). Su un array non ordinato la ricerca è $O(n)$, e anche l'inserimento lo è, perché prima bisogna verificare che la chiave non ci sia già. La tabella hash di dict (Dizionari e insiemi in PythonADT mappa e insieme; dict con chiavi hashable, accesso, get, iterazione, conteggi e raggruppamenti; set e operazioni insiemistiche; tabelle hash e costo O(1) medio; Counter e defaultdict.Dizionari e insiemi in Python →) dà $O(1)$ medio per tutte le operazioni ma non mantiene l'ordine delle chiavi.

Se il dizionario deve poter dare gli elementi ordinati (una toSortedArray), l'array ordinato li ha già; con una struttura non ordinata servono un ordinamento (Algoritmi di ordinamentoSelection sort e insertion sort (quadratici, con invarianti), merge sort (divide et impera, Theta(n log n)), quick sort (caso pessimo quadratico, medio n log n), heap sort (in loco, Theta(n log n)), ordinamento senza confronti per chiavi intere in un intervallo piccolo, limite inferiore Omega(n log n) per gli algoritmi basati su confronti.Algoritmi di ordinamento →) in $O(n \log n)$.

Coda doppia su array circolare

Una coda doppia (deque) permette inserimento e rimozione a entrambe le estremità. Su array circolare con testa t e lunghezza n, l'elemento i-esimo sta in a[(t + i) % cap]:

class CodaVuota(Exception):
    pass

class CodaDoppia:
    def __init__(self, cap=2):
        self._a, self._t, self._n = [None] * cap, 0, 0

    def _raddoppia(self):
        cap = len(self._a)
        nuovo = [self._a[(self._t + i) % cap] for i in range(self._n)] + [None] * cap
        self._a, self._t = nuovo, 0

    def add_last(self, x):
        if self._n == len(self._a):
            self._raddoppia()
        self._a[(self._t + self._n) % len(self._a)] = x
        self._n += 1

    def add_first(self, x):
        if self._n == len(self._a):
            self._raddoppia()
        self._t = (self._t - 1) % len(self._a)       # la testa arretra (Python: % è sempre >= 0)
        self._a[self._t] = x
        self._n += 1

    def remove_first(self):
        if self._n == 0:
            raise CodaVuota
        x = self._a[self._t]
        self._a[self._t] = None
        self._t = (self._t + 1) % len(self._a)
        self._n -= 1
        return x

    def remove_last(self):
        if self._n == 0:
            raise CodaVuota
        i = (self._t + self._n - 1) % len(self._a)
        x, self._a[i] = self._a[i], None
        self._n -= 1
        return x

    def __len__(self):
        return self._n


c = CodaDoppia()
for x in (1, 2, 3):
    c.add_last(x)
c.add_first(0)
print(c.remove_first(), c.remove_last(), len(c))   # 0 3 2

Tutte le operazioni sono $O(1)$ tranne il raddoppio, ammortizzato $O(1)$. In C la formula è identica, ma attenzione: (t - 1) % cap con t = 0 dà $-1$ in C (il resto ha il segno del dividendo); si scrive (t + cap - 1) % cap. L'alternativa è la lista doppiamente concatenata (Liste concatenateLista concatenata semplice: nodi allocati dinamicamente collegati da puntatori; inserimento e rimozione in testa, scorrimento, ricerca, inserimento ordinato, deallocazione; confronto dei costi con l'array; versione in Python.Liste concatenate →) con puntatori a testa e coda: $O(1)$ senza raddoppi, ma un puntatore in più per elemento. collections.deque è già una coda doppia.

Coda con priorità a livelli

Una coda con priorità estrae sempre l'elemento a priorità più alta. Se i livelli sono pochi e fissi (4 livelli, 0 = massima), si tiene una coda per livello:

from collections import deque

class CodaPriorita:
    def __init__(self, livelli=4):
        self._code = [deque() for _ in range(livelli)]

    def inserisci(self, priorita, x):            # O(1)
        self._code[priorita].append(x)

    def estrai(self):                            # O(numero di livelli)
        for q in self._code:
            if q:
                return q.popleft()
        raise IndexError("coda vuota")


cp = CodaPriorita()
cp.inserisci(2, "spesa"); cp.inserisci(0, "esame"); cp.inserisci(0, "tesi")
print(cp.estrai(), cp.estrai(), cp.estrai())     # esame tesi spesa

A parità di priorità l'ordine è FIFO. Con priorità arbitrarie si usa uno heap (heapq): inserimento ed estrazione $O(\log n)$.

ADT costruiti sopra altri ADT

Spesso la struttura richiesta si ottiene componendo ADT già pronti, senza toccare gli array:

• Pila di code di taglia massima $k$: una pila di code; push inserisce nella coda in cima, e se è piena ne apre una nuova; pop toglie dalla coda in cima il primo inserito e, se si svuota, la elimina.
• Multicoda (sportelli di una biglietteria): una lista di $N$ code; chi arriva si accoda alla più corta (min(range(N), key=lambda i: len(code[i]))).
• Pila reversibile con reverse() in $O(1)$: una coda doppia e un flag invertita; push e pop lavorano a un'estremità o all'altra a seconda del flag, reverse inverte il flag.

La complessità di ogni operazione è quella delle operazioni dell'ADT usato, più il costo del codice che le collega.

Costi a confronto

Errori tipici

• Dimenticare di aggiornare la lunghezza logica n dopo un inserimento o una rimozione.
• Nell'array circolare, scordare il modulo o usare n e capacità come se fossero la stessa cosa (coda piena e coda vuota si confondono se non si tiene n).
• Raddoppiare senza riallineare la testa a 0: gli elementi copiati non sono più in posizione.
• Ridimensionare con incremento costante invece che per raddoppio: il costo medio diventa lineare.
• In un dizionario, inserire una chiave già presente come se fosse nuova (duplicati) invece di sostituire il valore.
• Rimuovere o leggere da un contenitore vuoto senza segnalare l'errore (eccezione) come prevede l'interfaccia.