Come faccio a trovare un ago in un pagliaio?
Di cosa si parla
La magia dell’algoritmo di Google per interrogare una mole gigantesca di dati in un baleno.
Incipit
Quali sono le domande più frequenti che gli italiani hanno posto a Google nel 2015 nella forma di “Come fare…”? Questa è la top-ten ufficiale.
Cercare i valori comuni a due insiemi (come, ad esempio, due insiemi di pagine web corrispondenti a due parole in esse contenute). In altre parole, calcolare l’intersezione di due liste di valori, supponendo che i valori delle due liste siano ordinati.
Posizionarsi all’inizio delle due liste. Se i due valori considerati sono uguali, inserire quel valore nel risultato e procedere avanti di una posizione in entrambe le liste. Se i due valori sono diversi, andare avanti nella lista che contiene il valore più piccolo e stare fermi sull’altra. Si continua finché una delle due o tutte e due le liste non hanno più valori da esaminare.
function inter(l1, l2)
o = Int64[]
p1 = 1
p2 = 1
n1 = length(l1)
n2l = length(l2)
while p1<=n1 && p2<=n2
if l1[p1]==l2[p2]
append!(o,l1[p1])
p1 = p1+1
p2 = p2+1
elseif l1[p1]<l2[p2]
p1 = p1+1
else
p2 = p2+1
end
end
return o
end