Cerca le voci dell'elenco da un altro elenco, modo migliore?

Question

Cerca le voci dell'elenco da un altro elenco, modo migliore?

#1 da (3 voti)

0

Oggi devo cercare gli elementi della lista da un'altra lista individualmente. Sto solo pensando ad un approccio migliore. Di seguito è descritto lo scenario.

Diciamo che ho due array, arr1 con 100 elementi (potrebbe avere voci duplicate) e arr2 con 1000 elementi unici. ora ho bisogno di trovare elementi di arr1 da arr2 ed eseguire qualche azione su di esso. Dovrei scorrere tra gli elementi arr1 e poi cercarli in arr2 ed eseguire l'azione desiderata. o iterare su arr2 e cercare i suoi elementi da arr1 e, se trovato, eseguire l'azione desiderata sull'elemento arr2. quale sarà il modo efficace? La scelta ovvia sembra essere la prima, ma volevo confrontare i suoi vantaggi (dis) rispetto all'altra.

Secondo me entrambi saranno quasi gli stessi.

algorithms list search

posta Kashif 27.04.2016 - 10:24

fonte

1 risposta

Leggi altre domande sui tag algorithms list search

Quando si applicano prestazioni e memoria profiler? [chiuso] Determina l'ordine di esecuzione in base alla definizione dichiarativa?

score 3 · Answer 1

Se si fa riferimento alla dimensione di arr1 come dimensione di m e di arr2 come n, e assumendo che per "ricerca" si intenda una semplice ricerca lineare, allora l'algoritmo di forza bruta naive che si sta descrivendo richiederà O (nm) di tempo. È vero che l'array su cui si esegue l'iterazione non ha alcun effetto su questo; stai solo scegliendo tra n iterazioni di una ricerca di O (m) contro m iterazioni di una ricerca di O (n).

Il modo più ovvio per farlo più rapidamente di O (nm) è non usare affatto ricerche lineari, ma pre-processare arr1 per rendere possibili ricerche più veloci . L'opzione di gran lunga più semplice è quella di ordinare arr1 all'inizio e quindi utilizzare le ricerche binarie, che dovrebbero portare la ricerca completa a O (n * log (m)), quindi inizierei con quello. Se anche questo non fosse abbastanza, allora guarderei nelle tabelle hash. Data una funzione di hash ideale (che a seconda dei dati potrebbe essere difficile o addirittura impossibile), potrebbe teoricamente ottenere la ricerca completa in O (m + n) ammortizzata.

A proposito, i confronti 100 * 1000 non sono nulla su un computer moderno. Assicurati che questo codice causi effettivamente problemi di prestazioni prima di provare a ottimizzarlo.