Ricerca inefficiente su molti strumenti

Questa lezione appartiene al Modulo 19 — Prestazioni e manutenzione.

Il problema concreto

Ogni volta che si cerca uno strumento per ID, si fa qualcosa del genere:

function trovaPerId(lista, id) {
  return lista.find(s => s.id === id) ?? null;
}

Questa è una ricerca lineare — in media esamina metà della lista. Se la lista ha 10 strumenti, esamina circa 5. Se ne ha 1000, ne esamina circa 500.

Il costo cresce linearmente con la dimensione: O(n).

In un laboratorio scolastico con 30-50 strumenti, questo non è un problema. Ma capire perché non è un problema — e quando lo diventerebbe — è il punto di questa lezione.

Dove avvengono le ricerche nel Registro

Ogni operazione del Registro fa almeno una ricerca:

registraPrestito    → trovaPerId(strumenti, strumentoId)         ← O(n)
chiudiPrestito      → trovaPerId(prestiti, prestitoId)           ← O(n)
apriSegnalazione    → trovaPerId(strumenti, strumentoId)         ← O(n)
cercaStrumenti      → strumenti.filter(s => match(s, filtri))    ← O(n)
verificaCoerenza    → prestitiAperti.filter(p => ...)            ← O(n)

Cinque operazioni, tutte O(n). Con 50 strumenti, ogni operazione esamina al massimo 50 elementi — irrilevante per un browser moderno.

Quando diventa un problema reale

Facciamo i conti per un contesto diverso:

Laboratorio piccolo (50 strumenti):
  trovaPerId esamina al max 50 elementi → < 1 ms → irrilevante

Magazzino scolastico (500 strumenti):
  trovaPerId esamina al max 500 elementi → < 1 ms → ancora irrilevante

Inventario regionale (50.000 strumenti):
  trovaPerId esamina al max 50.000 elementi → qualche ms → comincia a sentirsi
  cercaStrumenti con filtri complessi → decine di ms → percepibile

E-commerce (5.000.000 articoli):
  trovaPerId → secondi → inaccettabile

Per il Registro del laboratorio scolastico: la ricerca lineare è corretta e non va ottimizzata. Il laboratorio avrà al massimo qualche centinaio di strumenti.

Come si misura prima di ottimizzare

Se si volesse verificare sperimentalmente:

// Misura il tempo di una ricerca su liste di dimensioni diverse
function misuraTempo(n) {
  // Genera una lista di n strumenti finti
  const lista = Array.from({ length: n }, (_, i) => ({
    id: `str-${i}`,
    nome: `Strumento ${i}`,
    categoria: "Test",
    stato: "disponibile"
  }));

  // Cerca sempre l'ultimo elemento (caso peggiore)
  const idCercato = `str-${n - 1}`;

  const inizio = performance.now();
  lista.find(s => s.id === idCercato);
  const fine = performance.now();

  return fine - inizio;
}

console.log("10 strumenti:   ", misuraTempo(10).toFixed(3), "ms");
console.log("100 strumenti:  ", misuraTempo(100).toFixed(3), "ms");
console.log("1000 strumenti: ", misuraTempo(1000).toFixed(3), "ms");
console.log("10000 strumenti:", misuraTempo(10000).toFixed(3), "ms");

Eseguendo questo nel browser del laboratorio, si vede che fino a 10.000 strumenti il tempo è inferiore a 1 ms. La ricerca lineare non è il collo di bottiglia.

Quando l’ottimizzazione avrebbe senso

Se il Registro crescesse a migliaia di strumenti, la soluzione sarebbe usare una Map invece di un array:

// Invece di un array con find() O(n):
const listaStrumenti = [{ id: "s1", nome: "Trapano" }, ...];
const trovato = listaStrumenti.find(s => s.id === id); // O(n)

// Si usa una Map con lookup O(1):
const indiceStrumenti = new Map(listaStrumenti.map(s => [s.id, s]));
const trovato = indiceStrumenti.get(id); // O(1) — costante indipendentemente dalla dimensione

Ma attenzione: la Map ha un costo di costruzione (O(n) per popolarla) e un costo di memoria aggiuntivo. Va usata solo se il guadagno di prestazioni è misurabile e necessario.

Regola: non ottimizzare finché non hai misurato che c’è un problema reale.

La ricerca su testo libero — caso speciale

La ricerca per nome con .includes() è O(n × m) dove m è la lunghezza del termine cercato:

function cercaPerNome(strumenti, query) {
  return strumenti.filter(s =>
    s.nome.toLowerCase().includes(query.toLowerCase())
  );
}

Per 50 strumenti con nomi di ~20 caratteri: 50 × 20 = 1000 operazioni per query. Ancora irrilevante.

Per implementazioni di ricerca full-text su grandi dataset si userebbero indici dedicati (ElasticSearch, Meilisearch) — fuori scope per un laboratorio scolastico.

Analisi delle prestazioni del tuo Registro

Esercizio: identifica le tre operazioni più frequenti nel Registro e stima il loro costo.

Operazione più frequente: cercaStrumenti (ogni volta che si digita nel filtro)
  - Struttura dati usata: array
  - Complessità: O(n × m) con filtro testo
  - Numero medio di strumenti: ~30-50
  - Costo stimato: < 1 ms → accettabile

Operazione meno frequente: chiudiPrestito (poche volte al giorno)
  - Struttura dati usata: array
  - Complessità: O(n)
  - Numero medio di prestiti: ~5-10
  - Costo stimato: < 0.1 ms → irrilevante

Procedura guidata

1. Identifica le operazioni che eseguono ricerche nel tuo Registro.
2. Stima il numero massimo di elementi che la lista conterrà nel contesto scolastico.
3. Usa performance.now() per misurare il tempo di una ricerca sul caso peggiore.
4. Documenta: “la ricerca è accettabile / è un problema / andrebbe ottimizzata quando…”.
5. Non ottimizzare se il tempo è sotto 10 ms per il caso d’uso reale.

Attività in classe

## Analisi ricerca nel mio Registro

Operazione analizzata:

Struttura dati usata (array / Map / altro):

Numero stimato di elementi nel contesto reale:

Tempo misurato con performance.now() (caso peggiore):

Conclusione: ricerca accettabile / potrebbe diventare un problema se [condizione]:

Ottimizzazione applicata (sì/no):
  Se no, perché no:
  Se sì, cosa ho fatto:

Spiegazione guidata per studiare

La ricerca inefficiente è uno dei problemi di prestazioni più comuni nel codice. Ma nel contesto del Registro del laboratorio scolastico, non è un problema — perché la dimensione dei dati è piccola e le operazioni sono rare.

Il punto centrale è: l’inefficienza è relativa alla scala. Una ricerca O(n) su 50 elementi è più veloce di una ricerca O(1) che richiede la costruzione di un indice su 5 elementi. Ottimizzare senza misurare spesso peggiora il codice (più complesso, più difficile da mantenere) senza migliorare le prestazioni percepibili.

Il rischio tipico è ottimizzare in anticipo perché “si sa” che sarà lento. Il principio corretto è: misura prima, ottimizza dopo — e solo se il problema è reale e percepibile.

Passo per passo nel progetto

1. Identifica la ricerca più frequente nel tuo Registro (probabilmente trovaPerId o cercaStrumenti).
2. Aggiungi console.time / console.timeEnd attorno alla chiamata.
3. Usa il Registro normalmente per un minuto — guarda i tempi in console.
4. Sono sotto 10 ms? Non c’è nulla da ottimizzare.
5. Sono sopra 100 ms? Hai trovato un collo di bottiglia reale da analizzare.

Esempio da leggere lentamente

// Misura il costo reale della ricerca nel Registro reale
function trovaPerId(lista, id) {
  console.time(`trovaPerId(${id})`);
  const risultato = lista.find(s => s.id === id) ?? null;
  console.timeEnd(`trovaPerId(${id})`);
  return risultato;
}

// Se il log mostra: "trovaPerId(str-042): 0.003 ms"
// → non c'è nessun problema di prestazioni da risolvere

Prova di comprensione

• Quanti strumenti ha il tuo laboratorio? La ricerca lineare è un problema a quella scala?
• Qual è la differenza di costo tra find() su array e get() su Map?
• Quando useresti una Map invece di un array nel Registro?

Errori da evitare

• ottimizzare la ricerca prima di misurarla — il “problema” potrebbe non esistere;
• usare strutture dati complesse (Map, Set) quando un array è sufficiente;
• misurare in laboratorio (2 strumenti) e fare proiezioni per milioni di elementi senza contesto;
• confondere complessità teorica (O(n)) con prestazioni percepibili (ms reali).

Prodotto da consegnare

Può essere:

• la misurazione con performance.now() di una ricerca sul Registro reale, documentata;
• l’analisi delle tre operazioni più frequenti con stima del costo;
• una nota nel README: “la ricerca è accettabile per N strumenti — il collo di bottiglia sarebbe [X] se il numero crescesse a [Y]”.

Checklist di chiusura

• Ho identificato le operazioni di ricerca nel mio Registro
• Ho stimato il numero massimo di elementi nel contesto scolastico
• Ho misurato il tempo di almeno una ricerca con performance.now()
• Ho concluso se la ricerca è accettabile o no (con motivazione)
• Non ho ottimizzato senza una misurazione che mostrasse un problema reale

Domande per la revisione

• Il tuo Registro ha un problema di prestazioni reale? Come lo sai?
• Se il laboratorio crescesse a 500 strumenti, quale ricerca diventerebbe lenta per prima?
• Come distingui “inefficiente” da “lento”?

Risultato atteso

Alla fine lo studente deve saper dire:

Nel mio Registro, la ricerca più frequente è [operazione].
Ha una complessità O(n) su una lista di [N] strumenti.
Ho misurato: [X] ms — accettabile / non accettabile.
[Se ottimizzato]: ho usato [struttura] perché [motivazione basata sulla misura].
[Se non ottimizzato]: non ho ottimizzato perché il costo è accettabile per il contesto.

Se questa spiegazione non è possibile, la lezione non è ancora davvero conclusa.