Steve Nadis su Quanta Magazine spiega un nuovo algoritmo per stimare il numero di elementi unici di una lista.

Il problema è semplice:

Immaginate di essere spediti in una foresta pluviale incontaminata, per effettuare un censimento della fauna selvatica. Ogni volta che vedete un animale, scattate una foto. Il vostro apparecchio terrà traccia del numero totale di scatti, ma a voi interessa solo il numero di animali unici, tutti quelli che non avete ancora contato. Qual è il modo migliore per ottenere questo numero?

La risposta ingenua è di munirsi di taccuino e aggiungere solo i nuovi animali. Ma con una lista composta da miliardi di elementi (pensiamo agli accessi ad un sito molto frequentato), i requisiti di memoria e tempo diventano sempre più grandi.

Ci vuole una stima, e «stima dei valori univoci in una lista» è un problema studiatissimo. Tre informatici (Sourav Chakraborty, Vinodchandran Variyame e Kuldeep Meel) hanno fatto un passo avanti. I ricercatori hanno sviluppato un nuovo algoritmo chiamato CVM per approssimare il numero di elementi distinti in un lungo elenco. Questo metodo richiede di ricordare solo un piccolo numero di voci e soprattutto — la novità del lavoro — è molto facile da implementare e spiegare per chi ha delle conoscenze basilari di probabilità.

Nadis prende come modello l’Amleto:

Torniamo all’Amleto, ma questa volta la vostra memoria di lavoro — costituita da una lavagna — ha spazio per sole 100 parole. Una volta iniziata la rappresentazione, scrivete le prime 100 parole che sentite, saltando ancora una volta le ripetizioni. Quando lo spazio è esaurito, premete pausa e lanciate una moneta per ogni parola. Se è testa, la parola rimane nell’elenco; se è croce, eliminatela. Dopo questa fase preliminare, rimarranno circa 50 parole distinte.

L’algoritmo continua aggiungendo e togliendo parole dalla lista — sempre con l’ausilio di una moneta — in varie riprese dove sarà sempre più difficile per una parola rimanere nell’elenco. Il risultato:

Alla fine dell’n-ismo turno, si giungerà al termine dell’Amleto. Lo scopo della procedura è stato quello di garantire che ogni parola, in virtù delle selezioni casuali effettuate, abbia la stessa probabilità di essere presente: ½ᵏ.

L’Amleto ha precisamente 3.967 parole e la stima CVM con memoria di cento elementi si avvicina molto al numero esatto.

«Questo è un ottimo esempio di come, anche per problemi molto elementari e ben studiati, ci siano a volte soluzioni molto semplici ma non ovvie che aspettano ancora di essere scoperte», ha dichiarato William Kuszmaul dell’Università di Harvard.