Co jest szybsze, Hash lookup czy Binary search?

Dla bardzo małych zbiorów różnica będzie znikoma. Na niskim końcu zakresu (500K przedmiotów) zaczniesz widzieć różnicę, jeśli robisz wiele wyszukiwań. Wyszukiwanie binarne będzie o (log n), podczas gdy wyszukiwanie hashowe będzie O (1), , . To nie to samo, co naprawdę constant, ale nadal będziesz musiał mieć dość straszną funkcję hashową, aby uzyskać gorszą wydajność niż wyszukiwanie binarne.

(Kiedy mówię "straszny hash" , mam na myśli coś like:

hashCode()
{
    return 0;
}

Tak, sama w sobie jest błyskawiczna, ale sprawia, że Twoja mapa hashowa staje się połączoną listą.)

Ialiashkevich napisał jakiś kod C# używając tablicy i słownika, aby porównać te dwie metody, ale używał długich wartości dla kluczy. Chciałem przetestować coś, co faktycznie wykonałoby funkcję hash podczas wyszukiwania, więc zmodyfikowałem ten kod. Zmieniłem go, aby używać wartości łańcuchowych, i refakturowałem sekcje wypełniania i Wyszukiwania na własne metody, więc łatwiej jest zobacz w profilerze. Zostawiłem też w kodzie, który używał długich wartości, tylko jako punkt porównania. W końcu pozbyłem się niestandardowej funkcji wyszukiwania binarnego i użyłem tej w klasie Array.

Oto ten kod:

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);
    }
}

Oto wyniki z kilku różnych rozmiarów zbiorów. (Czasy są w milisekundach.)

500000 długich wartości...
Długi Słownik: 26
Long Array: 2
Wyszukaj Długi Słownik: 9
Szukaj Long Array: 80

500000 wartości ciągów...
Populate String Array: 1237
Populate String Dictionary: 46
Sort String Array: 1755
Szukana Fraza: 27
Szukany Ciąg Array: 1569

1000000 długich wartości...
Długość Słownika: 58
Long Array: 5
Wyszukaj Długi Słownik: 23
Szukaj Long Array: 136

1000000 String wartości...
Zapełnianie Tablicy Ciągów: 2070
Słownik Haseł: 121
Sort String Array: 3579
Szukana Fraza: 58
Szukany Ciąg Array: 3267

3000000 długich wartości...
Długość Słownika: 207
Long Array: 14
Wyszukaj Długi Słownik: 75
Szukaj Long Array: 435

3000000 wartości ciągów...
Zapełnij Tablicę Ciągów: 5553
Liczba Haseł: 449
Sort String Array: 11695
Szukana Fraza: 194
Szukany Ciąg Array: 10594

10000000 długich wartości...
Długość Słownika: 521
Long Array: 47
Wyszukaj Długi Słownik: 202
Wyszukaj Long Array: 1181

10000000 wartości łańcuchowych...
Liczba Znaków: 18119
Słownik Haseł: 1088
Sort String Array: 28174
Szukana Fraza: 747
Szukany Ciąg Array: 26503

I dla porównania, oto wyjście profilera dla ostatniego uruchomienia programu(10 milionów rekordów i wyszukań). Podkreśliłem odpowiednie funkcje. Dość ściśle zgadzają się z powyższymi wskaźnikami czasu stopera.

Widać, że wyszukiwanie słownikowe jest znacznie szybsze niż wyszukiwanie binarne, a (zgodnie z oczekiwaniami) różnica jest większa im większa kolekcja. Tak więc, jeśli masz rozsądną funkcję hashowania (dość szybką z kilkoma kolizjami), wyszukiwanie hash powinno pokonać binarne wyszukiwanie kolekcji w tym zakresie.

Odpowiedzi Bobby ' ego, Billa i Corbina są błędne. O(1) nie jest wolniejsze od O (log n) dla stałej / ograniczonej n:

Log (n) jest stały, więc zależy od stałego czasu.

A dla funkcji slow hash słyszałeś kiedyś o md5?

Domyślny algorytm hashowania łańcuchów prawdopodobnie dotyka wszystkich znaków i może być łatwo 100 razy wolniejszy niż przeciętne porównanie dla długich kluczy łańcuchowych. Już to przerabiałem.

Możesz (częściowo) użyć radixa. Jeśli możesz podziel się na 256 bloków o podobnej wielkości, patrzysz na wyszukiwanie binarne od 2k do 40K. To prawdopodobnie zapewni znacznie lepszą wydajność.

[Edytuj] Zbyt wielu ludzi odrzuca to, czego nie rozumie.

Porównywanie ciągów binarnych sortowanych zestawów ma bardzo interesującą właściwość: stają się wolniejsze im bliżej celu. Najpierw będą łamać na pierwszym znaku, w końcu tylko na ostatnim. Zakładając, że stały czas dla nich jest nieprawidłowy.

Jedyna rozsądna odpowiedź na to pytanie brzmi: to zależy. Zależy to od rozmiaru danych, kształtu danych, implementacji hash, implementacji wyszukiwania binarnego i miejsca, w którym żyją dane (nawet jeśli nie jest to wymienione w pytaniu). Kilka innych odpowiedzi mówi tyle, więc mogę to usunąć. Jednak może być miło podzielić się tym, czego nauczyłem się od opinii do mojej oryginalnej odpowiedzi.

1. napisałem, " algorytmy Hash są O (1) podczas wyszukiwania binarnego jest O (log n). " - jak zaznaczono w komentarzach, notacja Big O szacuje złożoność, a nie szybkość. To jest absolutna prawda. Warto zauważyć, że zwykle używamy złożoności, aby uzyskać poczucie wymagań czasowych i przestrzennych algorytmu. Tak więc, podczas gdy głupotą jest zakładanie, że złożoność jest ściśle taka sama jak szybkość, szacowanie złożoności bez czasu i przestrzeni w głębi umysłu jest niezwykłe. Moja rekomendacja: unikaj notacji Big O.
2. napisałem: " tak jak n zbliża się do nieskończoności ..."- To to najgłupsza rzecz, jaką mogłem zawrzeć w odpowiedzi. Nieskończoność nie ma nic wspólnego z Twoim problemem. Wspomniałeś o górnej granicy 10 milionów. Ignoruj nieskończoność. Jak podkreślają komentatorzy, bardzo duże liczby spowodują różnego rodzaju problemy z Hashem. (Bardzo duże liczby nie sprawiają, że wyszukiwanie binarne to spacer po parku.) Moje zalecenie: nie wspominaj o nieskończoności, chyba że masz na myśli nieskończoność.
3. również z komentarzy: uważaj na domyślne hashe łańcuchów (czy hashujesz łańcuchy? Ty nie wspominaj.), indeksy baz danych są często drzewami b (food for thought). Moje zalecenie: rozważ wszystkie opcje. Rozważ inne struktury danych i podejścia... podobnie jak staromodny trie (do przechowywania i pobierania łańcuchów) lub R-tree (do danych przestrzennych) lub MA-FSA (Minimal Acyclic Finite State Automaton-small storage footprint).

Biorąc pod uwagę komentarze, można założyć, że ludzie, którzy używają tabel hash są obłąkani. Czy tabele hash lekkomyślny i niebezpieczny? Czy ci ludzie są szaleni?

Okazuje się, że nie. Podobnie jak drzewa binarne są dobre w pewnych rzeczach (przepływ danych w kolejności, wydajność przechowywania), tabele hash mają również swój moment, aby zabłysnąć. W szczególności mogą być bardzo dobre w zmniejszaniu liczby odczytów wymaganych do pobrania danych. Algorytm hashowy może wygenerować lokalizację i przeskoczyć bezpośrednio do niej w pamięci lub na dysku, podczas gdy wyszukiwanie binarne odczytuje dane podczas każdego porównania, aby zdecydować, co dalej czytać. Każdy read może spowodować brak pamięci podręcznej, która jest o rząd wielkości (lub więcej) wolniejsza niż instrukcja procesora.

To nie znaczy, że tabele hash są lepsze niż wyszukiwanie binarne. Nie są. Nie chodzi również o to, aby sugerować, że wszystkie implementacje hash i wyszukiwania binarnego są takie same. Nie są. Jeśli mam rację, to jest tak: oba podejścia istnieją nie bez powodu. To do ciebie należy decyzja, który jest najlepszy dla Twoich potrzeb.

Oryginalna odpowiedź:

Algorytmy Hash są O (1) podczas gdy wyszukiwanie binarne to o (log n). Tak jak n zbliża się do nieskończoności, wydajność hash poprawia się w stosunku do binarnych Szukaj. Twój przebieg będzie się różnić w zależności od n, Twój hash implementacja, oraz implementacja wyszukiwania binarnego.

Ciekawa dyskusja na temat O (1) . Parafrazowany:

O(1) nie oznacza chwilowego. Oznacza to, że wykonanie nie zmiana w miarę wzrostu rozmiaru N. Możesz zaprojektować algorytm haszujący to tak powolne, że nikt nigdy by tego nie użył i nadal byłoby O (1). Jestem całkiem pewien, że. Net / C# nie cierpi z powodu wygórowanego kosztowo hashowania, jednak ;)

Jeśli twój zestaw obiektów jest naprawdę statyczny i niezmienny, możesz użyć perfect hash , aby uzyskać gwarancję wydajności O(1). Widziałem gperf wspomniany kilka razy, choć sam nigdy nie miałem okazji go użyć.

Hasze są zazwyczaj szybsze, chociaż wyszukiwanie binarne ma lepsze cechy najgorszego przypadku. Dostęp do skrótu jest zazwyczaj obliczaniem, które ma na celu uzyskanie wartości skrótu w celu określenia, w którym "zasobniku" będzie znajdować się rekord, a więc wydajność będzie zasadniczo zależeć od równomiernego rozłożenia rekordów i metody używanej do wyszukiwania zasobnika. Zła funkcja hash (pozostawiająca kilka łyżek z dużą ilością rekordów) z przeszukiwaniem liniowym przez łyżki spowoduje powolne wyszukiwanie. (Na po trzecie, jeśli czytasz dysk, a nie pamięć, łyżki skrótu prawdopodobnie będą sąsiadować, podczas gdy drzewo binarne praktycznie gwarantuje dostęp nielokalny.)

Jeśli chcesz ogólnie szybko, Użyj hash. Jeśli naprawdę chcesz mieć gwarantowaną ograniczoną wydajność, możesz wybrać drzewo binarne.

Dziwi mnie, że nikt nie wspomniał o Cuckoo hashing, które zapewnia gwarantowane O(1) i w przeciwieństwie do doskonałego hashowania, jest w stanie wykorzystać całą przydzieloną pamięć, gdzie jako doskonałe hashing może skończyć się gwarantowanym O(1), ale marnując większą część jego przydziału. Zastrzeżenie? Czas wstawiania może być bardzo powolny, zwłaszcza, że liczba elementów wzrasta, ponieważ cała optymalizacja jest wykonywana podczas fazy wstawiania.

Wydaje mi się, że jakaś wersja tego jest używana w routerze sprzęt do wyszukiwania ip.

Zobacz link text

Słownik / Hashtable zużywa więcej pamięci i zajmuje więcej czasu w porównaniu do tablicy. Ale wyszukiwanie odbywa się szybciej przez słownik, a nie binarne wyszukiwanie w tablicy.

Oto liczby dla 10 milion Int64 elementów do przeszukania i wypełnienia. Plus przykładowy kod, który możesz uruchomić samodzielnie.

Pamięć Słownika: 462,836

Pamięć Tablicy: 88,376

Słownik: 402

Populate Array: 23

Search Dictionary: 176

Tablica Wyszukiwania: 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;
        }
    }
}

Mocno podejrzewam, że w problemowym zestawie wielkości ~1M, hashowanie byłoby szybsze.

Tylko dla liczb:

Wyszukiwanie binarne wymagałoby ~ 20 porównań (2^20 == 1M)

Szukanie skrótu wymagałoby 1 obliczenia skrótu na kluczu wyszukiwania i ewentualnie kilku porównań w celu rozwiązania ewentualnych kolizji

Edit: liczby:

    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);
    }

Times: c = "abcde", d = "rwerij" hashcode: 0.0012 seconds. Porównaj: 2,4 sekundy.

Disclaimer: W rzeczywistości porównywanie hash lookup vs Binary lookup może być lepsze niż ten nie do końca istotny test. Nie jestem nawet pewien, czy GetHashCode zostanie zapamiętany pod maską

Powiedziałbym, że zależy to głównie od wydajności metod hash i compare. Na przykład, przy użyciu kluczy łańcuchowych, które są bardzo długie, ale losowe, porównanie zawsze przyniesie bardzo szybki wynik, ale domyślna funkcja skrótu przetworzy cały łańcuch.

Ale w większości przypadków Mapa hash powinna być szybsza.

Zastanawiam się, dlaczego nikt nie wspomniał o doskonałym hashowaniu .

Ma to znaczenie tylko wtedy, gdy zbiór danych jest stały przez długi czas, ale to, co robi, analizuje dane i konstruuje idealną funkcję skrótu, która zapewnia brak kolizji.

Całkiem niezłe, jeśli zestaw danych jest stały, a czas na obliczenie funkcji jest mały w porównaniu do czasu uruchomienia aplikacji.

To zależy od tego, jak obsłużysz duplikaty tabel hashowych (jeśli w ogóle). Jeśli chcesz zezwolić na duplikaty kluczy hashowych(żadna funkcja hash nie jest idealna), pozostaje O (1) dla wyszukiwania klucza podstawowego, ale wyszukiwanie za "właściwą" wartością może być kosztowne. Odpowiedź jest wtedy, teoretycznie większość czasu, hasze są szybsze. YMMV w zależności od tego, które dane tam umieścisz...

Tutaj jest opisane, jak budowane są hashy i ponieważ wszechświat kluczy jest dość duży, a funkcje hash są zbudowane tak, aby były" bardzo iniekcyjne", tak że kolizje rzadko się zdarzają, czas dostępu do tabeli hash nie jest w rzeczywistości O(1)... to coś oparte na pewnych prawdopodobieństwach. Ale rozsądne jest stwierdzenie, że czas dostępu do hasha jest prawie zawsze mniejszy niż czas O(log_2 (N))

Oczywiście, hash jest najszybszy dla tak dużego zbioru danych.

Jednym ze sposobów, aby przyspieszyć to jeszcze bardziej, ponieważ dane rzadko się zmieniają, jest programowo generowanie kodu ad-hoc, aby wykonać pierwszą warstwę wyszukiwania jako giant switch statement (jeśli twój kompilator może sobie z tym poradzić), a następnie rozgałęziać się, aby przeszukać wynikowe wiadro.

Odpowiedź zależy. Pomyślmy, że liczba elementów "n" jest bardzo duża. Jeśli jesteś dobry w pisaniu lepszej funkcji hash, która ma mniejsze kolizje, to haszowanie jest najlepsze. zauważ, że Funkcja hash jest wykonywana tylko raz podczas wyszukiwania i kieruje do odpowiedniego zasobnika. Więc nie jest to duży narzut, jeśli n jest wysokie.
Problem w Hashtable: Ale problem w tabelach hash jest taki, że jeśli funkcja hash nie jest dobra( zdarza się więcej kolizji), to wyszukiwanie nie jest O (1). Ma tendencję do O (n), ponieważ wyszukiwanie w wiadrze jest wyszukiwaniem liniowym. Może być gorzej niż drzewo binarne. problem w drzewie binarnym: W drzewie binarnym, jeśli drzewo nie jest zrównoważone, również ma tendencję do O (n). Na przykład, jeśli wstawiłeś 1,2,3,4,5 do drzewa binarnego, które byłoby bardziej prawdopodobne, że lista. Więc, Jeśli widzisz dobrą metodologię haszowania, użyj hashtable Jeśli nie, lepiej Użyj drzewa binarnego.