Что быстрее, поиск по хэшу или бинарный поиск?

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

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

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

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

11.12.2008 16:48:12
Что такое «поиск»? Вы хотите только проверить членство (существует ли определенный элемент или нет)? Или у вас есть пары ключ-значение, и вы хотите найти значение, связанное с каким-то ключом?
ShreevatsaR 11.12.2008 17:12:43
Зависит от уровня совершенства хэш-функции.
jmucchiello 9.11.2009 22:53:25
17 ОТВЕТОВ
РЕШЕНИЕ

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

C # краткий ответ:

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

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

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

Хеш-таблица имеет ПОСЛЕДНЕЕ постоянное время поиска, и получение элемента в хеш-таблице в реальном мире не просто требует вычисления хеша.

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

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

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

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

21
11.12.2008 17:33:24

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

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

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

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

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

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


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

Интересная дискуссия по О (1) . Перефразировано:

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

19
23.05.2017 11:54:33
Не знаю, почему за это проголосовали - хороший ответ и интересный момент. +1.
xan 11.12.2008 17:09:33
-1: обозначение Big O измеряет сложность, а не скорость относительно других алгоритмов. Утверждение, что хэши имеют O (1) и, следовательно, быстрее, чем O (log n), двоичные поиски не совсем верны.
Juliet 11.12.2008 18:18:46
И даже не практически правильно. Хеши строк по умолчанию затрагивают всю строку и могут быть намного медленнее, чем сравнения.
Stephan Eggermont 11.12.2008 21:15:16
@ Стефан: Согласен! Хорошие альтернативы - длина строки + хеш первых 8 символов или длина + хэш первых 4 + последние 4. Все, кроме использования целого.
Zan Lynx 12.08.2010 18:44:07
@Corbin - но ширина хэша накладывает постоянное ограничение на размер таблицы в любом случае, который не существует для бинарного поиска. Забудьте заменить старую 32-битную хеш-функцию, и, возможно, ваша хеш-таблица просто перестанет работать до того, как O (1) против O (log n) станет актуальным. Если вы учитываете необходимость в более широких хэшах по мере того, как таблицы становятся больше, вы в конечном итоге возвращаетесь к O (log n), где n - максимальное количество ключей в таблице (а не количество фактически представленных элементов, как в случае двоичного кода). дерево). Конечно, это критика теории - хеширование обычно быстрее на практике.
Steve314 9.02.2011 20:41:42

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

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

hashCode()
{
    return 0;
}

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

ialiashkevich написал код на C #, используя массив и словарь для сравнения двух методов, но он использовал длинные значения для ключей. Я хотел протестировать что-то, что фактически выполняло бы хеш-функцию во время поиска, поэтому я изменил этот код. Я изменил его, чтобы использовать значения String, и я реорганизовал разделы заполнения и поиска в свои собственные методы, чтобы их было легче увидеть в профилировщике. Я также оставил в коде, который использовал значения 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 Long values ​​...
Заполнить длинный словарь: 26
Заполнить длинный массив: 2
Искать в длинном словаре: 9
Искать в длинном массиве: 80

500000 String values ​​...
Заполнить строковый массив: 1237
Заполнить строковый словарь: 46
Сортировать строковый массив: 1755
Поиск строкового словаря: 27
Поиск строкового массива: 1569

1000000 Long values ​​...
Заполнить длинный словарь: 58
Заполнить длинный массив: 5
Поиск в длинном словаре: 23
Поиск в длинном массиве: 136

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

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

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

10000000 Long values ​​...
заполнить длинный словарь: 521
заполнить длинный массив: 47
найти длинный словарь: 202
найти длинный массив: 1181

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

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

Профилировщик выводит для 10 миллионов записей и поисков

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

50
23.05.2017 12:09:40
md5 был бы совершенно неуместен как хеш для поиска значений в хеш-таблице. Это криптографический хеш.
Bill the Lizard 11.12.2008 17:10:26
Не совсем неуместно, просто медленно. И даже хорошие некриптографические хеш-функции действительно могут быть медленнее, чем бинарный поиск для небольших размеров.
Nick Johnson 11.12.2008 20:49:37
небольшая коррекция - O (1) в среднем для случайных данных и хорошей хэш-функции. Не O (1) амортизируется.
orip 11.12.2008 21:47:35
Нет, getHashCode медленнее, чем сравнение. Гораздо медленнее для длинных струн.
Stephan Eggermont 11.12.2008 23:46:11
Это немного шокирует, что за это проголосовали так много, поскольку этот ответ просто неправильный - довольно часто бинарный поиск выполняется быстрее, чем хеш-таблица. log n является довольно небольшим фактором и может легко перевешиваться эффектами кэширования, постоянными коэффициентами масштабирования и еще чем-то для данных любого размера - в конце концов, эти данные должны вписываться в эту вселенную; и практически говоря, никакие структуры данных, скорее всего, не будут содержать более 2 ^ 64 элементов, и, вероятно, не более 2 ^ 30, прежде чем вы начнете смотреть на perf немного более конкретно.
Eamon Nerbonne 15.03.2013 09:58:02

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

1
11.12.2008 16:53:40
«Нет хэш-функции идеально» - нет, это неправильно. Существует такая вещь, как идеальное хеширование с очень широкой областью применения. Простейшим случаем, конечно, является вырожденная хеш-функция h (x) = x. Обратите внимание , что это является действительным хэш - функция и есть довольно некоторые случаи , в которых используется это.
Konrad Rudolph 11.12.2008 21:32:03
@Konrad - Идеальные хэши идеальны только в очень специфическом контексте. На самом деле «идеальный» - это имя, а не описание. Нет такого понятия, как хеш-код, идеально подходящий для всех целей. Тем не менее, шансы реальной проблемы с использованием некоторых хорошо известных стандартных хеш-функций чрезвычайно малы, за исключением конкретного случая, когда злоумышленник использует сведения о том, какая хеш-функция использовалась.
Steve314 9.02.2011 22:52:11

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

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

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

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

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

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

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

38
11.12.2008 22:50:26
@ Стефан: Мы все трое сказали, что O (1) быстрее, чем O (log n). Вам также нужно посмотреть, что означает большая буква О. Он сравнивает относительное использование ресурсов алгоритмами при изменении размера входных данных. Бессмысленно говорить о фиксированном n.
Bill the Lizard 11.12.2008 17:09:28
Э-э ... @Mike: n постоянство имеет большое значение. O (log n) может быть намного быстрее, чем O (1), если n является постоянным и небольшим, то операция с постоянным временем в O (1) занимает много времени. Но невероятно маловероятно, что O (log n) будет быстрее, чем O (1), если n не является постоянным.
Claudiu 11.12.2008 17:24:12
@ Билл: вопрос был о почти неизменном наборе. Конечно, хеш может быть быстрее, но он также может иметь в 20 раз больше коллизий. Вы должны сравнить фактические реализации.
Stephan Eggermont 11.12.2008 22:27:24
На самом деле пункт о том, что сравнение строк становится медленнее по мере приближения к цели, не присущ бинарному поиску, потому что можно отслеживать общий префикс при сужении подмножества. (Не то, что кто-либо делает.)
Mike Dunlavey 12.12.2008 02:17:25
@StephanEggermont спасибо за этот ответ. Количество итераций является лишь одним из соображений производительности, так как при меньшем n время поиска для двоичного поиска вполне может превзойти хэш-карту.
Justin Meiners 26.03.2017 18:20:54

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

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

2
11.12.2008 16:54:54
нет никакой причины, по которой хеш-функция должна использовать всю строку.
Javier 11.12.2008 17:48:16
Просто очень практичный, вы не хотите, чтобы все расширения строки заканчивались в одном и том же сегменте (если только вы не используете его как своеобразное основание и не удалили префикс из элементов блока, преобразовав его в трип-подобный структура)
Stephan Eggermont 11.12.2008 23:27:42

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

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

6
11.12.2008 16:58:07
деревья также имеют вырожденные случаи, которые фактически превращаются в список. Конечно, большинство вариаций имеют строгие инварианты, чтобы их избежать.
Javier 11.12.2008 17:50:04
Вводящий в заблуждение ответ. Проблема производительности, часто ломающая хеширование на практике, заключается в хэш-функции, а не в коллизиях.
Stephan Eggermont 11.12.2008 23:41:58
@Javier - практические двоичные деревья (AVL, красно-черные и т. Д.) Не имеют таких вырожденных случаев. Тем не менее, некоторые хеш-таблицы также не используются, так как стратегия обработки столкновений является выбором. IIRC, разработчик D, использовал (несбалансированную) схему двоичного дерева для обработки коллизий хеш-таблиц для Dscript и благодаря этому значительно улучшил производительность в среднем случае.
Steve314 9.02.2011 20:54:11

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

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

0
11.12.2008 17:18:08
Специальная оболочка первого слоя, безусловно, стоит попробовать.
Stephan Eggermont 11.12.2008 23:50:13
Я думаю, у меня есть слабость к генерации кода, хотя бы потому, что ни одна из основных популярных «методологий» не может сказать вам, когда это победа.
Mike Dunlavey 12.12.2008 02:10:05
У меня есть генератор кода, который генерирует вложенные операторы switch для дерева решений. Иногда он генерирует gotos (потому что это ациклический орграф). Но «переключатель» не алгоритм. Компилятор может использовать жестко запрограммированный двоичный поиск или таблицу поиска (структурированную одним из нескольких способов - может быть, простым массивом, возможно, хеш-таблицей, возможно, массивом с двоичным поиском), или чем-то еще. Я, возможно, переусердствую здесь - жестко запрограммированный двоичный поиск и простой массив, безусловно, существуют в реальных компиляторах, но помимо этого - компиляторы делают хорошую работу, и этого достаточно.
Steve314 9.02.2011 23:21:09
@ Steve314: Вы делаете это так, как я. «switch» создает таблицу переходов, если соответствующие случаи смежны, и это алгоритм. Я никогда не слышал о компиляторе, генерирующем if-дерево для переключателя, но это было бы потрясающе, если бы он это сделал, и это другой алгоритм. Во всяком случае, генерация кода может быть действительно большой победой. Это зависит от того, какую таблицу вы ищете, будучи относительно статичным.
Mike Dunlavey 10.02.2011 00:10:29
@Mike - сейчас я точно не могу вспомнить, был ли это GCC или VC ++ (скорее всего, GCC), но я видел if-дерево в разборке сгенерированного кода. Что касается относительно статического, мой генератор кода выполняет многократную диспетчеризацию, и множество возможных реализаций для полиморфной функции, конечно, полностью статично во время выполнения. Это не подходит для отдельной компиляции, так как вам нужно знать все случаи для построения дерева решений. Есть языки, которые делают это с отдельной компиляцией, но они строят свои деревья / таблицы решений во время выполнения (например, при первом вызове).
Steve314 10.02.2011 20:27:57

Я сильно подозреваю, что в проблемном наборе размером ~ 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 запоминается под капотом

3
11.12.2008 17:21:14
При достойном оптимизаторе результаты должны быть равны 0 для обоих.
Stephan Eggermont 11.12.2008 21:23:32

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

1
11.12.2008 18:00:34

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

7
11.12.2008 21:40:54
Если вы можете установить постоянную верхнюю границу для размера любого алгоритма или структуры данных, вы можете претендовать на оценку O (1) для его производительности. Это часто делается в реальности - например, производительность поиска в узле B-дерева считается постоянной, поскольку (независимо от линейного или двоичного поиска) максимальный размер узла постоянен. +1 за хорошее предложение, но за утверждение O (1), я думаю, вы немного обманываете.
Steve314 9.02.2011 21:21:19
@ Steve314, я думаю, ты упустил идеальный хеш. Настраивая хеш-функцию, вы гарантированно не будете иметь коллизий, так что это действительно одна операция для получения данных, когда у вас есть хеш-код, плюс одно сравнение, чтобы убедиться, что вы не искали что-то не в таблице.
Mark Ransom 9.02.2011 22:12:08
но я хочу сказать, что вы настраиваете хеш для определенного и постоянного количества данных. Вы совершенно правы в отношении преимуществ идеального хэша, но поскольку он не может справиться с изменением n (или даже с изменением данных в n, в этом отношении), он все еще обманывает.
Steve314 9.02.2011 22:45:30

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

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

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

2
11.12.2008 21:46:06

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

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

См текст ссылки

5
11.12.2008 23:04:27
Идеальное хеширование может использовать всю память, которую оно выделяет. Часто это происходит не из-за работы, связанной с поиском такой идеальной идеальной хеш-функции, но для небольших наборов данных это вполне выполнимо.
Steve314 9.02.2011 22:58:14

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

0
22.01.2014 11:09:55

Dictionary / 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;
        }
    }
}
4
17.02.2015 16:40:03

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

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

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

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

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

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

0
1.01.2019 11:32:48

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

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

0
17.08.2019 19:03:15