Esercizio 20duplicati vicini con una mappa

Soluzione banale

Per ogni $i$ confrontare $A[i]$ con $A[i+1], \dots, A[i+k]$: $\Theta(nk)$ confronti, quindi $\Theta(n^2)$ se $k$ è vicino a $n$. Si può fare meglio ricordando, per ogni valore, dove è stato visto per ultimo.

(a) Idea

Si scorre l'array da sinistra a destra con una mappa (vedi Mappe e dizionariADT mappa (chiavi distinte) con get, put, remove, keySet/values/entrySet; famiglia mappa/mappa ordinata/dizionario (multimappa); applicazioni; implementazioni semplici ma poco efficienti (lista, array indicizzato dalle chiavi); dizionario realizzato con una mappa di liste.Mappe e dizionari →) che associa a ogni valore già incontrato l'indice della sua ultima occorrenza. All'indice $i$:

• se $A[i]$ non è nella mappa, lo si inserisce con valore $i$;
• se $A[i]$ è nella mappa con ultimo indice $j$: se $i - j \le k$ si restituisce true; altrimenti si aggiorna l'indice a $i$ (le occorrenze future saranno più vicine a $i$ che a $j$, quindi $j$ non serve più).

Basta guardare l'ultima occorrenza: se esiste una coppia vicina con valore $x$, in particolare lo sono due occorrenze consecutive di $x$.

Esempio $A = [4, 7, 2, 5, 7, 9]$ (indici da $0$), $k = 3$. Le prime quattro iterazioni inseriscono $4 \mapsto 0$, $7 \mapsto 1$, $2 \mapsto 2$, $5 \mapsto 3$. All'indice $4$ il valore $7$ è già nella mappa con indice $1$ e $4 - 1 = 3 \le 3$: l'algoritmo restituisce true. Con $k = 2$ la stessa istanza restituirebbe false: all'indice $4$, $4 - 1 = 3 > 2$, si aggiorna $7 \mapsto 4$ e l'indice $5$ ($9$) non è nella mappa.

(b) Pseudocodice

Algoritmo hasNearbyDuplicate(A, k)
Input: array A[0..n-1] di interi, intero k >= 1
Output: true se esistono i != j con A[i] = A[j] e |i - j| <= k, false altrimenti
M <- mappa vuota                                 (chiave: valore di A; valore: ultimo indice)
for i <- 0 to n-1 do
    j <- M.get(A[i])                             (null se A[i] non è in M)
    if j != null AND i - j <= k then return true
    M.put(A[i], i)                               (inserisce o aggiorna con l'indice più recente)
return false

Correttezza. Invariante: all'inizio dell'iterazione $i$, per ogni valore $x$ comparso in $A[0..i-1]$, $M[x]$ è l'indice dell'ultima occorrenza di $x$ in $A[0..i-1]$, e nessuna coppia di occorrenze vicine esiste in $A[0..i-1]$. Se esiste una coppia vicina $(j, i)$ con $A[j] = A[i]$ e $j < i$ minima, l'occorrenza di $A[i]$ immediatamente precedente $i$ è anche vicina (è a distanza $\le i - j \le k$) e $M[A[i]]$ la contiene: viene trovata.

(c) Complessità

Il ciclo ha $n$ iterazioni, ciascuna con un get e un put sulla mappa. Con una tabella hash (vedi Tabelle hashTabella hash per implementare una mappa: funzione hash = hash code + compression function, bucket array, separate chaining; hash code per numeri e stringhe (polynomial, cyclic shift), division e MAD; load factor, complessità al caso pessimo Theta(n) e medio O(1+lambda), rehashing; esempio svolto con inserimenti e collisioni.Tabelle hash →) ogni operazione costa $\Theta(1)$ in media (hashing uniforme, $\lambda$ costante), quindi:

• caso medio: $\Theta(n)$;
• caso pessimo: ogni operazione può costare $O(m)$ con $m \le n$ chiavi presenti (collisioni), quindi $O(n^2)$.

Lo spazio è $O(n)$ (al più un'entry per valore distinto). Il tempo non dipende da $k$.

(d) Altre implementazioni della mappa

L'albero bilanciato dà una garanzia deterministica $O(n \log n)$ (utile se non ci si fida delle collisioni); la hash è più veloce in pratica. Un'alternativa che non usa la mappa, per $k$ piccolo, è mantenere una finestra degli ultimi $k$ elementi. (Algoritmo verificato su 3000 coppie casuali $(A, k)$ confrontandolo con il controllo di tutte le coppie.)

Errori comuni

• Controllare solo l'uguaglianza dei valori senza confrontare gli indici: restituirebbe true per qualunque duplicato.
• Non aggiornare l'indice quando la distanza supera $k$: poi le occorrenze successive vengono confrontate con un indice troppo vecchio. Esempio: $A = [5, 8, 9, 5, 5]$ con $k = 1$ deve dare true (gli ultimi due $5$ sono adiacenti); senza aggiornare, il $5$ in posizione $3$ non sostituisce quello in posizione $0$ e in posizione $4$ si confronta $4 - 0 = 4 > 1$: risposta sbagliata false.
• Dichiarare $\Theta(n)$ al caso pessimo con la hash: il caso pessimo è quadratico, lineare in media.
• Usare una struttura ordinata (albero) senza dire che le chiavi, interi, sono ordinabili.