Pattern algoritmici iterativi

Molti problemi su sequenze si risolvono combinando pochi schemi di ciclo. Per ognuno conviene sapere inizializzazione, aggiornamento e invariante (vedi Ciclo whileCiclo while, cicli controllati da contatore, da sentinella e da condizione; break, continue, else; terminazione e invariante di ciclo.Ciclo while →).

Accumulatore

Definizione (schema dell'accumulatore). Variabile inizializzata all'elemento neutro dell'operazione e aggiornata a ogni elemento.

somma = 0                      # neutro della somma
prodotto = 1                   # neutro del prodotto
testo = ""                     # neutro della concatenazione
for x in valori:
    somma += x
    prodotto *= x

Invariante: dopo $k$ iterazioni somma è la somma dei primi $k$ elementi.

Esempio. Con valori = [2, 3, 4] il ciclo dà somma = 9 e prodotto = 24.

Contatore

Definizione (schema del contatore)

conta = 0
for x in valori:
    if x > soglia:
        conta += 1
# equivalente: conta = sum(1 for x in valori if x > soglia)

Esempio. Con valori = [5, 1, 8, 7] e soglia = 4, conta vale 3.

Frequenze di più valori: un dizionario di contatori (vedi 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 →).

Massimo e minimo

Definizione (schema del massimo e del minimo). Si inizializza con il primo elemento, non con 0 (i valori potrebbero essere tutti negativi).

def indice_massimo(v):
    """Indice del massimo di una lista non vuota."""
    im = 0
    for i in range(1, len(v)):
        if v[i] > v[im]:
            im = i
    return im

> restituisce la prima occorrenza del massimo, >= l'ultima.

Esempio. indice_massimo([3, 9, 2, 9]) restituisce 1, la prima occorrenza del massimo; con >= al posto di > restituirebbe 3.

Ricerca con uscita anticipata (esiste?)

Definizione (ricerca con uscita anticipata)

def contiene_negativo(v):
    for x in v:
        if x < 0:
            return True        # basta un esempio: esco subito
    return False               # solo dopo aver visto tutto

Esempio. contiene_negativo([4, -1, 7]) restituisce True appena vede -1; contiene_negativo([4, 1]) restituisce False.

Verifica universale (per ogni?)

Definizione (verifica universale)

def tutti_positivi(v):
    for x in v:
        if x <= 0:
            return False       # basta un controesempio
    return True

Equivalenti predefiniti: any(x < 0 for x in v), all(x > 0 for x in v). Errore classico: mettere return True dentro il ciclo nel ramo else, decidendo dopo il primo elemento.

Esempio. tutti_positivi([3, 0, 5]) restituisce False al secondo elemento; all(x > 0 for x in [3, 4]) restituisce True.

Filtro e trasformazione

positivi = [x for x in v if x > 0]          # filtro
doppi = [2 * x for x in v]                  # trasformazione (map)

Elementi adiacenti

Confronto di ogni elemento con il successivo: indici fino a len(v) - 2.

def ordinata(v):
    for i in range(len(v) - 1):
        if v[i] > v[i + 1]:
            return False
    return True

Finestra scorrevole

Definizione (finestra scorrevole). Somma di ogni blocco di k elementi consecutivi aggiornando invece di ricalcolare ($O(n)$ invece di $O(nk)$):

def max_somma_finestra(v, k):
    s = sum(v[:k])
    migliore = s
    for i in range(k, len(v)):
        s += v[i] - v[i - k]       # entra v[i], esce v[i-k]
        migliore = max(migliore, s)
    return migliore

Esempio. max_somma_finestra([1, 3, 2, 6, 1], 2) restituisce 8, la somma di 2 e 6.

Due indici

Due indici che si muovono da estremi opposti o a velocità diverse.

def palindroma(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

def fusione(a, b):
    """Unisce due liste ordinate in una lista ordinata (base del merge sort)."""
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    out.extend(a[i:])
    out.extend(b[j:])
    return out

Tutte le coppie

# coppie i < j: n(n-1)/2 confronti
for i in range(len(v)):
    for j in range(i + 1, len(v)):
        if v[i] == v[j]:
            print("duplicato:", v[i])

Costo quadratico: con un insieme si fa in tempo lineare (vedi 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 →).

Errori tipici

• Inizializzare il massimo a 0 o l'accumulatore del prodotto a 0.
• Decidere "per ogni" alla prima iterazione.
• Indici fuori intervallo negli schemi con v[i + 1].
• Reinizializzare l'accumulatore dentro il ciclo invece che prima.