Esercizio 10coda doppia con costo costante

Esame

In questa pagina 5

Testo (appello del 13 febbraio 2018 di Fondamenti di Informatica, Ingegneria dell'Informazione UniPD; adattato da un tema d'esame in Java, qui in Python).

Il tipo di dato astratto CD (coda doppia) offre le operazioni:

operazione	significato
`size()`, `is_empty()`	numero di elementi; vero se vuota
`add_first(x)`, `add_last(x)`	aggiunge all'inizio / alla fine
`remove_first()`, `remove_last()`	toglie e restituisce l'elemento all'inizio / alla fine; eccezione `EmptyCDException` se vuota
`get_first()`, `get_last()`	restituisce senza togliere; eccezione se vuota

Scrivere la classe MiaCD che realizza l'ADT in modo che tutte le operazioni richiedano tempo $O(1)$ , oppure $O(1)$ in termini di analisi ammortizzata, e l'eccezione EmptyCDException, che estende RuntimeException (qui RuntimeError).
Scrivere un programma di prova che crea tre code uno, due, tre; legge dallo standard input una sequenza di stringhe (una per riga) e le inserisce alla fine di uno; svuota uno dalla fine (remove_last) trasferendone il contenuto all'inizio di due; svuota due dall'inizio (remove_first) inserendo i dati alla fine di tre; svuota infine tre dall'inizio scrivendo i dati sullo standard output, uno per riga. I dati in uscita devono avere lo stesso ordine di quelli in ingresso.

Teoria: Pila e coda, Liste concatenate, Complessità computazionale, Realizzare contenitori su array e liste.

Scelta della rappresentazione

Un array normale non va bene: togliere o aggiungere all'inizio sposta tutti gli elementi, $O(n)$ . Servono due estremità raggiungibili in $O(1)$ :

array circolare: si tengono l'indice t del primo elemento e il numero n di elementi; l'elemento i-esimo sta in a[(t + i) % capacità]. add_first fa arretrare t (in modo circolare); add_last scrive in (t + n) % cap. Se l'array è pieno si raddoppia la capacità: la copia costa $O(n)$ ma succede dopo $4, 8, 16, \dots$ inserimenti, quindi il costo è $O(1)$ ammortizzato (vedi Realizzare contenitori su array e liste);
lista doppiamente concatenata con puntatori a entrambe le estremità: tutte le operazioni sono $O(1)$ senza ammortizzamento, ma serve un oggetto per ogni elemento.

Si tiene n separato (invece di un indice di fine) per distinguere coda piena da coda vuota: con soli t e indice di fine le due situazioni coinciderebbero.

Soluzione con array circolare

python

import io

class EmptyCDException(RuntimeError):
    """operazione su una coda doppia vuota"""


class MiaCD:
    """Coda doppia su array circolare con raddoppio: tutte le operazioni O(1) (ammortizzato)."""

    def __init__(self):
        self._a = [None] * 4        # array
        self._t = 0                 # indice del primo elemento
        self._n = 0                 # numero di elementi

    def size(self):
        return self._n

    def is_empty(self):
        return self._n == 0

    def _cresci(self):              # O(n), ma raro: ammortizzato O(1)
        cap = len(self._a)
        nuovo = [self._a[(self._t + i) % cap] for i in range(self._n)]   # in ordine, da 0
        self._a = nuovo + [None] * cap
        self._t = 0                 # la testa torna a 0

    def add_first(self, x):
        if self._n == len(self._a):
            self._cresci()
        self._t = (self._t - 1) % len(self._a)       # arretra: in Python % dà sempre >= 0
        self._a[self._t] = x
        self._n += 1

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

    def get_first(self):
        if self._n == 0:
            raise EmptyCDException("get_first su coda vuota")
        return self._a[self._t]

    def get_last(self):
        if self._n == 0:
            raise EmptyCDException("get_last su coda vuota")
        return self._a[(self._t + self._n - 1) % len(self._a)]

    def remove_first(self):
        x = self.get_first()
        self._a[self._t] = None                      # libera il riferimento
        self._t = (self._t + 1) % len(self._a)
        self._n -= 1
        return x

    def remove_last(self):
        x = self.get_last()
        self._a[(self._t + self._n - 1) % len(self._a)] = None
        self._n -= 1
        return x


def main(f, out):
    uno, due, tre = MiaCD(), MiaCD(), MiaCD()
    for riga in f:
        uno.add_last(riga.rstrip("\n"))
    while not uno.is_empty():
        due.add_first(uno.remove_last())             # inverte due volte...
    while not due.is_empty():
        tre.add_last(due.remove_first())
    while not tre.is_empty():
        print(tre.remove_first(), file=out)


dati = "uno\ndue\ntre\nquattro\ncinque\nsei\nsette\n"
out = io.StringIO()
main(io.StringIO(dati), out)                          # con la tastiera: main(sys.stdin, sys.stdout)
assert out.getvalue() == dati                         # come "diff stringhe.txt output.txt"
print(out.getvalue().split())                         # ['uno', 'due', 'tre', 'quattro', 'cinque', 'sei', 'sette']

Perché l'ordine si conserva. Con ingresso s1 s2 s3: uno = [s1, s2, s3]. remove_last dà s3, s2, s1 e ogni elemento va in testa a due: due = [s3], poi [s2, s3], poi [s1, s2, s3]; i due travasi invertono due volte l'ordine, il risultato è l'ordine originale. due.remove_first() dà s1, s2, s3 e tre.add_last li accoda nello stesso ordine.

Soluzione con lista doppiamente concatenata

Due sentinelle (nodi fittizi all'inizio e alla fine) eliminano i casi particolari "lista vuota" e "un solo elemento":

python

class CDLista:
    """Coda doppia su lista doppiamente concatenata con due sentinelle."""

    class _Nodo:
        __slots__ = ("val", "prec", "succ")
        def __init__(self, val, prec, succ):
            self.val, self.prec, self.succ = val, prec, succ

    def __init__(self):
        self._testa = self._Nodo(None, None, None)          # sentinella iniziale
        self._coda = self._Nodo(None, self._testa, None)    # sentinella finale
        self._testa.succ = self._coda
        self._n = 0

    def size(self): return self._n
    def is_empty(self): return self._n == 0

    def _inserisci_dopo(self, nodo, x):                     # O(1)
        nuovo = self._Nodo(x, nodo, nodo.succ)
        nodo.succ.prec = nuovo
        nodo.succ = nuovo
        self._n += 1

    def _togli(self, nodo):                                 # O(1)
        nodo.prec.succ = nodo.succ
        nodo.succ.prec = nodo.prec
        self._n -= 1
        return nodo.val

    def add_first(self, x): self._inserisci_dopo(self._testa, x)
    def add_last(self, x): self._inserisci_dopo(self._coda.prec, x)

    def get_first(self):
        if self._n == 0: raise EmptyCDException("coda vuota")
        return self._testa.succ.val

    def get_last(self):
        if self._n == 0: raise EmptyCDException("coda vuota")
        return self._coda.prec.val

    def remove_first(self):
        if self._n == 0: raise EmptyCDException("coda vuota")
        return self._togli(self._testa.succ)

    def remove_last(self):
        if self._n == 0: raise EmptyCDException("coda vuota")
        return self._togli(self._coda.prec)

Verifica

Si confrontano le due implementazioni con collections.deque su sequenze casuali di operazioni (anche su coda vuota):

python

from collections import deque
import random

for classe in (MiaCD, CDLista):
    for _ in range(200):
        c, d = classe(), deque()
        for _ in range(200):
            op = random.choice(["af", "al", "rf", "rl", "gf", "gl"])
            try:
                if op == "af":
                    x = random.random(); c.add_first(x); d.appendleft(x)
                elif op == "al":
                    x = random.random(); c.add_last(x); d.append(x)
                elif op == "rf":
                    assert c.remove_first() == d.popleft()
                elif op == "rl":
                    assert c.remove_last() == d.pop()
                elif op == "gf":
                    assert c.get_first() == d[0]
                else:
                    assert c.get_last() == d[-1]
            except EmptyCDException:
                assert not d                  # l'eccezione deve comparire solo se è vuota
            assert c.size() == len(d)
    print(classe.__name__, "ok")

Errori comuni

Usare una list Python con insert(0, x) o pop(0): $O(n)$ , viola il vincolo.
Non riportare la testa a 0 dopo il raddoppio: gli elementi copiati non sono nelle posizioni attese.
Calcolare l'indice della fine come t + n senza il modulo, o t - 1 senza modulo (in C darebbe $-1$ : si scrive (t + cap - 1) % cap).
Nella lista concatenata, aggiornare un solo verso dei collegamenti (succ ma non prec).
Dimenticare di sollevare EmptyCDException su get_* e remove_* a coda vuota.

Versione ripasso

Appello del 13 febbraio 2018 (UniPD, in Java; adattato a Python). Teoria: Realizzare contenitori su array e liste, Liste concatenate.

ADT CD: size, is_empty, add_first, add_last, remove_first, remove_last, get_first, get_last (eccezione EmptyCDException se vuota); vincolo: ogni operazione $O(1)$ o $O(1)$ ammortizzato.

Array circolare: t (primo), n (elementi), elemento i in a[(t + i) % cap]; add_first: t = (t - 1) % cap; add_last: indice (t + n) % cap; ultimo: (t + n - 1) % cap; pieno → raddoppio copiando in ordine da 0 e t = 0 (ammortizzato $O(1)$ ). Si tiene n per distinguere pieno e vuoto.

Lista doppiamente concatenata con due sentinelle: _inserisci_dopo(nodo, x) e _togli(nodo) aggiornano prec e succ, tutto $O(1)$ .

Programma di prova: uno.add_last per ogni riga; due.add_first(uno.remove_last()) fino a vuotare uno; tre.add_last(due.remove_first()); stampa tre.remove_first(): l'ordine in uscita è quello in ingresso (due inversioni).

Errori comuni: insert(0, x)/pop(0) ( $O(n)$ ); testa non riportata a 0 dopo il raddoppio; modulo dimenticato (in C (t + cap - 1) % cap); un solo verso dei collegamenti aggiornato; eccezione non sollevata su coda vuota.

Esercizio 10coda doppia con costo costante

Scelta della rappresentazione

Soluzione con array circolare

Soluzione con lista doppiamente concatenata

Verifica

Errori comuni

Teoria collegata