algorithm - flujo - busqueda binaria pseint

¿Qué es más rápido, búsqueda Hash o búsqueda binaria?

Question

Cuando se le da un conjunto estático de objetos (estáticos en el sentido de que una vez cargados rara vez cambia alguna vez) en los que se necesitan búsquedas concurrentes repetidas con un rendimiento óptimo, ¿qué es mejor, un HashMap o una matriz con una búsqueda binaria usando algún comparador personalizado?

¿La respuesta es una función del tipo de objeto o estructura? Hash y / o rendimiento de la función Equal? Hash unicidad? ¿Tamaño de lista? Hashset tamaño / tamaño del conjunto?

El tamaño del conjunto que estoy viendo puede oscilar entre 500k y 10m, en caso de que esa información sea útil.

Mientras busco una respuesta de C #, creo que la verdadera respuesta matemática no radica en el idioma, por lo que no incluiré esa etiqueta. Sin embargo, si hay cosas específicas de C # que debe tener en cuenta, se desea esa información.

Answer 1

Depende de cómo maneje los duplicados para las tablas hash (si es que lo hace). Si desea permitir los duplicados de la clave hash (ninguna función hash es perfecta), sigue siendo O (1) para la búsqueda de la clave principal, pero la búsqueda del valor "correcto" puede ser costosa. La respuesta es, por lo general, la mayor parte del tiempo, los hashes son más rápidos. YMMV dependiendo de qué datos coloques allí ...

Answer 2

El diccionario / Hashtable usa más memoria y tarda más tiempo en completarse comparando con la matriz. Pero la búsqueda se hace más rápido por el diccionario en lugar de la búsqueda binaria dentro de la matriz.

Aquí están los números de 10 millones de elementos Int64 para buscar y poblar. Además de un código de muestra que puede ejecutar usted mismo.

Memoria del diccionario: 462,836

Memoria de matriz: 88,376

Diccionario poblado: 402

Populate Array: 23

Diccionario de búsqueda: 176

Matriz de búsqueda: 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;
        }
    }
}

Answer 3

La única respuesta razonable a esta pregunta es: depende. Depende del tamaño de sus datos, la forma de sus datos, su implementación de hash, su implementación de búsqueda binaria y dónde viven sus datos (aunque no se mencione en la pregunta). Un par de otras respuestas dicen tanto, así que podría borrar esto. Sin embargo, podría ser bueno compartir lo que he aprendido de los comentarios a mi respuesta original.

1. Escribí: " Los algoritmos Hash son O (1) mientras que la búsqueda binaria es O (log n). " - Como se señala en los comentarios, la notación Big O estima la complejidad, no la velocidad. Esto es absolutamente cierto. Vale la pena señalar que generalmente utilizamos la complejidad para tener una idea de los requisitos de tiempo y espacio de un algoritmo. Entonces, si bien es una tontería asumir que la complejidad es estrictamente lo mismo que la velocidad, es inusual estimar la complejidad sin tiempo ni espacio en el fondo de su mente. Mi recomendación: evitar la notación de Big O.
2. Escribí, " Así que cuando n se acerca al infinito ..." - Esta es la cosa más estúpida que podría haber incluido en una respuesta. Infinity no tiene nada que ver con tu problema. Usted menciona un límite superior de 10 millones. Ignora el infinito Como señalan los comentaristas, números muy grandes crearán todo tipo de problemas con un hash. (Los números muy grandes tampoco hacen que la búsqueda binaria sea una caminata en el parque.) Mi recomendación: no menciones el infinito a menos que quieras decir infinito.
3. También a partir de los comentarios: cuidado con los hashes de cadena predeterminados (¿Son cadenas hash? No lo mencionas), los índices de bases de datos son a menudo b-trees (alimento para pensar). Mi recomendación: considere todas sus opciones. Considere otras estructuras de datos y enfoques ... como un trie antiguo (para almacenar y recuperar cadenas) o un R-tree (para datos espaciales) o un MA-FSA (Automatización de estado finito acíclica mínima - huella de almacenamiento pequeña).

Teniendo en cuenta los comentarios, puede suponer que las personas que usan tablas hash están desquiciadas. ¿Las tablas hash son imprudentes y peligrosas? ¿Estas personas están locas?

Resulta que no lo son. Así como los árboles binarios son buenos en ciertas cosas (cruce de datos en orden, eficiencia de almacenamiento), las tablas hash también tienen su momento para brillar. En particular, pueden ser muy buenos para reducir el número de lecturas requeridas para recuperar sus datos. Un algoritmo hash puede generar una ubicación 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 una falta de caché que es un orden de magnitud (o más) más lenta que una instrucción de CPU.

Eso no quiere decir que las tablas hash sean mejores que la búsqueda binaria. Ellos no están. Tampoco es sugerir que todas las implementaciones de búsqueda hash y binaria sean las mismas. Ellos no están. Si tengo un punto, es esto: ambos enfoques existen por una razón. Depende de usted decidir cuál es la mejor para sus necesidades.

Respuesta original:

Los algoritmos Hash son O (1) mientras que la búsqueda binaria es O (log n). Entonces, cuando n se aproxima al infinito, el rendimiento de hash mejora en relación con la búsqueda binaria. Su kilometraje variará según n, su implementación de hash y su implementación de búsqueda binaria.

Interesante discusión sobre O (1) . Parafraseado

O (1) no significa instantáneo. Significa que el rendimiento no cambia a medida que crece el tamaño de n. Puede diseñar un algoritmo de hash que sea tan lento que nadie lo use y aún así sería O (1). Estoy bastante seguro .NET / C # no sufre de hash de costo prohibitivo, sin embargo;)

Answer 4

La respuesta depende Pensemos que la cantidad de elementos ''n'' es muy grande. Si eres bueno escribiendo una mejor función hash que colisiones menores, entonces hash es lo mejor. Tenga en cuenta que la función hash se está ejecutando solo una vez en la búsqueda y que dirige al cubo correspondiente. Por lo tanto, no es una gran sobrecarga si n es alto.
Problema en Hashtable: Pero el problema en las tablas hash es si la función hash no es buena (ocurren más colisiones), entonces la búsqueda no es O (1). Tiende a O (n) porque buscar en un cubo es una búsqueda lineal. Puede ser peor que un árbol binario. problema en el árbol binario: en árbol binario, si el árbol no está equilibrado, también tiende a O (n). Por ejemplo, si insertó 1,2,3,4,5 en un árbol binario, sería más probable que fuera una lista. Por lo tanto, si puede ver una buena metodología de hash, use una tabla hash. De lo contrario, será mejor que utilice un árbol binario.

Answer 5

Las respuestas de Bobby, Bill y Corbin están equivocadas. O (1) no es más lento que O (log n) para un n fijo / acotado:

log (n) es constante, por lo que depende del tiempo constante.

Y para una función hash lenta, ¿has oído hablar de md5?

El algoritmo hash de cadena predeterminado probablemente toque todos los caracteres, y puede ser fácilmente 100 veces más lento que la comparación promedio para las claves de cadena larga. Estado allí, hecho eso.

Es posible que pueda (parcialmente) usar una raíz. Si puedes dividir en 256 bloques del mismo tamaño, estás buscando una búsqueda binaria de 2k a 40k. Es probable que proporcione un rendimiento mucho mejor.

[Editar] Demasiadas personas votan por lo que no entienden.

La secuencia se compara para la búsqueda binaria. Los conjuntos clasificados tienen una propiedad muy interesante: se vuelven más lentos cuanto más se acercan al objetivo. Primero romperán con el primer personaje, al final solo en el último. Asumir un tiempo constante para ellos es incorrecto.

Answer 6

Los valores hash suelen ser más rápidos, aunque las búsquedas binarias tienen mejores características de peor caso. Un acceso hash suele ser un cálculo para obtener un valor hash para determinar en qué "cubo" estará un registro, por lo que el rendimiento generalmente dependerá de qué tan uniformemente se distribuyan los registros y el método utilizado para buscar en el depósito. Una mala función hash (dejando algunos cubos con un montón de registros) con una búsqueda lineal a través de los cubos resultará en una búsqueda lenta. (Por otro lado, si está leyendo un disco en lugar de memoria, es probable que los segmentos de hash sean contiguos, mientras que el árbol binario prácticamente garantiza el acceso no local).

Si generalmente quiere rápido, use el hash. Si realmente quieres un rendimiento limitado garantizado, puedes ir con el árbol binario.

Answer 7

Me pregunto por qué nadie mencionó hashing perfecto .

Solo es relevante si su conjunto de datos está fijo durante mucho tiempo, pero lo que hace es analizar los datos y construir una función hash perfecta que garantice que no haya colisiones.

Bastante limpio, si su conjunto de datos es constante y el tiempo para calcular la función es pequeño en comparación con el tiempo de ejecución de la aplicación.

Answer 8

Ok, intentaré ser bajo.

C: respuesta corta:

Pruebe los dos enfoques diferentes.

.NET le brinda las herramientas para cambiar su enfoque con una línea de código. De lo contrario, use System.Collections.Generic.Dictionary y asegúrese de inicializarlo con un número grande como capacidad inicial o pasará el resto de su vida insertando elementos debido al trabajo que GC tiene que hacer para recolectar matrices de cubetas antiguas.

Respuesta más larga:

Una tabla hash tiene CASI tiempos de búsqueda constantes y llegar a un elemento en una tabla hash en el mundo real no solo requiere calcular un hash.

Para acceder a un elemento, tu hashtable hará algo como esto:

• Obtener el hash de la clave
• Obtenga el número de intervalo para ese hash (generalmente la función del mapa se ve como este cubo = hash% bucketsCount)
• Recorre la cadena de elementos (básicamente es una lista de elementos que comparten el mismo segmento, la mayoría de las tablas hash utilizan este método de manejo de colisiones de cubo / hash) que comienza en ese segmento y compara cada clave con la del elemento que estás intentando agregar / eliminar / actualizar / verificar si está contenido.

Los tiempos de búsqueda dependen de qué tan "bueno" (cuán escaso sea el resultado) y rápido es su función de hash, la cantidad de cubetas que está utilizando y qué tan rápido es el comparador de claves, no siempre es la mejor solución.

Una explicación mejor y más profunda: http://en.wikipedia.org/wiki/Hash_table

Answer 9

Para colecciones muy pequeñas, la diferencia será insignificante. En el extremo inferior de su rango (500k elementos) comenzará a ver una diferencia si está haciendo muchas búsquedas. Una búsqueda binaria va a ser O (log n), mientras que una búsqueda hash será O (1), amortized . Eso no es lo mismo que realmente constante, pero aún tendrías que tener una función hash bastante terrible para obtener un peor rendimiento que una búsqueda binaria.

(Cuando digo "terrible hash", me refiero a algo como:

hashCode()
{
    return 0;
}

Sí, es increíblemente rápido, pero hace que tu hash map se convierta en una lista vinculada.)

ialiashkevich escribió un código C # utilizando una matriz y un diccionario para comparar los dos métodos, pero utilizó valores largos para las claves. Quería probar algo que realmente ejecutaría una función hash durante la búsqueda, así que modifiqué ese código. Lo cambié para usar valores de cadena, y refactoré las secciones de llenado y búsqueda en sus propios métodos para que sea más fácil de ver en un generador de perfiles. También me quedé en el código que usaba los valores Long, solo como un punto de comparación. Finalmente, eliminé la función de búsqueda binaria personalizada y usé la de la clase Array .

Aquí está ese 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://.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 están en milisegundos).

500000 valores largos ...
Populate Long Dictionary: 26
Poblar Long Array: 2
Diccionario de búsqueda larga: 9
Búsqueda Long Array: 80

500000 valores de cadena ...
Rellenar matriz de cadenas: 1237
Populate String Dictionary: 46
Sort String Array: 1755
Diccionario de cadenas de búsqueda: 27
Matriz de cadenas de búsqueda: 1569

1000000 valores largos ...
Populate Long Dictionary: 58
Poblar Long Array: 5
Diccionario de búsqueda larga: 23
Búsqueda Long Array: 136

1000000 valores de cadena ...
Rellenar matriz de cadenas: 2070
Populate String Dictionary: 121
Sort String Array: 3579
Diccionario de cadenas de búsqueda: 58
Matriz de cadenas de búsqueda: 3267

3000000 valores largos ...
Populate Long Dictionary: 207
Poblar Long Array: 14
Diccionario de búsqueda larga: 75
Búsqueda Long Array: 435

3000000 Valores de cadena ...
Rellenar matriz de cadenas: 5553
Populate String Dictionary: 449
Sort String Array: 11695
Diccionario de cadenas de búsqueda: 194
Matriz de cadenas de búsqueda: 10594

10000000 valores largos ...
Populate Long Dictionary: 521
Poblar Long Array: 47
Diccionario de búsqueda larga: 202
Búsqueda Long Array: 1181

10000000 valores de cadena ...
Poblar matriz de cadenas: 18119
Populate String Dictionary: 1088
Sort String Array: 28174
Diccionario de cadenas de búsqueda: 747
Matriz de cadenas de búsqueda: 26503

Y a modo de comparación, aquí está la salida del generador de perfiles para la última ejecución del programa (10 millones de registros y búsquedas). Destaqué las funciones relevantes. Están bastante de acuerdo con las métricas de cronometraje de cronómetro anteriores.

Puede ver que las búsquedas del diccionario son mucho más rápidas que la búsqueda binaria, y (como se esperaba) la diferencia es más pronunciada cuanto mayor es la colección. Por lo tanto, si tiene una función de hash razonable (bastante rápida con pocas colisiones), una búsqueda hash debería superar la búsqueda binaria de colecciones en este rango.

Answer 10

Por supuesto, hash es el más rápido para un conjunto de datos tan grande.

Una forma de acelerarlo aún más, ya que los datos rara vez cambian, es generar código ad-hoc programáticamente para hacer la primera capa de búsqueda como una declaración de cambio gigante (si su compilador puede manejarlo), y luego bifurcar para buscar el cubo resultante.

Answer 11

Si su conjunto de objetos es realmente estático e inmutable, puede usar un hash perfecto para obtener un rendimiento O (1) garantizado. He visto a gperf mencionar algunas veces, aunque nunca tuve ocasión de usarlo yo mismo.

Answer 12

Sorprendido, nadie mencionó el hash Cuckoo, que proporciona O (1) garantizado y, a diferencia del hash perfecto, es capaz de usar toda la memoria que asigna, donde un hashing perfecto puede terminar con O (1) garantizado pero desperdiciando la mayor parte de su asignación. La advertencia? El tiempo de inserción puede ser muy lento, especialmente a medida que aumenta el número de elementos, ya que toda la optimización se realiza durante la fase de inserción.

Creo que alguna versión de esto se usa en hardware de enrutador para búsquedas en IP.

Ver el texto del enlace

Answer 13

Sospecho fuertemente que en un conjunto de problemas de tamaño ~ 1M, el hash sería más rápido.

Solo por los números:

una búsqueda binaria requeriría ~ 20 comparaciones (2 ^ 20 == 1M)

una búsqueda hash requeriría 1 cálculo hash en la clave de búsqueda, y posiblemente un puñado de comparaciones posteriores para resolver 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" hashcode: 0.0012 segundos. Comparar: 2.4 segundos.

Descargo de responsabilidad: en realidad, la evaluación comparativa de una búsqueda hash versus una búsqueda binaria podría ser mejor que esta prueba no del todo relevante. Ni siquiera estoy seguro de si GetHashCode se memora debajo del capó

Answer 14

Yo diría que depende principalmente del rendimiento de los métodos hash y comparar. Por ejemplo, cuando se usan claves de cadena que son muy largas pero aleatorias, una comparación siempre dará un resultado muy rápido, pero una función de hash predeterminada procesará la cadena completa.

Pero en la mayoría de los casos, el mapa hash debe ser más rápido.

Answer 15

Here se describe cómo se construyen los hash y porque el universo de las claves es razonablemente grande y las funciones hash están diseñadas para ser "muy inyectivas", por lo que las colisiones rara vez suceden. El tiempo de acceso para una tabla hash no es O (1) ... algo basado en algunas probabilidades. Pero, es razonable decir que el tiempo de acceso de un hash es casi siempre menor que el tiempo O (log_2 (n))