Un ago in un pagliaio nell'informatica

La via lenta: guardare tutto

Se non sai nulla su dove si trovi l'ago, l'unica scelta è controllare ogni pezzo di fieno finché non lo trovi. In informatica si chiama ricerca lineare. In media controlli metà di tutto prima di riuscire e, nel caso peggiore, tutto. Funziona sempre, ma il tempo cresce in proporzione alle dimensioni del mucchio.

Ordinare cambia tutto

Immagina ora che il fieno fosse disposto in ordine, come le parole di un dizionario. Un metodo più furbo, la ricerca binaria, apre a metà, decide in quale metà si trova la risposta e scarta l'altra. Ripetendo, un milione di elementi si esamina in circa 20 passaggi. Il trucco è che il mucchio deve essere già in ordine, e un pagliaio non lo è mai.

Gli indici: barare preparandosi

Database e motori di ricerca aggirano il problema facendo il lavoro duro in anticipo. Costruiscono un indice, come l'elenco in fondo a un libro che ti dice a che pagina si trova una parola. Cercare diventa rapido perché il tempo è stato speso prima. Non esiste un indice per un vero pagliaio, ed è esattamente per questo che esiste il modo di dire.

Seguire un segnale

Un metal detector è diverso. Non ti dice dove sia l'ago, ma se ti stai avvicinando. Immagina un numero che sale man mano che ti avvicini. Puoi allora usare una regola semplice: fai un passo, guarda se il segnale è cresciuto e continua nella direzione che lo migliora. I programmatori chiamano una versione di questo hill climbing (salita sulla collina), e sta dietro molte ottimizzazioni pratiche.

Nel gioco, il segnale è calcolato dalla tua distanza dal pezzo di metallo più vicino rispetto alla portata del detector. I bip si fanno più rapidi quando quel numero si avvicina a 1, così il tuo orecchio fa la salita sulla collina al posto tuo. Altro in Come funziona il metal detector.

Quando i segnali falliscono

L'hill climbing può bloccarsi. Se c'è molto metallo di scarto vicino all'ago, il segnale più forte può portarti a un chiodo. Il gioco lo risolve dando ai detector di livello alto la capacità di distinguere l'ago. Le ricerche reali incontrano lo stesso problema e usano sensori migliori o filtri aggiuntivi.

Il pagliaio come dati

Il pagliaio nel gioco è esso stesso una struttura dati: una griglia di 88 per 40 per 88 celle, ciascuna con un numero per la densità del fieno. Scavare significa cambiare numeri, e chunk da 16 celle mantengono il lavoro piccolo. Come funziona è in Come funziona il pagliaio.