Skip to content
Problemi, algoritmi e coding

Problemi, algoritmi e coding

Le magie dell'informatica

  • Home
  • Capitoli
    • Uno
    • Due
    • Tre
    • Quattro
    • Cinque
  • Errata corrige
  • Oltre il libro
    • Uno
      • Il metodo algoritmico
      • Colora la mappa
      • Colorazione di una mappa: il codice
      • Ordinamento per selezione: il codice
      • Indovina il numero
      • L’algoritmo T3: il codice
      • Ordinamento per fusione: il codice
      • Ricerca esaustiva: il codice
    • Due
      • Le domande a Google
      • Shmoogle
    • Quattro
      • Il metodo dei fattori nascosti: visualizzazione
    • Cinque
      • La macchina di Turing
      • Il gioco dell’imitazione
      • L’algoritmo del percettrone: il codice
      • Lost in translation
      • A proposito di traduttori
    • Video
      • Domande e risposte
      • Errare coding est
  • Il metodo PAC
    • Il rompicapo di Guarini
    • Come funziona il time-lapse
    • Fellini e la crittografia
    • Il problema delle donazioni di reni
  • Lucidi
    • Due
    • Tre
    • Quattro
    • Cinque
  • Parlano di noi
  • Chi siamo
  • Toggle search form

Due

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
Esegui e sperimenta

Copyright © 2025 Problemi, algoritmi e coding.

Powered by PressBook WordPress theme