Что быстрее: поиск по хешу или двоичный поиск?

StackOverflow https://stackoverflow.com/questions/360040

Вопрос

Когда дан статический набор объектов (статический в том смысле, что после загрузки он редко, если вообще когда-либо, меняется), в котором требуются повторные одновременные поиски с оптимальной производительностью, что лучше, HashMap или массив с двоичным поиском с использованием специального компаратора?

Является ли ответ функцией типа объекта или структуры?Производительность хеш-функции и/или равной функции?Уникальность хеша?Размер списка? Hashset размер/установленный размер?

Размер набора, который я рассматриваю, может быть от 500 тысяч до 10 метров — если эта информация окажется полезной.

Пока я ищу ответ на C#, я думаю, что настоящий математический ответ заключается не в языке, поэтому я не включаю этот тег.Однако, если есть какие-то особенности C#, о которых следует знать, эта информация желательна.

Это было полезно?

Решение

Хорошо, я постараюсь быть кратким.

Краткий ответ С#:

Проверьте два разных подхода.

.NET предоставляет вам инструменты, позволяющие изменить ваш подход с помощью одной строки кода.В противном случае используйте System.Collections.Generic.Dictionary и обязательно инициализируйте его с большим числом в качестве начальной емкости, иначе вы проведете остаток своей жизни, вставляя элементы из-за работы, которую должен выполнить GC по сбору старых массивов сегментов.

Более длинный ответ:

Хеш-таблица имеет ПОЧТИ постоянное время поиска, и для получения элемента в хеш-таблице в реальном мире не требуется просто вычислить хэш.

Чтобы добраться до элемента, ваша хеш-таблица будет делать что-то вроде этого:

  • Получить хэш ключа
  • Получите номер сегмента для этого хэша (обычно функция карты выглядит так: Bucket = hash % BucketsCount)
  • Пройдите цепочку предметов (в основном это список предметов, которые имеют одно и то же ведро, большинство хэш -атлетов используют этот метод обработки ведра/хэш -столкновений), которые начинаются с этого ведра и сравните каждый ключ с одним из предметов, который вы пытаетесь добавить/ Удалить/обновить/проверить, если содержатся.

Время поиска зависит от того, насколько «хороша» (насколько разрежен вывод) и быстра ваша хэш-функция, количество используемых вами сегментов и насколько быстро работает компаратор ключей, это не всегда лучшее решение.

Лучшее и более глубокое объяснение: http://en.wikipedia.org/wiki/Hash_table

Другие советы

Для очень маленьких коллекций разница будет незначительной.В нижней части вашего диапазона (500 тыс. элементов) вы начнете видеть разницу, если будете выполнять много поисков.Бинарный поиск будет O(log n), тогда как поиск по хешу будет O(1), амортизированный.Это не то же самое, что настоящая константа, но вам все равно придется иметь довольно ужасную хеш-функцию, чтобы получить худшую производительность, чем двоичный поиск.

(Когда я говорю «ужасный хэш», я имею в виду что-то вроде:

hashCode()
{
    return 0;
}

Да, он сам по себе невероятно быстрый, но превращает вашу хеш-карту в связанный список.)

Яляшкевич написал код C#, используя массив и словарь для сравнения двух методов, но в качестве ключей использовал длинные значения.Я хотел протестировать что-то, что фактически выполняло бы хэш-функцию во время поиска, поэтому я изменил этот код.Я изменил его, чтобы использовать строковые значения, и реорганизовал разделы заполнения и поиска в отдельные методы, чтобы их было легче увидеть в профилировщике.Я также оставил в коде значения Long, просто для сравнения.Наконец, я избавился от пользовательской функции двоичного поиска и использовал ту, что есть в Array сорт.

Вот этот код:

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

Вот результаты с коллекциями нескольких разных размеров.(Время указано в миллисекундах.)

500000 Длинные значения...
Заполнить длинный словарь:26
Заполнить длинный массив:2
Поиск в длинном словаре:9
Поиск длинного массива:80

500000 строковых значений...
Заполнить массив строк:1237
Заполнить словарь строк:46
Сортировать массив строк:1755 г.
Поиск в словаре строк:27
Поиск в массиве строк:1569

1000000 Длинные значения...
Заполнить длинный словарь:58
Заполнить длинный массив:5
Поиск в длинном словаре:23
Поиск длинного массива:136

1000000 строковых значений...
Заполнить массив строк:2070 год
Заполнить словарь строк:121
Сортировать массив строк:3579
Поиск в словаре строк:58
Поиск в массиве строк:3267

3000000 Длинные значения...
Заполнить длинный словарь:207
Заполнить длинный массив:14
Поиск в длинном словаре:75
Поиск длинного массива:435

3000000 строковых значений...
Заполнить массив строк:5553
Заполнить словарь строк:449
Сортировать массив строк:11695
Поиск в словаре строк:194
Поиск в массиве строк:10594

10000000 Длинные значения...
Заполнить длинный словарь:521
Заполнить длинный массив:47
Поиск в длинном словаре:202
Поиск длинного массива:1181

10000000 Строковые значения...
Заполнить массив строк:18119
Заполнить словарь строк:1088
Сортировать массив строк:28174
Поиск по словарю строк:747
Поиск в массиве строк:26503

И для сравнения, вот результат профилировщика для последнего запуска программы (10 миллионов записей и поисков).Я выделил соответствующие функции.Они довольно близко согласуются с приведенными выше показателями секундомера.

Profiler output for 10 million records and lookups

Вы можете видеть, что поиск по словарю выполняется намного быстрее, чем двоичный поиск, и (как и ожидалось) разница тем заметнее, чем больше коллекция.Итак, если у вас есть разумная функция хеширования (довольно быстрая и с небольшим количеством коллизий), поиск по хешу должен превосходить двоичный поиск для коллекций в этом диапазоне.

Ответы Бобби, Билла и Корбина неверны.O(1) не медленнее, чем O(log n) для фиксированного/ограниченного n:

log(n) постоянен, поэтому он зависит от постоянного времени.

А что касается медленной хэш-функции, вы когда-нибудь слышали о md5?

Алгоритм хеширования строк по умолчанию, вероятно, затрагивает все символы и может быть в 100 раз медленнее, чем средний алгоритм сравнения для длинных строковых ключей.Был там, сделал это.

Возможно, вы сможете (частично) использовать систему счисления.Если вы можете разделить на 256 блоков примерно одинакового размера, вы получите двоичный поиск от 2 до 40 тысяч.Вероятно, это обеспечит гораздо лучшую производительность.

Редактировать] Слишком много людей, голосующих за то, что они не понимают.

Сравнение строк при двоичном поиске отсортированных наборов имеет очень интересное свойство:они становятся медленнее, чем ближе они подходят к цели.Сначала они сломаются на первом символе, в итоге только на последнем.Предположение о постоянном времени для них неверно.

Единственный разумный ответ на этот вопрос:Это зависит.Это зависит от размера ваших данных, формы ваших данных, вашей реализации хэша, реализации двоичного поиска и места хранения ваших данных (даже если это не упоминается в вопросе).Пара других ответов говорит то же самое, поэтому я мог бы просто удалить это.Однако было бы неплохо поделиться тем, что я узнал из отзывов о своем первоначальном ответе.

  1. Я написал, "Алгоритмы хеширования — O(1), а двоичный поиск — O(log n).» — Как отмечено в комментариях, нотация Big O оценивает сложность, а не скорость.Это абсолютно верно.Стоит отметить, что мы обычно используем сложность, чтобы понять требования алгоритма ко времени и пространству.Итак, хотя глупо полагать, что сложность строго равна скорости, оценка сложности без учета времени и пространства в глубине души — это необычно.Моя рекомендация:избегайте обозначения Big O.
  2. Я написал, "Итак, когда n приближается к бесконечности...» — это самое глупое, что я мог бы включить в ответ.Бесконечность не имеет никакого отношения к вашей проблеме.Вы упоминаете верхнюю границу в 10 миллионов.Игнорируйте бесконечность.Как отмечают комментаторы, очень большие числа создадут всевозможные проблемы с хешем.(Очень большие числа также не делают бинарный поиск прогулкой по парку.) Моя рекомендация:не упоминайте бесконечность, если вы не имеете в виду бесконечность.
  3. Также из комментариев:остерегайтесь хэшей строк по умолчанию (вы хэшируете строки?Вы не упоминаете.), индексы базы данных часто представляют собой b-деревья (пища для размышлений).Моя рекомендация:рассмотрите все ваши варианты.Рассмотрим другие структуры данных и подходы...как старомодный попробовать (для хранения и извлечения строк) или R-дерево (для пространственных данных) или МА-ФСА (Минимальный ациклический автомат с конечным состоянием - небольшой объем памяти).

Учитывая комментарии, можно предположить, что люди, использующие хеш-таблицы, невменяемы.Являются ли хеш-таблицы безрассудными и опасными?Эти люди сумасшедшие?

Оказывается, это не так.Точно так же, как двоичные деревья хороши в определенных вещах (порядковый обход данных, эффективность хранения), хеш-таблицы тоже имеют свой момент проявить себя.В частности, они могут очень хорошо сократить количество операций чтения, необходимых для получения данных.Алгоритм хеширования может генерировать местоположение и сразу переходить к нему в памяти или на диске, в то время как двоичный поиск считывает данные во время каждого сравнения, чтобы решить, что читать дальше.Каждое чтение может привести к промаху в кэше, что на порядок (или более) медленнее, чем инструкция ЦП.

Это не значит, что хеш-таблицы лучше двоичного поиска.Они не.Это также не означает, что все реализации хеш- и двоичного поиска одинаковы.Они не.Если у меня есть точка зрения, то она такова:оба подхода существуют не просто так.Вам решать, что лучше всего соответствует вашим потребностям.

Оригинальный ответ:

Алгоритмы хеширования — O(1), а двоичный поиск — O(log n).Таким образом, по мере приближения к бесконечности производительность хэша улучшается по сравнению с бинарным поиском.Ваш пробег будет варьироваться в зависимости от N, вашей хэш -реализации и вашей бинарной реализации поиска.

Интересное обсуждение O(1).Перефразировано:

O(1) не означает мгновенное.Это означает, что производительность не меняется по мере роста размера n.Вы можете спроектировать алгоритм хеширования, который настолько медленный, никто никогда не будет его использовать, и он все равно будет O (1).Я довольно уверен, что .net/c# не страдает от затрат на хеширование, однако;)

Если ваш набор объектов действительно статичен и неизменен, вы можете использовать идеальный хеш чтобы получить гарантированную производительность O (1).я видел gperf упоминался несколько раз, хотя сам мне ни разу не довелось им воспользоваться.

Хэши обычно работают быстрее, хотя двоичный поиск имеет лучшие характеристики в худшем случае.Доступ к хешу обычно представляет собой расчет для получения значения хеш-функции, чтобы определить, в каком «корзине» будет находиться запись, поэтому производительность обычно зависит от того, насколько равномерно распределены записи, а также от метода, используемого для поиска в корзине.Плохая хэш-функция (оставляющая несколько сегментов с большим количеством записей) с линейным поиском по сегментам приведет к медленному поиску.(С другой стороны, если вы читаете данные с диска, а не из памяти, хеш-корзины, скорее всего, будут смежными, а двоичное дерево в значительной степени гарантирует нелокальный доступ.)

Если вы хотите вообще быстро, используйте хэш.Если вам действительно нужна гарантированная ограниченная производительность, вы можете использовать двоичное дерево.

Удивлен, что никто не упомянул хеширование Cuckoo, которое обеспечивает гарантированный O(1) и, в отличие от идеального хеширования, способно использовать всю выделяемую память, в то время как идеальное хеширование может привести к гарантированному O(1), но тратить большую часть его памяти. распределение.Предостережение?Время вставки может быть очень медленным, особенно при увеличении количества элементов, поскольку вся оптимизация выполняется на этапе вставки.

Я считаю, что какая-то версия этого используется в оборудовании маршрутизатора для поиска IP.

Видеть текст ссылки

Словарь/Hashtable использует больше памяти и занимает больше времени для заполнения по сравнению с массивом.Но поиск по словарю выполняется быстрее, чем по двоичному поиску внутри массива.

Вот цифры для 10 Миллион Int64 элементы для поиска и заполнения.Плюс пример кода, который вы можете запустить самостоятельно.

Словарная память: 462,836

Память массива: 88,376

Заполнить словарь: 402

Заполнить массив: 23

Поиск по словарю: 176

Поисковый массив: 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;
        }
    }
}

Я сильно подозреваю, что в наборе задач размером ~ 1M хеширование будет быстрее.

Просто для цифр:

двоичный поиск потребует ~ 20 сравнений (2 ^ 20 == 1M)

поиск по хэшу потребует 1 вычисления хеша по ключу поиска и, возможно, нескольких сравнений впоследствии для разрешения возможных коллизий

Редактировать:цифры:

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

раз:c = "abcde", d = "rwerij" хеш-код:0,0012 секунды.Сравнивать:2,4 секунды.

отказ от ответственности:На самом деле сравнение хеш-поиска с двоичным поиском может быть лучше, чем этот не совсем значимый тест.Я даже не уверен, что GetHashCode запоминается скрыто.

Я бы сказал, что это зависит главным образом от производительности методов хеширования и сравнения.Например, при использовании очень длинных, но случайных строковых ключей сравнение всегда даст очень быстрый результат, но хеш-функция по умолчанию будет обрабатывать всю строку.

Но в большинстве случаев хеш-карта должна работать быстрее.

Интересно, почему никто не упомянул идеальное хеширование.

Это актуально только в том случае, если ваш набор данных фиксирован в течение длительного времени, но он анализирует данные и создает идеальную хэш-функцию, которая гарантирует отсутствие коллизий.

Довольно удобно, если ваш набор данных постоянен, а время расчета функции невелико по сравнению со временем выполнения приложения.

Это зависит от того, как вы обрабатываете дубликаты хеш-таблиц (если вообще).Если вы хотите разрешить дубликаты хэш-ключей (ни одна хеш-функция не идеальна), для поиска первичного ключа остается O(1), но поиск «правильного» значения может оказаться дорогостоящим.Ответ таков: теоретически в большинстве случаев хэши работают быстрее.YMMV в зависимости от того, какие данные вы туда поместите...

Здесь описано, как строятся хэши, и поскольку Вселенная ключей достаточно велика, а хеш-функции построены так, чтобы быть «очень инъективными», поэтому коллизии случаются редко, время доступа для хеш-таблицы на самом деле не равно O (1) ...это нечто, основанное на некоторых вероятностях.Но разумно сказать, что время доступа к хешу почти всегда меньше времени O(log_2(n))

Конечно, хэш является самым быстрым для такого большого набора данных.

Один из способов еще больше ускорить этот процесс, поскольку данные редко меняются, — это программно генерировать специальный код для выполнения первого уровня поиска в виде гигантского оператора переключения (если ваш компилятор может его обработать), а затем переходить к поиску. получившееся ведро.

Ответ зависит.Давайте представим, что количество элементов n очень велико.Если вы умеете писать лучшую хеш-функцию с меньшим количеством коллизий, то хеширование — лучший вариант.Обратите внимание, чтоХэш-функция выполняется только один раз при поиске и направляется в соответствующую корзину.Так что это не большие накладные расходы, если n велико.
Проблема в хеш-таблице:Но проблема в хеш-таблицах заключается в том, что если хеш-функция не очень хорошая (происходит больше коллизий), то поиск не равен O(1).Оно стремится к O(n), поскольку поиск в корзине является линейным поиском.Может быть хуже, чем двоичное дерево. проблема в двоичном дереве:В двоичном дереве, если дерево не сбалансировано, оно также стремится к O(n).Например, если вы вставили 1,2,3,4,5 в двоичное дерево, скорее всего, это будет список. Так,Если вы можете увидеть хорошую методологию хэширования, используйте хэш -таблицу, если нет, вам лучше использовать двоичное дерево.

Это скорее комментарий к ответу Билла, потому что его ответ получил так много голосов, хотя он и неверен.Поэтому мне пришлось опубликовать это.

Я вижу много дискуссий о том, какова наихудшая сложность поиска в хеш-таблице и что считается амортизированным анализом, а что нет.Пожалуйста, проверьте ссылку ниже

Сложность выполнения хеш-таблицы (вставка, поиск и удаление)

сложность в худшем случае равна O(n), а не O(1), в отличие от того, что говорит Билл.И, таким образом, его сложность O (1) не амортизируется, поскольку этот анализ можно использовать только для худших случаев (также об этом говорит его собственная ссылка в Википедии)

https://en.wikipedia.org/wiki/Hash_table

https://en.wikipedia.org/wiki/Amortized_anaанализ

Этот вопрос сложнее, чем вопрос о производительности чистого алгоритма.Если мы удалим факторы, согласно которым алгоритм двоичного поиска более дружественен к кэшу, поиск по хешу в общем смысле будет быстрее.Лучший способ выяснить это — создать программу и отключить параметры оптимизации компилятора, и мы могли бы обнаружить, что поиск по хешу выполняется быстрее, учитывая, что эффективность времени его алгоритма равна O (1) в общем смысле.

Но когда вы включаете оптимизацию компилятора и пробуете тот же тест с меньшим количеством выборок, скажем, менее 10 000, двоичный поиск превзошёл поиск по хешу, воспользовавшись преимуществами своей структуры данных, удобной для кэша.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top