Due clip audio occupano uno stesso campione?
Un editor audio segnala che due clip sono separate. Eppure, ingrandendo la traccia, si vede che la clip più breve cade tutta dentro la più lunga. Il programma ha restituito un risultato plausibile e ha concluso il calcolo senza segnalare errori. Come possiamo stabilire dove ha sbagliato e costruire un test che riconosca il difetto anche dopo una modifica al codice?
Stabilire che cosa conta come risposta corretta
Consideriamo la linea temporale di una traccia digitale. Numeriamo i campioni a partire da zero. Per descrivere una clip scriviamo [inizio, fine). La parentesi quadra include l’inizio, quella tonda esclude la fine. La clip [2, 5) occupa quindi i campioni 2, 3 e 4. La posizione 5 è il confine dal quale può cominciare la clip successiva.
La richiesta è precisa. Date due clip non vuote sulla stessa linea temporale, la funzione deve terminare e rispondere sì se e solo se esiste almeno un indice di campione occupato da entrambe. Gli estremi sono interi non negativi e ogni inizio precede la rispettiva fine. Per decidere la sovrapposizione bastano le posizioni. Anche un campione silenzioso occupa il proprio posto nella traccia.
In questo esempio, dire che l’algoritmo è corretto significa impegnarsi su ogni coppia di clip ammessa. Il caso [4, 4) è escluso perché la clip sarebbe vuota. Se l’applicazione deve accettare anche marcatori di durata zero, occorre specificare il loro comportamento e aggiungere i relativi test.
Un errore logico che i primi test lasciano passare
Chiamiamo A la prima clip e B la seconda. Una prima soluzione controlla se il primo oppure l’ultimo campione di B cade in A. L’idea sembra funzionare quando le clip si incrociano da un lato. Per A = [2, 5) e B = [4, 7), il primo campione di B è 4 e appartiene ad A. La funzione risponde correttamente sì. Per due clip lontane risponde altrettanto correttamente no.
Ora proviamo A = [1, 2) e B = [0, 3). Il primo campione di B è 0 e l’ultimo è 2. Entrambi cadono fuori da A. La funzione risponde no. Basta però scrivere i campioni su carta: A contiene 1 e B contiene 0, 1 e 2. Il campione 1 appartiene a entrambe. Questo è un falso negativo.
Il difetto riguarda il ragionamento. Trovare un estremo di B dentro A è una condizione sufficiente per rispondere sì. Trattarla anche come condizione necessaria fa perdere il caso in cui B avvolge A. Scambiando l’ordine delle stesse due clip, la funzione cambia risposta: un ulteriore indizio, perché condividere un campione è una relazione simmetrica.
Scegliere prove che distinguano i comportamenti
Scriviamo il risultato atteso prima di eseguire il programma. Qui possiamo ottenerlo elencando a mano i campioni comuni. Questo criterio indipendente è l’oracolo di test. Copiare nel test la stessa regola degli estremi farebbe coincidere due risposte sbagliate.
Casi di prova calcolati sulla stessa traccia| Situazione | Clip A | Clip B | Campioni comuni | Atteso | Prima soluzione |
|---|---|---|---|---|---|
| Separate da un campione libero | [0, 1) | [2, 4) | Nessuno | No | No |
| Fine e inizio coincidono | [0, 2) | [2, 4) | Nessuno | No | No |
| Un solo campione comune | [0, 3) | [2, 4) | 2 | Sì | Sì |
| A interamente dentro B | [1, 2) | [0, 3) | 1 | Sì | No |
| Stesse clip, ordine inverso | [0, 3) | [1, 2) | 1 | Sì | Sì |
| Due clip identiche e minime | [3, 4) | [3, 4) | 3 | Sì | Sì |
Confronta la seconda e la terza riga. Si sposta di una sola posizione la fine di A, da 2 a 3. Quel passo trasforma un semplice contatto in una sovrapposizione. È ciò che rende informativo un caso limite: una variazione minima dell’ingresso attraversa il confine tra due risposte previste. Le due righe sul contenimento controllano invece una proprietà diversa, la simmetria.
Correggere la regola e spiegare perché vale
Qual è il primo campione che potrebbe appartenere a entrambe? È il più tardo fra i due inizi. Chiamiamolo p. Il primo confine che impedisce di proseguire è la più precoce fra le due fini. Chiamiamolo q. Esiste almeno un campione comune esattamente quando p < q.
def si_sovrappongono(inizio_a, fine_a, inizio_b, fine_b):
primo_comune = max(inizio_a, inizio_b)
fine_comune = min(fine_a, fine_b)
return primo_comune < fine_comune
Se p è minore di q, p stesso è un indice intero compreso in entrambe le clip: abbiamo trovato il campione richiesto. Se p è uguale o superiore a q, qualunque candidato dovrebbe essere insieme almeno p e strettamente minore di q, due condizioni incompatibili. Il calcolo esegue un numero fisso di confronti e termina. Questo ragionamento copre tutte le coppie ammesse dalla specifica.
Che cosa attestano cento test
Possiamo anche controllare il codice su un piccolo dominio completo. Usando gli estremi 0, 1, 2, 3 e 4 si formano dieci clip non vuote e cento coppie ordinate. Per ciascuna coppia abbiamo confrontato entrambe le versioni con un oracolo che costruisce i due insiemi di campioni e ne calcola l’intersezione. La prima versione sbaglia 5 casi su 100. La versione corretta concorda con l’oracolo in tutti e 100.
I cinque errori corrispondono a contenimenti stretti di A dentro B. Quel conteggio descrive il piccolo dominio enumerato. Per estremi arbitrariamente grandi, la garanzia viene dal ragionamento su p e q. I due controlli hanno scopi complementari: uno verifica il codice effettivamente eseguito sui dati scelti, l’altro giustifica la regola generale.
Conservare l’errore come test di regressione
Una volta corretto il difetto, conserviamo il caso che lo ha rivelato. Aggiungiamo il caso adiacente alla frontiera per intercettare un’altra modifica possibile.
assert si_sovrappongono(1, 2, 0, 3) assert not si_sovrappongono(0, 2, 2, 4) assert si_sovrappongono(0, 3, 2, 4)
Prova a sostituire l’ultimo confronto della funzione con <=. Quale test fallisce? Il secondo: le due clip si toccano alla posizione 2, ma la prima termina prima di occuparla. Il primo test continuerebbe a passare. Conservare entrambi i casi permette di riconoscere due errori diversi, anche quando il programma continua a produrre risposte sensate a prima vista.
