Является ли HashSet<T> самым быстрым контейнером для поиска?

Question

Мне нужно проверить, что конкретная строка содержится в наборе других:

private bool Contains(string field)
{
   return this.Fields.Contains(field); // HashSet<string> local property
}

Какой тип контейнера лучше всего использовать, если у него только одна задача - хранить несколько строк и проверять, входит ли в них другая или нет?

Answer 1

Да, HashSet идеально подходит для этого, поскольку он содержит одно значение для поиска, в отличие от словаря, для которого требуются ключ и значение.

Answer 2

Работает ли HashSet?Конечно.Но это не тот вопрос, который вы задали.Вы просили о самый быстрый из возможных поиск.

Является ли это максимально быстрым из возможных?Нет, конечно, нет, ни в коем случае.

Во-первых, для того, чтобы говорить о "самом быстром", нам нужно точно описать, что означает "самый быстрый".Ты имеешь в виду:

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

?Пожалуйста, уточните точно, что означает "как можно быстрее".Мы можем разработать для вас алгоритм, который является теоретически как можно быстрее только если мы точно знаем, что самый быстрый из возможных значит для тебя.

Например, предположим, что вы пишете компилятор.Что-то, что мы должны постоянно делать в компиляторах, - это проверять, есть ли конкретная строка в списке строк.Возможно, мы проверяем, является ли строка ключевым словом, поэтому нам нужно посмотреть, находится ли данная строка внутри set {"int", "double", "for", "foreach", "class" ...}

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

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

Рассмотрим, например, если вы пишете реализацию среды выполнения JScript.Нам часто приходится искать строку в наборе строк:

for(i = 0; i < 10; ++i) { foo.bar(i); }

Здесь мы должны десять раз просмотреть строку "bar" внутри объекта, идентифицируемого с помощью "foo".Хэш-таблица внутри "foo", которая реализует этот поиск, при первом выполнении цикла замечает, что был использован "bar", поэтому она динамически настраивает структуру хэш-таблицы таким образом, чтобы второй со временем прохождения цикла поиск происходит быстрее.Это стратегия, которую мы использовали при нашей реализации JScript.

Теперь это оптимизирует прецедент для циклов, но делает этот прецедент потенциально медленнее, чем он мог бы быть:

for(i = 0; i < 10; ++i) { foo.bar(i); foo.blah(i); foo.abc(i); }

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

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

Можете ли вы тщательно и полностью описать, каков именно ваш вариант использования для самый быстрый возможный поиск?Существует множество алгоритмов, которые вы можете использовать для ускорения поиска, но они становятся очень сложными.