Che è più veloce, ricerca Hash o la ricerca binaria?
https://stackoverflow.com/questions/360040
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Quando dato un insieme statico di oggetti (statici nel senso che una volta caricate di rado se cambia mai) in cui ripetute ricerche simultanee intero con prestazioni ottimali, che è meglio, un HashMap o un array con una ricerca binaria utilizzando alcuni di confronto personalizzato?
E 'la risposta di una funzione di oggetto o struct tipo? Hash e / o le prestazioni uguale funzione? unicità Hash? Dimensioni elenco? Hashset dimensioni / impostare le dimensioni?
La dimensione del set che sto guardando può essere ovunque da 500k a 10m - in caso che l'informazione è utile
.Mentre sto cercando un C # risposta, credo che la vera risposta matematica non sta nella lingua, quindi non mi compreso quel tag. Tuttavia, se ci sono C # cose specifiche da tenere presente, che l'informazione è desiderato.
Soluzione
Ok, cercherò di essere breve.
C # risposta breve:
Testare i due approcci differenti.
.NET fornisce gli strumenti per cambiare il vostro approccio con una riga di codice. In caso contrario, utilizzare System.Collections.Generic.Dictionary ed essere sicuri di inizializzare con un gran numero di capacità iniziale o si passa il resto della tua vita inserimento di elementi a causa del lavoro GC ha a che fare per raccogliere i vecchi sistemi secchio.
Più rispondere:
Una tabella hash ha tempi di ricerca quasi costante e di arrivare a un elemento in una tabella hash nel mondo reale non si limita a richiedere per calcolare un hash.
Per arrivare a un elemento, la vostra tabella hash farà qualcosa di simile:
- Prendi l'hash della chiave
- Ottieni il numero bucket per quella hash (di solito la funzione di mappa assomiglia a questo secchio = hash% bucketsCount)
- attraversano la catena articoli (in pratica si tratta di un elenco di elementi che condividono lo stesso secchio, la maggior parte delle hashtables usano questo metodo di gestione della benna / hash collisioni) che inizia in quel secchio e confrontare ogni tasto con il uno della voce che si sta tentando di aggiungere / eliminare / modificare / verificare se contenute.
volte Lookup dipendono da come "buono" (come scarsa è l'uscita) e veloce è la vostra funzione di hash, il numero di secchi che si sta utilizzando e quanto velocemente è la chiavi di confronto, non è sempre la soluzione migliore.
Una spiegazione migliore e più profonda: http: //en.wikipedia. org / wiki / Hash_table
Altri suggerimenti
Per molto piccole collezioni la differenza sta per essere trascurabile. Nella parte bassa del range (500k articoli) si inizierà a vedere una differenza se si sta facendo un sacco di ricerche. Una ricerca binaria sarà O (log n), mentre una ricerca hash sarà O (1), ammortizzato . Che non è la stessa come veramente costante, ma si dovrebbe ancora avere una funzione di hash abbastanza terribile per ottenere le prestazioni di peggio di una ricerca binaria.
(Quando dico "terribile hash", voglio dire qualcosa come:
hashCode()
{
return 0;
}
Sì, è veloce come un lampo in sé, ma fa sì che la tua mappa di hash per diventare una lista collegata.)
ialiashkevich ha scritto qualche codice C # utilizzando un array e un dizionario per confrontare i due metodi, ma ha usato i valori a lungo per chiavi. Ho voluto mettere alla prova qualcosa che sarebbe in realtà eseguire una funzione di hash durante la ricerca, in modo che ho modificato il codice. L'ho cambiato per utilizzare i valori di stringa, e ho refactoring sezioni popolamento e di ricerca nei loro propri metodi in modo che sia più facile vedere in un profiler. Ho anche lasciato nel codice che utilizza i valori lunghi, proprio come un punto di confronto. Infine, mi sono liberato della funzione di ricerca binaria personalizzato e utilizzato quello nella classe di Array.
Ecco il codice:
class Program
{
private const long capacity = 10_000_000;
private static void Main(string[] args)
{
testLongValues();
Console.WriteLine();
testStringValues();
Console.ReadLine();
}
private static void testStringValues()
{
Dictionary<String, String> dict = new Dictionary<String, String>();
String[] arr = new String[capacity];
Stopwatch stopwatch = new Stopwatch();
Console.WriteLine("" + capacity + " String values...");
stopwatch.Start();
populateStringArray(arr);
stopwatch.Stop();
Console.WriteLine("Populate String Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
populateStringDictionary(dict, arr);
stopwatch.Stop();
Console.WriteLine("Populate String Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
Array.Sort(arr);
stopwatch.Stop();
Console.WriteLine("Sort String Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchStringDictionary(dict, arr);
stopwatch.Stop();
Console.WriteLine("Search String Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchStringArray(arr);
stopwatch.Stop();
Console.WriteLine("Search String Array: " + stopwatch.ElapsedMilliseconds);
}
/* Populate an array with random values. */
private static void populateStringArray(String[] arr)
{
for (long i = 0; i < capacity; i++)
{
arr[i] = generateRandomString(20) + i; // concatenate i to guarantee uniqueness
}
}
/* Populate a dictionary with values from an array. */
private static void populateStringDictionary(Dictionary<String, String> dict, String[] arr)
{
for (long i = 0; i < capacity; i++)
{
dict.Add(arr[i], arr[i]);
}
}
/* Search a Dictionary for each value in an array. */
private static void searchStringDictionary(Dictionary<String, String> dict, String[] arr)
{
for (long i = 0; i < capacity; i++)
{
String value = dict[arr[i]];
}
}
/* Do a binary search for each value in an array. */
private static void searchStringArray(String[] arr)
{
for (long i = 0; i < capacity; i++)
{
int index = Array.BinarySearch(arr, arr[i]);
}
}
private static void testLongValues()
{
Dictionary<long, long> dict = new Dictionary<long, long>(Int16.MaxValue);
long[] arr = new long[capacity];
Stopwatch stopwatch = new Stopwatch();
Console.WriteLine("" + capacity + " Long values...");
stopwatch.Start();
populateLongDictionary(dict);
stopwatch.Stop();
Console.WriteLine("Populate Long Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
populateLongArray(arr);
stopwatch.Stop();
Console.WriteLine("Populate Long Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchLongDictionary(dict);
stopwatch.Stop();
Console.WriteLine("Search Long Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchLongArray(arr);
stopwatch.Stop();
Console.WriteLine("Search Long Array: " + stopwatch.ElapsedMilliseconds);
}
/* Populate an array with long values. */
private static void populateLongArray(long[] arr)
{
for (long i = 0; i < capacity; i++)
{
arr[i] = i;
}
}
/* Populate a dictionary with long key/value pairs. */
private static void populateLongDictionary(Dictionary<long, long> dict)
{
for (long i = 0; i < capacity; i++)
{
dict.Add(i, i);
}
}
/* Search a Dictionary for each value in a range. */
private static void searchLongDictionary(Dictionary<long, long> dict)
{
for (long i = 0; i < capacity; i++)
{
long value = dict[i];
}
}
/* Do a binary search for each value in an array. */
private static void searchLongArray(long[] arr)
{
for (long i = 0; i < capacity; i++)
{
int index = Array.BinarySearch(arr, arr[i]);
}
}
/**
* Generate a random string of a given length.
* Implementation from https://stackoverflow.com/a/1344258/1288
*/
private static String generateRandomString(int length)
{
var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
var stringChars = new char[length];
var random = new Random();
for (int i = 0; i < stringChars.Length; i++)
{
stringChars[i] = chars[random.Next(chars.Length)];
}
return new String(stringChars);
}
}
Ecco i risultati con diversi formati di collezioni. (I tempi sono in millisecondi).
500000 valori lunghi ...
Popolare lungo Dizionario: 26
Popolare Array Long: 2
Cerca Lunga Dizionario: 9
Cerca lunga serie: 80500000 valori String ...
Popolare String Array: 1237
Popolare String Dizionario: 46
Ordina String Array: 1755
Cerca String Dizionario: 27
Stringa di ricerca Array: 15691000000 valori lunghi ...
Popolare lungo Dizionario: 58
Popolare Array Long: 5
Cerca Lunga Dizionario: 23
Cerca lunga serie: 1361000000 valori String ...
Popolare String Array: 2070
Popolare String Dizionario: 121
Ordina String Array: 3579
Cerca String Dizionario: 58
Stringa di ricerca Array: 32673000000 valori lunghi ...
Popolare lungo Dizionario: 207
Popolare Array lungo: 14
Cerca Lunga Dizionario: 75
Cerca lunga serie: 4353000000 valori String ...
Popolare String Array: 5553
Popolare String Dizionario: 449
Ordina String Array: 11695
Cerca String Dizionario: 194
Stringa di ricerca Array: 1059410000000 valori lunghi ...
Popolare lungo Dizionario: 521
Popolare Array lungo: 47
Cerca Lunga Dizionario: 202
Cerca Array Long: 118110000000 valori String ...
Popolare String Array: 18119
Popolare String Dizionario: 1088
Ordina String Array: 28174
Cerca String Dizionario: 747
Stringa di ricerca Array: 26503
E per il confronto, ecco l'output profiler per l'ultima esecuzione del programma (10 milioni di dischi e le ricerche). Ho evidenziato le relative funzioni. Sono abbastanza stretto accordo con le metriche cronometro di cui sopra.
Si può vedere che le ricerche Dizionario sono molto più veloce di ricerca binaria, e (come previsto) la differenza è più marcata quanto maggiore è la collezione. Quindi, se si dispone di una funzione di hashing ragionevole (abbastanza veloce con poche collisioni), una ricerca hash dovrebbe battere ricerca binaria per le collezioni di questa gamma.
Le risposte di Bobby, Bill e Corbin sono sbagliate. O (1) non è più lento di O (log n) per un / limitato n fisso:
log (n) è costante, in modo che dipende dalla costante di tempo.
E per una funzione di hash lento, mai sentito parlare di md5?
L'algoritmo di hashing stringa di default probabilmente tocca tutti i caratteri, e può essere facilmente 100 volte più lento rispetto alla media confrontare per chiavi stringa lunghi. Conosci, già fatto.
Si potrebbe essere in grado di (in parte) utilizzano una radice. Se si può dividere in 256 blocchi approssimativamente delle stesse dimensioni, si sta guardando 2k a 40k ricerca binaria. Questo è probabilmente quello di fornire prestazioni molto migliori.
[Modifica] Troppe persone voto giù quello che non capiscono.
String confronto per la ricerca ordinato insiemi binari hanno una proprietà molto interessante: ottengono più lenta è la più si avvicinano al bersaglio. In primo luogo si romperà sul primo carattere, alla fine solo l'ultimo. Assumendo una costante di tempo per loro non è corretta.
L'unica risposta ragionevole a questa domanda è: dipende. Essa dipende dalla dimensione dei dati, la forma dei vostri dati, l'implementazione hash, l'implementazione ricerca binaria, e dove i dati vive (anche se non è menzionato nella questione). Un paio di altre risposte dicono tanto, così ho potuto solo cancellare questo. Tuttavia, potrebbe essere bello condividere quello che ho imparato da un feedback alla mia risposta originale.
- ho scritto, " algoritmi di hash sono O (1), mentre ricerca binaria è O (log n) ." - Come notato nei commenti, Big O stime notazione complessità, non la velocità. Questo è assolutamente vero. Vale la pena notare che usiamo di solito la complessità per ottenere un senso di requisiti di tempo e di spazio di un algoritmo. Così, mentre è sciocco presumere complessità è rigorosamente lo stesso della velocità, la stima complessità senza tempo né spazio nella parte posteriore della vostra mente è insolito. La mia raccomandazione:. Evitare notazione O-grande
- ho scritto, " Quindi, per n che tende all'infinito ..." - Questa è la cosa più stupida che avrebbe potuto inserire in una risposta. Infinity non ha nulla a che fare con il vostro problema. Lei parla di un limite superiore di 10 milioni. Ignora l'infinito. Mentre i commentatori sottolineano, numeri molto grandi creeranno problemi di ogni genere con un hash. (Numeri molto grandi non fanno ricerca binaria una passeggiata nel parco o.) La mia raccomandazione: non menzionare l'infinito a meno che non si intende l'infinito .
- Anche dai commenti: attenzione hash stringa di default (? Stai hashing stringhe Tu non parlare.), Gli indici di database sono spesso b-alberi (cibo per il pensiero). La mia raccomandazione: considerare tutte le opzioni. Prendere in considerazione altre strutture di dati e approcci ... come un vecchio trie (per la memorizzazione e il recupero stringhe) o un R-tree (per i dati spaziali) o un MA-FSA (Basico aciclici Finite State Automaton - minimo ingombro di stoccaggio).
Dati i commenti, si potrebbe supporre che le persone che fanno uso di tabelle hash sono squilibrati. Sono tabelle hash sconsiderato e pericoloso? Sono queste persone folle?
Abbiamo scoperto che non lo sono. Proprio come gli alberi binari sono bravi a certe cose (in-ordine di attraversamento dei dati, l'efficienza dello storage), tabelle hash hanno il loro momento di gloria pure. In particolare, possono essere molto bravi a ridurre il numero di letture necessarie per recuperare i dati. Un algoritmo di hash può generare una posizione e passare direttamente ad esso nella memoria o sul disco mentre la ricerca binaria legge i dati nel corso di ogni confronto per decidere cosa leggere successivo. Ogni lettura ha il potenziale per una cache miss, che è un ordine di grandezza (o più) più lento di un'istruzione di CPU.
Questo non vuol dire tabelle hash sono meglio di ricerca binaria. Loro non sono. Non è anche suggerire che tutte le hash e le implementazioni binari di ricerca sono gli stessi. Loro non sono. Se ho un punto, è questo: esistono due approcci per una ragione. Sta a voi decidere quale è la cosa migliore per le vostre esigenze.
Risposta originale:
algoritmi di hash sono O (1), mentre ricerca binaria è O (log n). Così come n tende all'infinito, prestazioni hash migliora rispetto al binario ricerca. La vostra situazione varia a seconda del n, il vostro hash l'implementazione e l'implementazione ricerca binaria.
Interessante discussione su O (1) . Parafrasato:
O (1) non significa istantanea. Ciò significa che le prestazioni non lo fa cambiare la dimensione di n cresce. È possibile progettare un algoritmo di hashing che è così lento che nessuno avrebbe mai usarlo e sarebbe ancora O (1). Sono abbastanza sicuro .NET / C # non soffre di hashing un costo proibitivo, però;)
Se il set di oggetti è veramente statica ed immutabile, è possibile utilizzare un perfetta hash per ottenere O (1) prestazioni garantite. Ho visto gperf menzionato un paio di volte, anche se non ho mai avuto occasione di usarlo me stesso.
Gli hash sono in genere più veloce, anche se le ricerche binarie hanno migliori caratteristiche peggiori. Un accesso hash è tipicamente un calcolo per ottenere un valore hash per determinare quale "bucket" un record sarà in, e quindi le prestazioni generalmente dipenderà da come uniformemente sono distribuiti i record, e il metodo utilizzato per cercare il secchio. Una funzione hash cattivo (lasciando un paio di secchi con un sacco di record) con una ricerca lineare attraverso i secchi si tradurrà in una ricerca lenta. (Nella terza parte, se stai leggendo un disco piuttosto che la memoria, i secchi hash sono suscettibili di essere contigui, mentre l'albero binario praticamente garantisce l'accesso non locale).
Se si desidera generalmente veloce, utilizzare l'hash. Se si vuole veramente garantito prestazioni limitata, si potrebbe andare con l'albero binario.
Sorpreso nessuno ha menzionato hashing cucù, che fornisce O garantito (1) e, a differenza perfetto hashing, è in grado di utilizzare tutta la memoria si alloca, dove come perfetto hashing può finire con O garantito (1) ma sprecare maggiore parte della dotazione. L'avvertimento? tempo di inserimento può essere molto lento, soprattutto perché il numero di elementi aumenta, poiché tutti ottimizzazione viene eseguita durante la fase di inserimento.
Credo che una qualche versione di questo è usato in hardware router IP per le ricerche.
dizionario / Hashtable utilizza più memoria e richiede più tempo per popolare confronto ad array. Ma ricerca è fatto più velocemente dal dizionario piuttosto che di ricerca binaria all'interno dell'array.
Ecco i numeri per 10 milione di Int64 gli elementi per la ricerca e la popolano. Più un codice di esempio è possibile eseguire da soli.
Memoria Dizionario: 462.836
array di memoria: 88.376
Populate Dizionario: 402
Popolare Array: 23
Cerca Dictionary: 176
Cerca Array: 680
using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace BinaryVsDictionary
{
internal class Program
{
private const long Capacity = 10000000;
private static readonly Dictionary<long, long> Dict = new Dictionary<long, long>(Int16.MaxValue);
private static readonly long[] Arr = new long[Capacity];
private static void Main(string[] args)
{
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for (long i = 0; i < Capacity; i++)
{
Dict.Add(i, i);
}
stopwatch.Stop();
Console.WriteLine("Populate Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
for (long i = 0; i < Capacity; i++)
{
Arr[i] = i;
}
stopwatch.Stop();
Console.WriteLine("Populate Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
for (long i = 0; i < Capacity; i++)
{
long value = Dict[i];
// Console.WriteLine(value + " : " + RandomNumbers[i]);
}
stopwatch.Stop();
Console.WriteLine("Search Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
for (long i = 0; i < Capacity; i++)
{
long value = BinarySearch(Arr, 0, Capacity, i);
// Console.WriteLine(value + " : " + RandomNumbers[i]);
}
stopwatch.Stop();
Console.WriteLine("Search Array: " + stopwatch.ElapsedMilliseconds);
Console.ReadLine();
}
private static long BinarySearch(long[] arr, long low, long hi, long value)
{
while (low <= hi)
{
long median = low + ((hi - low) >> 1);
if (arr[median] == value)
{
return median;
}
if (arr[median] < value)
{
low = median + 1;
}
else
{
hi = median - 1;
}
}
return ~low;
}
}
}
Ho il forte sospetto che in un problema di set di dimensioni ~ 1M, hashing sarebbe più veloce.
Solo per i numeri:
una ricerca binaria richiederebbe ~ 20 confronta (2 ^ 20 == 1M)
una ricerca hash richiederebbe 1 calcolo dell'hash sulla chiave di ricerca, e forse una manciata di confronto in seguito per risolvere possibili collisioni
Edit: i numeri:
for (int i = 0; i < 1000 * 1000; i++) {
c.GetHashCode();
}
for (int i = 0; i < 1000 * 1000; i++) {
for (int j = 0; j < 20; j++)
c.CompareTo(d);
}
volte: c = "ABCDE", d = "rwerij" codice hash: 0,0012 secondi. Confronto: 2,4 secondi.
disclaimer: In realtà l'analisi comparativa una ricerca hash rispetto a una ricerca binaria potrebbe essere migliore di questo test non-tutto-rilevanti. Io non sono nemmeno sicuro se GetHashCode Ottiene memoized under-the-hood
Direi che dipende principalmente dalla performance del hash e confrontare metodi. Ad esempio, quando si utilizzano chiavi stringa che sono molto lunghi ma casuale, un confronta sempre produrre un risultato molto veloce, ma una funzione predefinita hash elaborerà l'intera stringa.
Ma nella maggior parte dei casi la mappa di hash dovrebbe essere più veloce.
Mi chiedo perché nessuno ha menzionato perfetta hashing .
E 'rilevante solo se il set di dati è fissato per lungo tempo, ma ciò che lo fa analizzare i dati e costruire una funzione di hash perfetta che garantisce l'assenza di collisioni.
Piuttosto pulito, se il set di dati è costante e il tempo per calcolare la funzione è piccola rispetto alla fase di esecuzione dell'applicazione.
Dipende da come si gestisce duplicati per le tabelle hash (se a tutti). Se si desidera consentire duplicati delle chiavi di hash (nessuna funzione di hash è perfetto), Resta O (1) per la ricerca della chiave primaria, ma cerca dietro per il valore "giusto" può essere costoso. La risposta è allora, teoricamente il più delle volte, gli hash sono più veloci. YMMV a seconda di quali dati si mette lì ...
qui è descritto come hash sono costruiti e perché il universo di chiavi è ragionevolmente grande e funzioni di hash sono costruiti per essere "molto iniettiva", in modo che le collisioni accadono raramente il tempo di accesso per una tabella di hash non è O (1) in realtà ... è qualcosa sulla base di alcune probabilità. Ma, è ragionevole dire che il tempo di accesso di un hash è quasi sempre inferiore al tempo di O (log_2 (n))
Naturalmente, hash è più veloce per un grande insieme di dati tale.
Un modo per accelerarlo ancora di più, dal momento che i dati cambiano raramente, è quello di generare a livello di codice il codice ad hoc per fare il primo strato di ricerca come un'istruzione switch gigante (se il compilatore in grado di gestire), e poi ramo fuori per cercare il secchio risultante.
La risposta dipende. Lascia pensare che il numero di elementi 'n' è molto grande. Se sei bravo a scrivere una migliore funzione di hash che collisioni minori, allora hashing è il migliore.
Nota che
La funzione hash viene eseguito solo una volta in ricerca e dirige al secchio corrispondente. Quindi non è un grande testa se n è alta.
Problema nella Hashtable:
Ma il problema in tabelle hash è se la funzione di hash non è buona (più collisioni avviene), allora la ricerca non è O (1). Esso tende a O (n), perché la ricerca in un secchio è una ricerca lineare. Può essere peggio di un albero binario.
problema in albero binario:
In albero binario, se l'albero non è bilanciato, tende anche a O (n). Per esempio, se si è inserito 1,2,3,4,5 ad un albero binario che sarebbe più probabile una lista.
Quindi,
Se è possibile vedere una buona metodologia di hashing, utilizzare una tabella hash
In caso contrario, è meglio utilizzare un albero binario.
Questo è più di un commento alla risposta di Bill, perché la sua risposta ha tante upvotes ancorché il suo male. Così ho dovuto pubblicare questo.
Vedo un sacco di discussione su quello che è il caso peggiore complessità di una ricerca nella tabella hash, e quello che è considerato ammortizzato analisi / ciò che non è. Si prega di verificare sul link qui sotto
Hash tavolo runtime complessità (inserimento, ricerca e cancellazione)
caso peggiore complessità è O (n) e non O (1) al contrario di quello che dice Bill. E così la sua O (1) la complessità non è ammortizzato in quanto questa analisi può essere utilizzato solo per casi più gravi (anche il suo proprio collegamento wikipedia dice così)
Questa domanda è più complicata di quanto la portata delle prestazioni pure algoritmo. Se togliamo i fattori che algoritmo di ricerca binaria è più di cache amichevole, la ricerca hash è più veloce in senso generale. Il modo migliore per capito è quello di costruire un programma e disattivare le opzioni di ottimizzazione del compilatore, e siamo riusciti a trovare che la ricerca di hash è più veloce data la sua efficienza temporale dell'algoritmo è O (1) in senso generale.
Ma quando si attiva l'ottimizzazione del compilatore, e provare la stessa prova con il più piccolo numero di campioni dire meno di 10.000, la ricerca binaria sovraperformato il lookup hash prendendo vantaggi della sua struttura dati di cache-friendly.
