Qual è il modo più veloce per catalogare la tua libreria? - Chand John

Per vedere la lezione completa: http://ed.ted.com/lessons/what-s-the-fastest-way-to-alphabetize-your-bookshelf-chand-john

Tu lavori nella biblioteca universitaria. Sei nel bel mezzo di un placido pomeriggio quando all'improvviso arriva un carico di 1.280 libri diversi. I libri sono stati consegnati in una singola, lunga fila, ma sono tutti in disordine e il sistema di classificazione automatica è rotto. Come puoi catalogare velocemente i libri? Ce lo spiega Chand John, mostrandoci come gli algoritmi possano aiutare i bibliotecari e i motori di ricerca ad ordinare in breve tempo le informazioni.

Lezione di Chand John, animazioni di Anton Trofimov.

Tu lavori nella biblioteca universitaria.

Sei nel bel mezzo di un placido pomeriggio

quando all'improvviso arriva un carico
di 1.280 libri diversi.

I libri sono stati consegnati
in una singola, lunga fila,

ma sono tutti in disordine,

e il sistema di classificazione
automatica è rotto.

Come se non bastasse,
le lezioni ricominciano domani,

il che vuol dire che di prima mattina

gli studenti si presenteranno in massa
alla ricerca dei loro libri.

Come puoi catalogarli tutti in tempo?

Un modo sarebbe cominciare da un capo
della fila con il primo paio di libri.

Se i primi due sono in ordine,
lasciali come sono.

Altrimenti, scambiali.

Poi guarda il secondo e il terzo libro,

ripeti il procedimento

e continua fino alla fine della linea.

Ad un certo punto arriverai
a quello che dovrebbe essere l'ultimo,

continua a scambiarlo
con i libri seguenti,

facendolo scorrere finché non raggiunge
la fine, il suo posto.

Poi, comincia dall'inizio
e ripeti il procedimento

per mettere a posto
il penultimo libro,

e continua finché tutti i libri
non sono catalogati.

Questo metodo si chiama Bubble Sort.

È semplice ma lento.

Dovresti fare 1.279 confronti
nel primo giro,

poi 1,278 e così via,

per un totale di 818.560 confronti.

Se ogni confronto durasse un secondo,
l'intero processo durerebbe nove giorni.

Una seconda strategia sarebbe di iniziare
a catalogare solo i primi due libri.

Poi prendi il terzo libro e lo confronti
con il libro al secondo posto.

Se deve stare prima del secondo,
scambiali,

poi confrontalo
con il libro al primo posto

e scambiali di nuovo se necessario.

Ora hai catalogato i primi tre libri.

Prosegui aggiungendo un libro alla volta
alla pila già catalogata,

confrontando e scambiando il nuovo libro
con quello che lo precede

finché non si trova al posto giusto
tra i libri finora catalogati.

Questo si chiama Insertion Sort.

A differenza del Bubble Sort, non bisogna
confrontare ciascun paio di libri.

In media, dovremmo solo
confrontare ogni libro

con la metà dei libri che lo precedono.

In questo caso,
il numero totale di confronti

sarebbe 409.280,

e richiederebbe quasi cinque giorni.

Stiamo facendo ancora troppi confronti.

Ecco un'idea migliore.

Prendi un libro a caso.

Questo è il divisorio
e lo confronterai con ogni altro libro.

Poi, dividi la fila

mettendo tutti i libri
prima del divisorio a sinistra

e quello dopo a destra.

Hai appena risparmiato
un sacco di tempo

non confrontando
nessun libro a sinistra

con quelli della destra.

Guardando i libri sulla sinistra,

scegli un altro libro divisorio a caso

e separa i libri che vengono prima
da quelli che vengono dopo.

Continua a creare sotto-divisori così

finché non hai tante mini pile di libri,

ognuna delle quali puoi catalogare
con un'altra strategia, come l'Insertion.

Ogni ciclo di ripartizioni richiede
circa 1.280 confronti.

Se i divisori sono ben equilibrati,

dividere i libri in 128 file di dieci
richiederebbe sette cicli,

o 8.960 secondi.

Catalogare queste sotto-file
richiederebbe 22 secondi circa.

In tutto, questo metodo,
conosciuto come QuickSort,

potrebbe catalogare i libri
in meno di tre ore e mezza.

Ma c'è un inghippo.

I divisori possono essere sbilanciati
e non ti farebbero risparmiare tempo.

Per fortuna, accade raramente.

Ecco perché QuickSort
è una della strategie più efficaci

usata oggi dai programmatori di computer.

È usata ad esempio nei negozi online
per catalogare oggetti in base al prezzo,

o per elencare i benzinai
vicini ad un dato luogo

in base alla distanza.

Nel tuo caso, hai finito
la catalogazione in men che non si dica.

Un'altra giornata
da brividi in biblioteca.