Elenca le tecniche di confronto per prestazioni più veloci

Il mio suggerimento sarebbe quello di sommergere la lista grande in un set di hash, quindi usarla per abbinare gli elementi della piccola lista.

Un set di hash è una struttura che memorizza elementi in una struttura di memoria indicizzabile, come una matrice, in cui la posizione dell'elemento è uguale a un valore di hash calcolato utilizzando l'oggetto. Ciò significa che cercare un valore nell'hashset è un'operazione relativamente veloce; calcola l'hash dell'oggetto che stai cercando, vai a quell'indice e controlla gli oggetti reali memorizzati lì, che per una buona implementazione sarà un numero molto piccolo (le implementazioni di hashset devono trovare un equilibrio tra la dimensione dell'hash e quindi il numero di elementi di prima dimensione e il numero di collisioni e quindi il numero medio di elementi in ciascun elemento).

Idealmente, gli hash si avvicinano a un tempo di ricerca costante (in particolare è O (log _{2 ^ H} N) dove H è il bit della funzione di hash, quindi per tutti N < 2 ^ H è effettivamente costante), quindi nel complesso, l'algoritmo di corrispondenza si avvicinerebbe alla complessità lineare. Due importanti aspetti negativi sono innanzitutto che, a meno che tu non abbia accesso a un'implementazione efficiente integrata (la HashMap di Java è costruita su questa struttura, come la classe Dictionary di .NET), devi eseguire il rollover che è piuttosto un po 'di codice, e secondo gli hashset sono veri e propri hog della memoria perché ci sono praticamente molti spazi vuoti nell'array a meno che l'implementazione non modifichi la sua funzione di hash basata sulla capacità prevista o effettiva (che potrebbe, se fatta in modo ingenuo, coinvolgere nuovamente ogni elemento diverse volte la prima dimensione viene estesa per limitare la crescita nella seconda dimensione).

Ordina entrambi gli elenchi con un efficiente algoritmo di ordinamento (o assicurati che gli elenchi siano "preordinati" da chiunque / qualunque sia stato creato).

Quindi, se il primo nome in entrambe le liste è lo stesso hai trovato una corrispondenza, altrimenti scartare qualsiasi nome sia "precedente"; e fallo finché uno degli elenchi non è vuoto.

Qualche pseudo-codice grezzo:

    do {
        status = compare(shortList[i], longList[j]);
        if(status == EQUAL) {
            // Found match!
            i++;
            j++;
        } else if(status == EARLIER) {
            // No match, discard first entry in short list
            i++;
        } else {
            // No match, discard first entry in long list
            j++;
        }
    } while( (i < shortListEntries) && (j < longListEntries) );

Ordina la piccola lista con un efficiente algoritmo di ordinamento, attraversa la grande lista e per ogni elemento della lista grande usa una ricerca binaria per scoprire se c'è una voce corrispondente nella piccola lista.

Trovare le cose in un set che corrispondono a quelle di un altro set e unire i dati è qualcosa su cui i database relazionali eccellono. Se questo è qualcosa che devi fare molto, caricare i tuoi elenchi in tabelle nella scelta del DB SQL è probabilmente la scelta migliore.