Que es más rápido, las operaciones de búsqueda de Hash o búsqueda binaria?
https://stackoverflow.com/questions/360040
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Cuando se le dé un conjunto estático de objetos (estáticas en el sentido de que una vez cargado que rara vez o nunca cambia) en el que repiten las búsquedas simultáneas se necesitan con un rendimiento óptimo, lo que es mejor, un o una matriz HashMap con una búsqueda binaria el uso de algunos comparador de encargo?
Es la respuesta en función del objeto o estructura tipo? Hash y / o rendimiento igual función? singularidad de hash? Tamaño de la lista? Hashset tamaño / set tamaño?
El tamaño del conjunto que estoy mirando puede ser desde 500 mil a 10 millones - en caso de que la información es útil
.Mientras estoy en busca de una respuesta de C #, creo que la verdadera respuesta matemática no reside en el lenguaje, así que no estoy incluyendo dicha etiqueta. Sin embargo, si hay C # cosas específicas a tener en cuenta, se desea que la información.
Solución
Ok, voy a tratar de ser breve.
C # respuesta corta:
Prueba de los dos enfoques diferentes.
.NET proporciona las herramientas para cambiar su enfoque con una línea de código. De lo contrario usar System.Collections.Generic.Dictionary y asegúrese de inicializarlo con un gran número como la capacidad inicial o pasará el resto de su vida inserción de artículos debido a que el trabajo de GC tiene que hacer para cobrar viejas matrices de cubo.
Respuesta larga:
Una tabla hash tiene tiempos de búsqueda casi constante y llegar a un elemento de una tabla hash en el mundo real no sólo requieren para calcular un hash.
Para llegar a un elemento, su tabla hash va a hacer algo como esto:
- Obtener el hash de la clave
- Obtener el número cubo para que la almohadilla (por lo general la función de mapa se parece a este cubo de hash =% bucketsCount)
- atravesar la cadena de artículos (que es básicamente una lista de elementos que comparten el mismo cubo, la mayoría de las tablas hash usan este método de manejo de cubo / de hash colisiones) que se inicia en ese cubo y comparar cada tecla con el uno de los elementos que está intentando añadir / eliminar / actualizar / verificar si contenida.
tiempos de búsqueda dependen de la "buena" (lo abstracto que es la salida) y rápido es su función hash, el número de cubos que está utilizando y qué tan rápido es el comparador de claves, no es siempre la mejor solución.
Una explicación mejor y más profundo: http: //en.wikipedia. org / wiki / tabla_hash
Otros consejos
Para muy pequeñas colecciones de la diferencia va a ser insignificante. En el extremo inferior de su rango de 500k (material), usted comenzará a ver una diferencia, si está haciendo un montón de búsquedas. Una búsqueda binaria va a ser O (log n), mientras que una búsqueda de hash será O (1), amortiza . Eso no es lo mismo que verdaderamente constante, pero a pesar de ello tiene que tener una función hash bastante terrible a empeorar el rendimiento de una búsqueda binaria.
(Cuando digo "terrible de hash", me refiero a algo como:
hashCode()
{
return 0;
}
Sí, es increíblemente rápido en sí, pero hace que su mapa hash para convertirse en una lista enlazada.)
ialiashkevich escribió algo de código C # utilizando una matriz y un diccionario para comparar los dos métodos, pero utiliza los valores largos para llaves. Quería probar algo que realmente ejecutar una función de hash durante las operaciones de búsqueda, por lo que he modificado el código. Lo cambié a utilizar valores de cadena, y yo refactorizado las secciones poblar y de búsqueda en sus propios métodos, así que es fácil de ver en un generador de perfiles. También me dejó en el código que utiliza valores de tiempo, sólo como un punto de comparación. Por último, me deshice de la función de búsqueda binaria personalizada y utilizamos el uno en el Array clase.
Aquí está el código:
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);
}
}
Estos son los resultados con diferentes tamaños de colecciones. (Los tiempos son en milisegundos.)
Los valores largos 500000 ...
Poblar largo diccionario: 26
Poblar larga serie: 2
Larga búsqueda Diccionario: 9
Buscar larga serie: 80Los valores de cadena 500000 ...
Poblar Array cadena: 1237
Poblar Diccionario de encordado: 46
Ordenar Array cadena: 1755
Buscar Diccionario de encordado: 27
Cadena de búsqueda Matriz: 15691000000 Los valores largos ...
Poblar largo diccionario: 58
Poblar larga serie: 5
Larga búsqueda Diccionario: 23
Buscar larga serie: 136Los valores de cadena 1000000 ...
Poblar Array cadena: 2070
Poblar Diccionario de encordado: 121
Ordenar Array cadena: 3579
Buscar Diccionario de encordado: 58
Cadena de búsqueda Matriz: 32673000000 Los valores largos ...
Poblar largo Diccionario: 207
Poblar larga serie: 14
Diccionario larga búsqueda: 75
Buscar larga serie: 435Los valores de cadena 3000000 ...
Poblar Array cadena: 5553
Poblar Diccionario de encordado: 449
Ordenar Array cadena: 11695
Buscar Diccionario de encordado: 194
Cadena de búsqueda Matriz: 1059410000000 Los valores largos ...
Poblar largo Diccionario: 521
Poblar larga serie: 47
Larga búsqueda Diccionario: 202
Buscar larga serie: 118110000000 Los valores de cadena ...
Poblar Array cadena: 18119
Poblar Diccionario de encordado: 1088
Ordenar Array cadena: 28174
Buscar Diccionario de encordado: 747
Cadena de búsqueda Matriz: 26503
Y para la comparación, aquí está la salida del generador de perfiles para la última ejecución del programa (10 millones de discos y de las actualizaciones). Destaqué las funciones pertinentes. Ellos muy de cerca están de acuerdo con las métricas cronómetro anteriores.
Se puede ver que las búsquedas de diccionario son mucho más rápido que la búsqueda binaria, y (como se esperaba) la diferencia es más pronunciada cuanto mayor sea la colección. Por lo tanto, si usted tiene una función hash razonable (bastante rápido con pocas colisiones), una búsqueda de hash debe vencer a la búsqueda binaria para las colecciones de esta gama.
Las respuestas de Bobby, Bill y Corbin están equivocados. O (1) no es más lento que el O (log n) para un / n acotada fijo:
log (n) es constante, lo que depende de la constante de tiempo.
Y para una función hash lento, nunca oído hablar de MD5?
El algoritmo de hash de cadena por defecto, probablemente afecta a todos los personajes, y puede ser fácilmente 100 veces más lento que el promedio para comparar claves de cadena larga. Estado allí, hecho eso.
Usted puede ser capaz de (parcialmente) utilizan una base. Si se puede dividir en 256 aproximadamente mismos bloques de tamaño, lo que buscas en 2k a 40k búsqueda binaria. Esto es probable que proporcione un rendimiento mucho mejor.
[Editar] Demasiada gente votando por lo que no entienden.
Cadena compara para conjuntos ordenados de búsqueda binarios tienen una propiedad muy interesante: se ponen más lenta cuanto más se acercan a la meta. En primer lugar se romperán en el primer carácter, al final, sólo en el último. Suponiendo un tiempo constante para ellos es incorrecto.
La única respuesta razonable a esta pregunta es: depende. Depende del tamaño de los datos, la forma de sus datos, su aplicación de hash, su aplicación de búsqueda binaria, y dónde están sus datos vive (aunque no se menciona en la pregunta). Un par de otras respuestas decir lo mismo, por lo que sólo podían eliminar esto. Sin embargo, podría ser bueno para compartir lo que he aprendido de retroalimentación a mi primera respuesta.
- Me escribió: " Los algoritmos hash son O (1), mientras que la búsqueda binaria es O (log n) ". - Como se ha señalado en los comentarios, Big O estimaciones de notación complejidad, no la velocidad. Esto es absolutamente cierto. Vale la pena señalar que la complejidad que suelen utilizar para tener una idea de los requisitos de tiempo y espacio de un algoritmo. Así, mientras que es absurdo suponer complejidad es estrictamente la misma que la velocidad, la estimación de la complejidad sin tiempo ni espacio en la parte posterior de su mente es inusual. Mi recomendación:. Evitar la notación Big O
- Me escribió: " Así que cuando n tiende a infinito ..." - Se trata de lo más tonto que podría haber incluido en una respuesta. Infinity no tiene nada que ver con su problema. Usted menciona un límite superior de 10 millones. Ignorar el infinito. Como los comentaristas señalan, números muy grandes crearán todo tipo de problemas con un hash. (Muy grandes números no hacen búsqueda binaria de un paseo en el parque tampoco.) Mi recomendación: no mencionan el infinito a menos que decir infinito .
- Además de los comentarios: cuidado con los hashes de cadena por defecto (? ¿Estás hashing cuerdas Usted no menciona.), Los índices de bases de datos son a menudo los árboles B (alimento para el pensamiento). Mi recomendación: considerar todas sus opciones. Considere otras estructuras de datos y enfoques ... como un anticuado trie (para almacenar y recuperar cuerdas) o un href="https://en.wikipedia.org/wiki/R-tree" rel="nofollow noreferrer"> R-árbol MA-FSA (Minimal acíclico Autómatas de estados finitos - pequeña huella de almacenamiento).
Teniendo en cuenta los comentarios, es posible asumir que las personas que utilizan tablas hash están trastornadas. Son tablas hash imprudente y peligroso? Son estas personas dementes?
Resulta que no lo son. Al igual que los árboles binarios son buenos en ciertas cosas (en el orden de recorrido de datos, la eficiencia del almacenamiento), tablas hash tienen su momento para brillar también. En particular, pueden ser muy buenos para reducir el número de lecturas requerido a buscar sus datos. Un algoritmo de control puede generar un lugar y saltar directamente a ella en la memoria o en el disco, mientras que la búsqueda binaria lee los datos durante cada comparación para decidir qué leer a continuación. Cada lectura tiene el potencial de un fallo de caché que es un orden de magnitud (o más) más lento que una instrucción de la CPU.
Eso no es para decir tablas hash son mejores que la búsqueda binaria. Ellos no están. Tampoco es para sugerir que todos los binarios de hash y las implementaciones de búsqueda son los mismos. Ellos no están. Si tengo un punto, que es esto: existen dos enfoques por una razón. Todo depende de usted para decidir qué es mejor para sus necesidades.
Respuesta original:
algoritmos hash son O (1), mientras que la búsqueda binaria es O (log n). Así como n tiende a infinito, el rendimiento mejora de hash relativa a binario buscar. Su kilometraje puede variar en función de n, el picadillo implementación y su aplicación de búsqueda binaria.
interesante discusión sobre O (1) . Parafraseado:
O (1) no significa instantánea. Esto significa que el rendimiento no lo hace cambiar a medida que el tamaño de n crece. Usted puede diseñar un algoritmo de hash eso es tan lento nadie volvería a usarlo y aún sería O (1). Estoy bastante seguro de .NET / C # no sufre de hash costo prohibitivo, sin embargo;)
Si su conjunto de objetos es verdaderamente estático e inmutable, se puede utilizar un a obtener O (1) un rendimiento garantizado. He visto gperf mencionado un par de veces, aunque nunca he tenido ocasión de usarlo yo mismo.
Los valores hash son típicamente más rápido, aunque las búsquedas binarias tienen mejores características de peor caso. Un acceso hash es típicamente un cálculo para obtener un valor hash para determinar qué "cubo" un registro estará en, por lo que el rendimiento general dependerá de cómo se distribuyen de manera uniforme los registros, y el método utilizado para buscar el cubo. Una función hash malo (dejando unos cubos con una gran cantidad de registros) con una búsqueda lineal a través de los cubos se traducirá en una búsqueda lenta. (En la tercera parte, si usted está leyendo un disco en lugar de la memoria, los cubos de patata son propensos a ser contiguos, mientras que el árbol binario prácticamente garantiza el acceso no local).
Si desea generalmente rápido, usar el hash. Si realmente quieres un rendimiento garantizado, acotada, es posible ir con el árbol binario.
Sorprendido nadie mencionó hashing cuco, que proporciona O garantizada (1) y, a diferencia perfecto hashing, es capaz de utilizar toda la memoria se asigna, donde hashing tan perfecta puede terminar con O garantizada (1), pero perdiendo la mayor porción de su asignación. La advertencia? tiempo de inserción puede ser muy lenta, especialmente como el número de elementos se incrementa, ya que toda la optimización se lleva a cabo durante la fase de inserción.
Creo que alguna versión de este se utiliza en el hardware del router para búsquedas de IP.
Dictionary / Hashtable está utilizando más memoria y lleva más tiempo para rellenar en comparación con matriz. Sin embargo, la búsqueda se hace más rápido al diccionario en lugar de búsqueda binaria dentro de la agrupación.
Aquí están los números para 10 Millones de artículos para buscar y poblar. Además de un código de ejemplo se puede ejecutar por sí mismo.
diccionario memoria: 462836
Memoria Matriz: 88376
Populate Diccionario: 402
Rellenar matriz: 23
Búsqueda de Diccionario: 176
Búsqueda de matriz: 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;
}
}
}
Tengo la firme sospecha de que en un conjunto de problemas de tamaño ~ 1 M, hash sería más rápido.
Sólo por los números:
una búsqueda binaria requeriría ~ 20 compara (2 ^ 20 == 1 M)
una búsqueda de hash requeriría 1 cálculo de hash de la clave de búsqueda, y, posiblemente, un puñado de compara después para resolver los posibles colisiones
Editar: los números:
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);
}
veces: c = "abcde", d = "rwerij" código hash: 0,0012 segundos. Compare: 2,4 segundos.
descargo de responsabilidad: En realidad la evaluación comparativa de una búsqueda de hash frente a una búsqueda binaria podría ser mejor que esta prueba no del todo relevante. Ni siquiera estoy seguro de si se GetHashCode memoized bajo el capó
Yo diría que depende principalmente de la actuación del hash y comparar los métodos. Por ejemplo, cuando se utiliza claves de cadena que son muy largas pero al azar, una comparación siempre dará un resultado muy rápido, pero una función hash por defecto procesará toda la cadena.
Sin embargo, en la mayoría de los casos la correlación hash debe ser más rápido.
Me pregunto por qué nadie mencionó hash perfecta .
Es sólo es relevante si el conjunto de datos es fija durante mucho tiempo, pero lo que hace que analizar los datos y la construcción de una función hash perfecta que garantiza que no haya colisiones.
Bastante limpio, si el conjunto de datos es constante y el tiempo para calcular la función es pequeña en comparación con la ejecución de la aplicación.
Depende de la forma de manejar los duplicados de las tablas hash (en su caso). Si desea permitir duplicados clave hash (sin función hash es perfecto), sigue siendo O (1) para la búsqueda de la clave principal, pero buscar detrás para el valor "correcto" pueden ser costosos. Respuesta es entonces, teóricamente mayor parte del tiempo, los hashes son más rápidos. Tu caso es distinto en función de los datos que puso en su lugar ...
aquí se describe cómo se construyen los hashes y porque el universo de las teclas es bastante grande y funciones de hash están diseñados para ser "muy inyectiva", por lo que las colisiones ocurren raramente el tiempo de acceso a una tabla hash no es O (1), en realidad ... es algo basado en algunas probabilidades. Sin embargo, es razonable decir que el tiempo de acceso de un hash es casi siempre menor que el tiempo O (log_2 (n))
Por supuesto, el hash es más rápido para un gran conjunto de datos tales.
Una forma de acelerarlo aún más, ya que los datos rara vez cambia, es la generación de programación de código ad-hoc para hacer la primera capa de búsqueda como una sentencia switch gigante (si el compilador puede manejarlo), y luego rama fuera a buscar el cubo resultante.
La respuesta depende. Vamos a pensar que el número de elementos 'n' es muy grande. Si usted es bueno en la escritura de una mejor función hash que las colisiones menores, entonces hash es el mejor.
Nota que
La función hash se ejecuta sólo una vez en la búsqueda y se dirige a la cubeta correspondiente. Por lo tanto, no es una gran sobrecarga si n es alta.
Problema en la tabla hash:
Pero el problema en las tablas hash es si la función hash no es bueno (más colisiones ocurre), entonces la búsqueda no es O (1). Se tiende a O (n), ya que la búsqueda de un cubo es una búsqueda lineal. Puede ser peor que un árbol binario.
problema en árbol binario:
En árbol binario, si el árbol no está equilibrado, sino que también tiende a O (n). Por ejemplo, si ha insertado 1,2,3,4,5 a un árbol binario que sería más probable una lista.
Por lo tanto,
Si puede ver una buena metodología de hash, utilice una tabla hash
Si no es así, es mejor que el uso de un árbol binario.
Esto es más un comentario a la respuesta de Bill porque su respuesta tiene tantas upvotes a pesar de su mal. Así que tenía que escribir esto.
Veo mucha discusión sobre lo que es el peor caso de complejidad de una búsqueda en la tabla hash, y lo que se considera el análisis amortizado / lo que no es. Por favor, compruebe el siguiente enlace
Hash complejidad tabla de tiempo de ejecución (insertar, buscar y eliminar)
peor de los casos la complejidad es O (n) y no O (1) en contraposición a lo que dice Bill. Y por lo tanto su O (1) la complejidad no se amortiza ya que este análisis sólo se puede utilizar para el peor de los casos (también su propio enlace de Wikipedia lo dice)
Esta pregunta es más complicado que el ámbito de actuación algoritmo puro. Si eliminamos los factores que algoritmo de búsqueda binaria es más caché de usar, la búsqueda de hash es más rápida en sentido general. La mejor manera de descubierto es construir un programa y desactivar las opciones de optimización del compilador, y que se podía encontrar que las operaciones de búsqueda hash es más rápido dada su eficiencia de tiempo algoritmo es O (1) en sentido general.
Sin embargo, cuando se habilita la optimización del compilador, y tratar de la misma prueba con menor recuento de muestras decir menos de 10.000, la búsqueda binaria superó a la búsqueda de hash tomando ventajas de su estructura de datos de caché de usar.
