03 - Ricerca: lineare, binaria, hash tables

Hai un milione di codici cliente e devi sapere, per ogni richiesta che arriva, se uno di essi è presente. Puoi scorrere la lista, puoi tenerla ordinata e dimezzare lo spazio a ogni passo, oppure puoi calcolare direttamente dove il codice dovrebbe stare. Sono tre costi molto diversi, e la differenza non sta nella bravura di chi scrive il codice ma in due cose che si controllano: l'ingresso è ordinato? Quanta memoria sei disposto a spendere per risposte più rapide?

Questo è il terzo articolo della serie Algoritmi e Strutture Dati; per leggerlo servono l'analisi per conteggio del primo articolo e, per la ricerca binaria, l'idea di lista ordinata vista nel secondo. I listati sono in Python 3.14 con la sola libreria standard (python3 -I); ogni costo è un conteggio (sonde, confronti, celle esaminate), e ciascuna formula è confrontata con una misura. La ricerca lineare l'hai già vista nel primo articolo, con i suoi n confronti nel caso peggiore: qui parto dalla binaria.

Ricerca binaria: l'invariante prima del codice

La ricerca binaria funziona perché, a ogni passo, sai due cose: tutto ciò che sta a sinistra di lo è minore del valore cercato, e tutto ciò che sta da hi in poi è maggiore o uguale. Questa coppia di fatti è l'invariante del ciclo: vera prima di ogni giro, mantenuta da ogni giro, e al termine (lo == hi) ti dice che lo è il primo posto dove il valore potrebbe stare. Il listato la verifica a ogni iterazione con un assert, su tutte le liste ordinate con valori da 0 a 5 e lunghezza fino a 8, duplicati compresi.

# Ricerca binaria (variante "primo indice con a[i] >= x"), con l'invariante verificata a ogni passo
import math, random
from bisect import bisect_left

def binary_search(a, x, check=False):
    lo, hi, probes = 0, len(a), 0
    while lo < hi:
        if check:                            # invariante: tutto a sinistra di lo e' < x, tutto da hi in poi e' >= x
            assert all(v < x for v in a[:lo]) and all(v >= x for v in a[hi:])
        mid = (lo + hi) // 2
        probes += 1
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo, probes                        # lo e' il punto di inserimento; trovato se a[lo] == x

# correttezza: tutte le liste ordinate con valori in 0..5 fino a lunghezza 8 (con duplicati), ogni x da -1 a 6
import itertools
for n in range(0, 9):
    for a in itertools.combinations_with_replacement(range(6), n):
        for x in range(-1, 7):
            pos, probes = binary_search(list(a), x, check=True)
            assert pos == bisect_left(a, x)                          # riferimento: libreria standard
            assert pos == next((i for i, v in enumerate(a) if v >= x), n)   # riferimento: scansione lineare
            assert probes <= (math.floor(math.log2(n)) + 1 if n else 0)
print("ricerca binaria: corretta, invariante verificata a ogni passo, sonde <= floor(log2 n)+1")

print(f"{'n':>9} {'sonde nel caso peggiore':>24} {'floor(log2 n)+1':>16} {'ricerca lineare':>16}")
for n in (10, 1000, 10**6, 10**9):
    worst = max(binary_search(range(n), x)[1] for x in (-1, 0, n // 3, n - 1, n))   # range(): nessuna lista da 10^9
    print(f"{n:>9} {worst:>24} {math.floor(math.log2(n)) + 1:>16} {n:>16}")

# se la lista NON e' ordinata il risultato non ha senso: 2000 liste casuali di 8 elementi distinti
rng = random.Random(7)
missed = 0
for _ in range(2000):
    a = rng.sample(range(100), 8)
    x = rng.choice(a)
    pos, _ = binary_search(a, x)
    missed += not (pos < len(a) and a[pos] == x)
print("su lista non ordinata, elemento presente dichiarato assente:", missed, "volte su 2000")

# in linguaggi con interi a 32 bit, (lo + hi) // 2 puo' superare il massimo: simulazione dell'aritmetica a 32 bit
to_int32 = lambda v: (v + 2**31) % 2**32 - 2**31
lo, hi = 1_500_000_000, 2_000_000_000
print("(lo + hi) / 2 a 32 bit:", to_int32(lo + hi) // 2, "| lo + (hi - lo) / 2:", to_int32(lo + (hi - lo) // 2))

# Output:
# ricerca binaria: corretta, invariante verificata a ogni passo, sonde <= floor(log2 n)+1
#         n  sonde nel caso peggiore  floor(log2 n)+1  ricerca lineare
#        10                        4                4               10
#      1000                       10               10             1000
#   1000000                       20               20          1000000
# 1000000000                       30               30       1000000000
# su lista non ordinata, elemento presente dichiarato assente: 1522 volte su 2000
# (lo + hi) / 2 a 32 bit: -397483648 | lo + (hi - lo) / 2: 1750000000

La variante restituisce il punto di inserimento, non solo «trovato / non trovato», ed è la stessa semantica di bisect_left nella libreria standard di Python (pos == bisect_left(a, x) è uno dei due riferimenti indipendenti, l'altro è una scansione lineare). Il numero di sonde nel caso peggiore è ⌊log₂ n⌋ + 1 in ogni riga: 10 per mille elementi, 20 per un milione, 30 per un miliardo. Per scorrere un miliardo di elementi servono un miliardo di confronti; per dimezzare ne servono trenta. È il vantaggio dell'ordine.

Le ultime due righe sono i due modi in cui la ricerca binaria si rompe. Se la lista non è ordinata, il risultato non è «un po' sbagliato»: su 2.000 liste casuali ha dichiarato assente un elemento presente 1.522 volte, il 76%. E in linguaggi con interi a 32 bit il calcolo (lo + hi) / 2 può superare il massimo rappresentabile: con lo = 1,5 miliardi e hi = 2 miliardi la somma diventa negativa e il punto medio esce fuori dalla lista (−397.483.648), mentre lo + (hi − lo) / 2 dà 1.750.000.000. In Python gli interi non hanno limite e il problema non si presenta; l'ho simulato con l'aritmetica a 32 bit per mostrarti la forma dell'errore.

Tabella hash: calcolare dove sta la chiave

Una tabella hash usa una funzione per trasformare la chiave in un indice di un array di m posizioni. Due chiavi diverse possono finire nella stessa posizione, ed è una collisione: va gestita. La soluzione più semplice è tenere in ogni posizione una lista (chaining). Il listato implementa inserimento, ricerca e cancellazione, e li verifica contro dict su 20.000 operazioni casuali a seme fisso. Il costo è il numero di confronti di chiave lungo la lista.

# Tabella hash con liste di collisione (chaining): costo = confronti di chiave lungo la lista
import random

class ChainedTable:
    def __init__(self, m, hash_fn):
        self.m, self.hash_fn = m, hash_fn
        self.buckets = [[] for _ in range(m)]
        self.compares = 0
    def _chain(self, key):
        return self.buckets[self.hash_fn(key) % self.m]
    def put(self, key, value):
        chain = self._chain(key)
        for pair in chain:
            if pair[0] == key:
                pair[1] = value
                return
        chain.append([key, value])
    def get(self, key):
        for k, v in self._chain(key):
            self.compares += 1
            if k == key:
                return v
        return None
    def delete(self, key):
        chain = self._chain(key)
        for i, pair in enumerate(chain):
            if pair[0] == key:
                del chain[i]
                return True
        return False

good = lambda k: (k * 2654435761) & 0xFFFFFFFF      # hash moltiplicativo di Knuth
bad = lambda k: 0                                    # tutte le chiavi nello stesso secchio

# correttezza contro dict: 20000 operazioni casuali, seme fisso
rng = random.Random(8)
t, ref = ChainedTable(64, good), {}
for _ in range(20000):
    k, op = rng.randrange(500), rng.randrange(3)
    if op == 0:
        t.put(k, k * 2); ref[k] = k * 2
    elif op == 1:
        assert t.get(k) == ref.get(k)
    else:
        assert t.delete(k) == (ref.pop(k, None) is not None)
print("tabella con liste: coerente con dict su 20000 operazioni")

M = 1024
print(f"{'alpha':>6} {'trovata: misura':>16} {'1 + alpha/2':>12} | {'assente: misura':>16} {'alpha':>7}")
for alpha in (0.5, 1, 2, 4):
    n = int(alpha * M)
    keys = rng.sample(range(10**9), n)
    t = ChainedTable(M, good)
    for k in keys:
        t.put(k, 0)
    t.compares = 0
    for k in keys:
        t.get(k)
    hit = t.compares / n
    absent = rng.sample(range(10**9, 2 * 10**9), 5000)
    t.compares = 0
    for k in absent:
        t.get(k)
    miss = t.compares / 5000
    print(f"{alpha:>6} {hit:>16.2f} {1 + alpha / 2:>12.2f} | {miss:>16.2f} {alpha:>7}")

keys = rng.sample(range(10**9), 1000)
for name, fn in (("buona", good), ("costante", bad)):
    t = ChainedTable(1024, fn)
    for k in keys:
        t.put(k, 0)
    t.compares = 0
    for k in keys:
        t.get(k)
    print(f"funzione {name}: confronti medi per ricerca di 1000 chiavi = {t.compares / 1000:.1f}")

# Output:
# tabella con liste: coerente con dict su 20000 operazioni
#  alpha  trovata: misura  1 + alpha/2 |  assente: misura   alpha
#    0.5             1.26         1.25 |             0.48     0.5
#      1             1.50         1.50 |             1.00       1
#      2             2.00         2.00 |             2.01       2
#      4             3.01         3.00 |             3.96       4
# funzione buona: confronti medi per ricerca di 1000 chiavi = 1.5
# funzione costante: confronti medi per ricerca di 1000 chiavi = 500.5

Il parametro che governa tutto è il fattore di carico α = n/m, il numero medio di elementi per lista. Una ricerca con successo costa in media 1 + α/2 confronti: trovi la chiave a metà di una lista di lunghezza α, più il confronto che la identifica; una ricerca senza successo scorre l'intera lista, cioè α. Le misure coincidono: 1,26 contro 1,25, 1,50, 2,00 e 3,01 contro 3,00 per le ricerche con successo, e 0,48, 1,00, 2,01 e 3,96 contro α per quelle senza. Il costo non dipende da n ma dal rapporto n/m, quindi se mantieni α limitato il costo è costante.

La condizione nascosta è che la funzione hash distribuisca le chiavi in modo uniforme: è l'ipotesi del testo di Sedgewick e Wayne, Algorithms, nella pagina sulle tabelle hash (Assumption J, «uniform hashing assumption»). Le ultime due righe mostrano che cosa accade quando non vale: con la stessa tabella e le stesse 1.000 chiavi, una funzione costante manda tutto nello stesso secchio e la ricerca costa in media 500,5 confronti, cioè (n + 1)/2, ovvero una ricerca lineare su una lista. «O(1)» è una proprietà della funzione hash tanto quanto della struttura.

Indirizzamento aperto e ridimensionamento

L'alternativa alle liste è tenere tutto nell'array: se la posizione è occupata si prova la successiva (scansione lineare). Non servono puntatori, ma la tabella non può riempirsi del tutto e le collisioni si accumulano in «grumi». Il listato conta le celle esaminate per una ricerca, e confronta la misura con le formule della Proposition M della pagina di Sedgewick e Wayne: ½(1 + 1/(1 − α)) per le ricerche con successo e ½(1 + 1/(1 − α)²) per quelle senza successo.

# Indirizzamento aperto con scansione lineare: costo = celle esaminate (sonde)
import random

class ProbingTable:
    def __init__(self, m, grow=False):
        self.m, self.n, self.slots, self.grow = m, 0, [None] * m, grow
        self.moves = 0                      # elementi spostati dai ridimensionamenti
        self.worst_insert = 0
    def _index(self, key, m):
        return ((key * 2654435761) & 0xFFFFFFFF) % m
    def put(self, key):
        cost = 1
        if self.grow and self.n + 1 > self.m // 2:    # fattore di carico massimo 1/2
            cost += self._resize(2 * self.m)
        i = self._index(key, self.m)
        while self.slots[i] is not None:
            i = (i + 1) % self.m
        self.slots[i] = key
        self.n += 1
        self.worst_insert = max(self.worst_insert, cost)
    def _resize(self, new_m):
        old, self.slots, self.m, self.n = [k for k in self.slots if k is not None], [None] * new_m, new_m, 0
        for k in old:
            i = self._index(k, self.m)
            while self.slots[i] is not None:
                i = (i + 1) % self.m
            self.slots[i] = k
            self.n += 1
        self.moves += len(old)
        return len(old)
    def probes(self, key):
        i, count = self._index(key, self.m), 1
        while self.slots[i] is not None and self.slots[i] != key:
            i = (i + 1) % self.m
            count += 1
        return count

rng = random.Random(9)
M = 65536
print(f"{'alpha':>6} {'trovata: misura':>16} {'1/2(1+1/(1-a))':>15} | {'assente: misura':>16} {'1/2(1+1/(1-a)^2)':>17}")
for alpha in (0.25, 0.5, 0.75, 0.9):
    n = int(alpha * M)
    keys = rng.sample(range(10**9), n)
    t = ProbingTable(M)
    for k in keys:
        t.put(k)
    hit = sum(t.probes(k) for k in keys) / n
    absent = rng.sample(range(10**9, 2 * 10**9), 20000)
    miss = sum(t.probes(k) for k in absent) / 20000
    a = n / M
    print(f"{a:>6.2f} {hit:>16.2f} {0.5 * (1 + 1 / (1 - a)):>15.2f} | {miss:>16.2f} {0.5 * (1 + 1 / (1 - a) ** 2):>17.2f}")

print()
print(f"{'inserimenti':>12} {'spostamenti totali':>19} {'per inserimento':>16} {'peggiore singolo':>17}")
for N in (1000, 10000, 100000):
    t = ProbingTable(8, grow=True)
    for k in rng.sample(range(10**9), N):
        t.put(k)
    print(f"{N:>12} {t.moves:>19} {t.moves / N:>16.2f} {t.worst_insert:>17}")

# Output:
#  alpha  trovata: misura  1/2(1+1/(1-a)) |  assente: misura  1/2(1+1/(1-a)^2)
#   0.25             1.17            1.17 |             1.38              1.39
#   0.50             1.50            1.50 |             2.47              2.50
#   0.75             2.46            2.50 |             8.21              8.50
#   0.90             5.06            5.50 |            41.92             50.49
#
#  inserimenti  spostamenti totali  per inserimento  peggiore singolo
#         1000                1020             1.02               513
#        10000               16380             1.64              8193
#       100000              131068             1.31             65537

A α = 0,25 e 0,5 le misure coincidono con le formule (1,17 e 1,50 per le ricerche con successo; 1,38 e 2,47 contro 1,39 e 2,50 per quelle senza). Ma quando α si avvicina a 1 il costo esplode: a 0,9 una ricerca senza successo costa circa 42 sonde nella tabella da 65.536 posizioni, e la formula ne prevede 50,5. La differenza non è un errore di misura: le formule sono asintotiche per tabelle grandi, e con una tabella da 2.048 posizioni (cambia M nel listato) lo stesso esperimento mi ha dato 3,94 e 24,10 a α = 0,9. Di qui la regola pratica: non portare una tabella ad indirizzamento aperto oltre un fattore di carico di circa metà.

Per mantenere α basso la tabella si ridimensiona: quando supera il carico massimo (qui 1/2) raddoppia le posizioni e reinserisce ogni chiave. La seconda tabella dell'uscita mostra il costo di questa operazione. Su 100.000 inserimenti gli spostamenti totali sono 131.068, cioè 1,31 per inserimento (e fra 1,02 e 1,64 sulle tre dimensioni), mentre il singolo inserimento più costoso ne richiede 65.537: è lo stesso schema dell'array dinamico del primo articolo. L'inserimento è O(1) ammortizzato, non nel caso peggiore, e se hai una latenza massima da rispettare quel picco è il numero che conta.

Perché in Python l'hash delle stringhe cambia a ogni avvio

Chi conosce la funzione hash può costruire chiavi che finiscono tutte nello stesso secchio, ed è esattamente l'esperimento con la funzione costante: una tabella che riceve quelle chiavi diventa quadratica nel tempo di costruzione. La documentazione del modello dei dati di Python dice che per questo gli hash di str e bytes sono «salati» con un valore casuale imprevedibile, costante dentro un processo ma diverso fra un avvio e l'altro, a protezione da attacchi di negazione del servizio che sfruttano il caso peggiore dell'inserimento in un dizionario. Il listato lo verifica avviando tre processi figli con PYTHONHASHSEED fissato.

# L'hash delle stringhe in Python e' "salato" a ogni avvio: lo si vede da due processi con semi diversi
import os, subprocess, sys

def hash_in_new_process(seed):
    env = dict(os.environ, PYTHONHASHSEED=str(seed))
    out = subprocess.run([sys.executable, "-c", "print(hash('algoritmi'))"],
                         env=env, capture_output=True, text=True, check=True).stdout
    return int(out)

a1, a2, b1 = hash_in_new_process(1), hash_in_new_process(2), hash_in_new_process(1)
print("stessa stringa, semi 1 e 2: hash uguali?", a1 == a2)
print("stessa stringa, seme 1 due volte: hash uguali?", a1 == b1)
print("hash di un intero piccolo non e' salato: hash(12345) =", hash(12345))

# Output:
# stessa stringa, semi 1 e 2: hash uguali? False
# stessa stringa, seme 1 due volte: hash uguali? True
# hash di un intero piccolo non e' salato: hash(12345) = 12345

Con semi diversi la stessa stringa ha hash diversi; con lo stesso seme, hash uguale; e l'hash di un intero piccolo non è salato (hash(12345) vale 12345). Le conseguenze sono pratiche: non salvare mai hash(s) su disco o in un database aspettandoti di ritrovarlo, e non dipendere dall'ordine di iterazione di un set di stringhe fra esecuzioni diverse, a meno di fissare il seme (cosa che nei test conviene fare). Per i listati della tabella hash ho scelto funzioni hash scritte a mano, e per il filtro di Bloom blake2b, che è deterministica, proprio perché l'uscita fosse la stessa a ogni esecuzione.

Filtro di Bloom: dire «certamente assente» con pochissima memoria

Un filtro di Bloom è un array di m bit e k funzioni hash. Inserisci una chiave accendendo k bit; chiedi se una chiave c'è controllando se tutti i suoi k bit sono accesi. Se uno è spento la chiave è certamente assente; se sono tutti accesi è probabilmente presente. Non esistono falsi negativi, ma esistono falsi positivi, e si possono prevedere: con n chiavi la probabilità è circa (1 − e^−kn/m)^k. Il listato inserisce 10.000 chiavi, controlla 50.000 chiavi mai inserite e confronta il tasso misurato con la formula, per cinque combinazioni di bit per chiave e di k.

# Filtro di Bloom: m bit, k funzioni hash ricavate da un solo digest (blake2b) con il doppio hashing
import hashlib, math

class Bloom:
    def __init__(self, m, k):
        self.m, self.k, self.bits = m, k, bytearray((m + 7) // 8)
    def _positions(self, key):
        d = hashlib.blake2b(str(key).encode(), digest_size=16).digest()
        h1, h2 = int.from_bytes(d[:8], "big"), int.from_bytes(d[8:], "big") | 1
        return [(h1 + i * h2) % self.m for i in range(self.k)]
    def add(self, key):
        for p in self._positions(key):
            self.bits[p // 8] |= 1 << (p % 8)
    def __contains__(self, key):
        return all(self.bits[p // 8] >> (p % 8) & 1 for p in self._positions(key))

n = 10000
print(f"{'bit/chiave':>10} {'k':>3} {'falsi positivi misurati':>24} {'(1-e^(-kn/m))^k':>16} {'falsi negativi':>15}")
for bits_per_key, k in ((5, 3), (10, 7), (10, 3), (10, 14), (15, 10)):
    m = bits_per_key * n
    f = Bloom(m, k)
    for key in range(n):
        f.add(key)
    false_neg = sum(key not in f for key in range(n))                  # deve essere 0
    tests = range(10**6, 10**6 + 50000)                                # chiavi mai inserite
    fp = sum(key in f for key in tests) / len(tests)
    print(f"{bits_per_key:>10} {k:>3} {fp:>24.4f} {(1 - math.exp(-k * n / m)) ** k:>16.4f} {false_neg:>15}")

# Output:
# bit/chiave   k  falsi positivi misurati  (1-e^(-kn/m))^k  falsi negativi
#          5   3                   0.0914           0.0918               0
#         10   7                   0.0078           0.0082               0
#         10   3                   0.0169           0.0174               0
#         10  14                   0.0182           0.0190               0
#         15  10                   0.0007           0.0007               0

La colonna dei falsi negativi è zero in ogni riga, come deve essere per costruzione. I falsi positivi coincidono con la formula entro l'ordine del decimo di punto: 9,1% contro 9,2% con 5 bit per chiave e k = 3, 0,78% contro 0,82% con 10 bit e k = 7. A parità di memoria (10 bit per chiave) il numero di hash conta: k = 7 dà 0,78%, mentre k = 3 e k = 14 danno 1,7% e 1,8%, cioè più del doppio. Il valore migliore di k è circa (m/n)·ln 2, che per 10 bit per chiave è 6,9: la misura lo conferma, ed è il motivo per cui con 15 bit per chiave si scende allo 0,07%. L'articolo originale di Bloom (Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, 1970) è la fonte della struttura: l'ho citato dopo aver verificato i metadati, non letto il testo.

Quale ricerca scegliere

• Ricerca lineare: nessun requisito sull'ingresso, n confronti nel caso peggiore; va bene per liste corte o per ricerche rare.
• Ricerca binaria: richiede un ingresso ordinato, ⌊log₂ n⌋ + 1 sonde; va bene quando cerchi molte volte in dati che cambiano di rado, e fornisce anche il punto di inserimento.
• Tabella hash: nessun ordine, costo atteso costante con α limitato, ma memoria aggiuntiva, ridimensionamenti con picchi e nessun ordinamento delle chiavi.
• Filtro di Bloom: pochi bit per chiave, nessun falso negativo e una probabilità di falsi positivi calcolabile, ma non restituisce il valore e non permette la cancellazione.

La scelta non dipende da quale sia «più veloce» ma da che cosa ti serve oltre al sì o no: l'ordine delle chiavi (che la tabella hash non conserva), l'intervallo di valori vicini (che solo la lista ordinata offre), o la garanzia di non ammettere falsi negativi con memoria minima (che solo il filtro dà). Se i dati cambiano di continuo e ti serve anche l'ordine, la struttura giusta non è nessuna di queste ma un albero bilanciato, protagonista dell'articolo su BST e AVL.

Esercizi

1. Scrivi la ricerca binaria per l'ultima occorrenza di un valore duplicato e verifica la tua funzione contro bisect_right.
2. Nel listato della tabella con liste prova una funzione hash k % 8 con chiavi che sono tutte multipli di 8 e misura i confronti medi.
3. Aggiungi la cancellazione all'indirizzamento aperto e spiega perché svuotare la cella rompe le ricerche successive.
4. Per un filtro con 10.000 chiavi e un obiettivo di falsi positivi dell'1%, ricava m e k dalla formula e verificali con il listato.

Il terzo esercizio è quello più istruttivo: nell'indirizzamento aperto una cella vuota significa «la catena finisce qui», e se la cancellazione la svuota senza lasciare un segno (una lapide) le chiavi inserite dopo la collisione diventano irraggiungibili. È la ragione per cui quasi tutte le implementazioni reali usano lapidi o ridisegnano il blocco.

Domande frequenti

Una tabella hash è davvero O(1)?

Lo è in media, se la funzione hash distribuisce bene le chiavi e il fattore di carico resta limitato; con una funzione che manda tutte le chiavi nello stesso secchio il costo di una ricerca diventa lineare, come mostra l'esperimento con la funzione costante.

Perché la ricerca binaria richiede una lista ordinata?

Perché a ogni passo scarta metà dell'intervallo basandosi sull'ordine; senza ordine la scelta di quale metà scartare è casuale, e su liste non ordinate il listato ha perso un elemento presente 1.522 volte su 2.000.

Un filtro di Bloom può sbagliare?

Solo in un verso: può dire «forse presente» per una chiave mai inserita (falso positivo, con probabilità calcolabile), ma non dice mai «assente» per una chiave inserita.

Che cosa sai fare adesso

Sai scrivere una ricerca binaria partendo dalla sua invariante e sai dove si rompe: lista non ordinata e somma degli indici a 32 bit. Sai misurare il costo di una tabella hash in confronti o sonde e confrontarlo con 1 + α/2, con le formule dell'indirizzamento aperto e con il costo del ridimensionamento; sai anche quando il costo costante smette di essere vero. Hai visto un filtro di Bloom funzionare e sai ricavare la probabilità dei falsi positivi. Nell'articolo successivo, liste, stack, queue e deque, passi alle strutture che queste ricerche hanno dato per scontate.

Nella stessa serie trovi anche il riepilogo sulla programmazione dinamica.