21
Quale è più veloce trovare un oggetto in una tabella hash o in una lista ordinata?Qual è più veloce trovare un oggetto in una tabella hash o in una lista ordinata?
A
risposta
23
La complessità dell'algoritmo è una buona cosa da sapere, e gli hashtables sono noti per essere 0 (1) mentre un vettore ordinato (nel tuo caso suppongo che sia meglio usare una matrice ordinata di una lista) fornirà 0 (log n) tempo di accesso.
Ma dovresti sapere che la notazione della complessità ti dà il tempo di accesso per N che va all'infinito. Ciò significa che se sai che i tuoi dati continueranno a crescere, la notazione della complessità ti dà qualche suggerimento sull'algoritmo da scegliere.
Quando si sa che i dati manterranno una lunghezza piuttosto bassa: ad esempio, con poche voci nell'array/hashtable, è necessario seguire l'orologio e misurare. Quindi fai un test.
Ad esempio, in un altro problema: l'ordinamento di un array. Per alcune voci bubble sort mentre O (N^2) può essere più veloce di .. l'ordinamento rapido, mentre è (n log n) ..
Inoltre, in base alle altre risposte e in base al proprio elemento, devi provare a trovare la migliore funzione di hash per l'istanza di hashtable. Altrimenti potrebbe portare a prestazioni pessime drammatiche per la ricerca nel tuo hashtable (come sottolineato nella risposta di Hank Gay).
Modifica: Dai un'occhiata a questo articolo per capire the meaning of Big O notation.
7
A meno che l'algoritmo di hashing sia estremamente lento (e/o cattivo), l'hashtable sarà più veloce.
AGGIORNAMENTO: Come i commentatori hanno sottolineato, si potrebbero anche ottenere prestazioni degradate da troppe collisioni non perché l'algoritmo hash è cattivo ma semplicemente perché la tabella hash non è abbastanza grande. La maggior parte delle implementazioni di libreria (almeno nei linguaggi di alto livello) aumenterà automaticamente il tuo hashtable dietro le quinte, il che causerà una performance più lenta del previsto sull'inserto che fa scattare la crescita, ma se stai facendo da solo, è sicuramente qualcosa considerare.
+3
Anche il tavolo dovrebbe essere abbastanza grande –
+2
Sì! Molto importante - se il tuo hashtable sta ottenendo un sacco di collisioni a causa di un algoritmo di hash male o di una mancanza di spazio, allora le sue prestazioni si deterioreranno sensibilmente! – sanbikinoraion
13
Supponendo che per "elenco ordinato" si intenda "raccolta casuale accessibile a caso". Una lista ha la proprietà che puoi attraversarlo solo elemento per elemento, il che si tradurrà in una complessità O (N).
Il modo più veloce per trovare un elemento in una raccolta indicizzabile ordinata è tramite ricerca N-ary, O (logN), mentre una tabella hash senza collisioni presenta una complessità di ricerca di O (1).
1
In alcuni casi, dipende dalle dimensioni della raccolta (e, in misura minore, dai dettagli di implementazione). Se la tua lista è molto piccola, forse 5-10 elementi, direi che la lista sarebbe più veloce. Altrimenti xtofl ha ragione.
0
HashTable sarebbe più efficiente per la lista contenente più di 10 articoli. Se la lista contiene meno di 10 voci, l'overhead dovuto all'hash algo sarà maggiore.
Nel caso in cui sia necessario un dizionario veloce ma anche necessario mantenere gli articoli in modo ordinato, utilizzare OrderedDictionary. (.Net 2.0 in poi)
4
L'operazione get in un SortedList è O(log n) mentre la stessa operazione e un HashTable è O(1). Quindi, normalmente, lo HashTable sarebbe molto più veloce.Ma questo dipende da una serie di fattori:
- La dimensione della lista
- prestazioni dell'algoritmo di hash
- numero di collisioni/qualità del algoritmo di hashing
3
Dipende interamente sulla quantità di dati che hai memorizzato.
Supponendo di avere memoria sufficiente per lanciarlo (quindi la tabella hash è abbastanza grande), la tabella hash individuerà i dati di destinazione in un intervallo di tempo fisso, ma la necessità di calcolare l'hash aggiungerà alcuni (anche riparato) overhead.
La ricerca in un elenco ordinato non avrà quell'overhead, ma il tempo necessario per eseguire il lavoro di localizzazione effettiva dei dati di destinazione aumenterà con l'aumentare dell'elenco.
Quindi, in generale, una lista ordinata sarà generalmente più veloce per i piccoli set di dati. (Per insiemi di dati estremamente piccoli che vengono frequentemente modificati e/o ricercati di rado, un elenco ordinato unificato può essere ancora più veloce, poiché evita il sovraccarico di fare l'ordinamento.) Come il set di dati diventa grande, la crescita della lista il tempo di ricerca oscura il sovraccarico fisso dell'hashing e la tabella hash diventa più veloce.
Il punto di interruzione varia in base alla tabella hash specifica e alle implementazioni di ricerca elenco di ordinamento. Esegui test e benchmark delle prestazioni su un numero di set di dati di dimensioni standard per vedere quali effettivamente funzioneranno meglio nel tuo caso particolare. (Oppure, se il codice funziona già "abbastanza velocemente", non farlo. Usa semplicemente il metodo che preferisci e non preoccuparti di ottimizzare qualcosa che non deve essere ottimizzato.)
Problemi correlati
- 1. Girando una lista non ordinata in una tabella di contenuti
- 2. Cos'è un modo veloce e pitonioso/pulito per rimuovere una lista ordinata da un'altra lista ordinata in python?
- 3. Il modo più veloce per trovare un elemento in una lista?
- 4. Qual è l'algoritmo più veloce per trovare un elemento con più alta frequenza in una matrice
- 5. Qual è il modo più veloce per analizzare una stringa JSON in una tabella SQLite?
- 6. Quale è più veloce in ruby: una ricerca hash o una funzione con un'istruzione case?
- 7. numpy.max o max? Qual è più veloce?
- 8. Tabella hash più veloce in C# rispetto al C++?
- 9. Come verificare se un oggetto di database in Oracle è una tabella o una vista
- 10. Conversione di un oggetto letterale in una matrice ordinata
- 11. Trovare prima istanza di una lista in una seconda lista
- 12. Java Array Sort: modo veloce per ottenere una lista ordinata di indici di un array
- 13. Qual è il modo più efficiente per eseguire una riduzione ordinata in PySpark?
- 14. Alla ricerca di una funzione hash veloce
- 15. Come inserire un elemento in una lista concatenata ordinata con una complessità a tempo costante?
- 16. Trovare una sottostringa in un oggetto NSString
- 17. Come creare una tabella hash
- 18. Perché l'elaborazione di una matrice ordinata è più lenta di una matrice non ordinata?
- 19. Trovare il numero di coppia non ordinata in una matrice
- 20. Se una tabella di moltiplicazione NxM viene ordinata, qual è il numero nel mezzo?
- 21. quando ridimensionare una tabella hash?
- 22. Creazione di una tabella hash/funzione hash
- 23. Trovare collisioni nella tabella hash
- 24. Ricerca in una matrice non ordinata
- 25. Qual è l'algoritmo più veloce per ordinare un elenco collegato?
- 26. Qual è il modo pitone di controllare se un oggetto è una lista?
- 27. Qual è il modo più elegante in Perl di espandere un iteratore in una lista?
- 28. trovare l'elemento minimo in una matrice ordinata ciclicamente
- 29. Trovare la distanza minima in una tabella
- 30. Qual è più veloce: UNISCI con GROUP BY o una sottoquery?
Gli hashtables sono O (1) in media e O (n) nel peggiore dei casi, mentre una ricerca binaria è O (log n) nel peggiore dei casi. Di solito quando non si menziona se si sta parlando del caso migliore, medio o peggiore, si presume il caso peggiore, quindi non è consigliabile dire semplicemente "le hastables sono O (1)". –