Каковы наиболее быстродействующие параметры для неупорядоченного набора уникальных строк только для чтения?

Question

Отказ от ответственности: я понимаю, что совершенно очевидный ответ на этот вопрос HashSet<string>. Это абсурдно быстро, оно неупорядочено, и его значения уникальны.

Но мне просто интересно, потому что HashSet<T> является изменяемым классом, поэтому он имеет Add, Remove и т. Д .; и поэтому я не уверен, что базовая структура данных, которая делает эти операции возможными, приводит к определенным потерям производительности, когда речь идет о read операциях - в частности, я обеспокоен Contains.

По сути, мне интересно, каковы абсолютные быстродействующие -образующие структуры данных, которые могут предоставить метод Contains для объектов типа string. Внутри или за пределами самой .NET Framework.

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

И последнее: я не ограничиваю это только структурами данных, доступными только для чтения. Очевидно, что любая структура данных для чтения и записи может быть встроена в оболочку только для чтения. Единственная причина, по которой я даже упомянул слово «только для чтения», заключается в том, что у меня нет требования для структуры данных, позволяющей добавлять, удалять и т. Д. Однако, если она имеет эти функции, я выиграл не жалуюсь.

---

UPDATE

Ответ Морон является отличным примером того, что я ищу. A Trie * определенно выглядит как большая возможность по следующей причине: HashSet<T>.Contains зависит от GetHashCode функции некоторого IEqualityComparer<string>, которая, , насколько Я могу сказать , это O (n) ** по умолчанию в .NET. Другими словами, каждый символ в строке должен быть проверен на HashSet<string>.Contains, чтобы получить или true или false. Для Trie, только возвращаемое значение true потребует O (n) для определения ; возвращаемое значение false потенциально может вернуть намного быстрее.

Это, конечно, гипотетически. До сих пор я не писал и не сталкивался с реализацией Trie в .NET, которая может побить HashSet<string> при Contains (хотя реализация, которую я сам написал, довольно близко подошла к алфавиту «a» - «z»). Я просто говорю, это кажется возможным.

_{* Эта ссылка, кстати, также привела меня к другой интригующей / похожей возможности: DAWG .
** Здесь «n» относится к длине строки.}

Answer 1

Попытки хороши для выполнения Contains, особенно для строк из конечного алфавита.Для строки s заданная временная сложность Contains для дерева составляет O (| s |) (| s | = длина s), что является оптимальным.

Answer 2

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

• Плохая функция хеширования, которая вызывает много коллизий.Худший из них будет вырожденным поиском O (n).У вас не будет проблем со строками, они очень хорошо хэшируются.String.GetHashCode () выполняет потрясающую работу.
• Коллекция, которая сильно видоизменена многими удаленными элементами, которые были добавлены ранее.Это может привести к появлению множества пустых блоков хэша, которые должны быть пропущены итераторами.Разложение до O (n) технически возможно, хотя и довольно редко.Простой обходной путь - перестроить коллекцию путем переназначения ссылки (например, table = new HashSet (table);)

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

Answer 3

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

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

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

Answer 4

Помимо твоего удивления, Hashset - самая быстрая коллекция.

Нет более быстрого метода, потому что базовый Hashtable позволяет O (1) доступ для чтения-записи