Как мне выбрать между хеш-таблицей и деревом префиксов?
-
05-07-2019 - |
Вопрос
Итак, если мне придется выбирать между хеш-таблицей или деревом префиксов, каковы отличительные факторы, которые заставят меня выбрать один из них, а не другой?С моей наивной точки зрения кажется, что использование дерева имеет некоторые дополнительные накладные расходы, поскольку оно не хранится в виде массива, но с точки зрения времени выполнения (при условии, что самый длинный ключ - это самое длинное английское слово) это может быть по сути O (1) (относительно верхней границы).Может быть, самое длинное английское слово состоит из 50 символов?
Хэш-таблицы мгновенно ищутся. как только вы получите индекс.Однако хеширование ключа для получения индекса может легко занять около 50 шагов.
Может ли кто-нибудь дать мне более опытный взгляд на этот вопрос?Спасибо!
Решение
Плюсы попыток:
Основы:
- Предсказуемое время поиска O(k), где k — размер ключа.
- Поиск может занять меньше k времени, если его там нет.
- Поддерживает упорядоченный обход
- Нет необходимости в хеш-функции
- Удаление не вызывает затруднений
Новые операции:
- Вы можете быстро найти префиксы ключей, перечислить все записи с заданным префиксом и т. д.
Преимущества связанной структуры:
- Если имеется много общих префиксов, требуемое для них пространство является общим.
- Неизменяемые попытки могут иметь общую структуру.Вместо обновления дерева на месте вы можете создать новое, отличающееся только по одной ветке, в другом месте указывая на старое дерево.Это может быть полезно для параллелизма, нескольких одновременных версий таблицы и т. д.
- Неизменяемое дерево является сжимаемым.То есть он может разделять структуру на суффиксы а также с помощью хеширования.
Преимущества хеш-таблиц:
- Все знают хеш-таблицы, верно?Ваша система уже будет иметь хорошую, хорошо оптимизированную реализацию, работающую быстрее, чем пытается для большинства целей.
- Ваши ключи не обязательно должны иметь специальную структуру.
- Более эффективно использует пространство, чем очевидная структура связанного дерева (см. комментарии ниже)
Другие советы
Все зависит от того, какую проблему вы пытаетесь решить. Если все, что вам нужно, это вставки и поиск, используйте хеш-таблицу. Если вам необходимо решить более сложные проблемы, такие как запросы, связанные с префиксами, лучше использовать три.
Все знают хеш-таблицу и ее использование, но это не совсем постоянное время поиска, это зависит от размера хеш-таблицы, сложности вычислений хеш-функции.
Создание огромных хеш-таблиц для эффективного поиска не является элегантным решением в большинстве промышленных сценариев, где важны даже небольшая задержка / масштабируемость (например, высокочастотная торговля). Вы должны позаботиться о том, чтобы структуры данных были оптимизированы для пространства, которое он также занимает в памяти, чтобы уменьшить потерю кэша.
Очень хорошим примером, когда trie лучше соответствует требованиям, является промежуточное ПО для обмена сообщениями. У вас есть миллион подписчиков и издателей сообщений различных категорий (в терминах JMS - темы или обмены), в таких случаях, если вы хотите отфильтровать сообщения по темам (которые на самом деле являются строками), вам определенно не нужно создавать хеш-таблицу за миллион подписок с миллионами тем. Лучшим подходом является сохранение тем в три файла, поэтому, когда фильтрация выполняется на основе совпадения тем, ее сложность не зависит от количества тем / подписок / издателей (зависит только от длины строки). Мне это нравится, потому что вы можете проявить творческий подход к этой структуре данных, чтобы оптимизировать требования к пространству и, следовательно, снизить кэш-память. Р>
Использовать дерево:
<Ол>HashTable занимает меньше места по сравнению с базовой реализацией Trie . Но со строками порядок необходим в большинстве практических приложений. Но HashTable полностью нарушает лексографический порядок. Теперь, если ваше приложение выполняет операции, основанные на лексографическом порядке (например, частичный поиск, все строки с заданным префиксом, все слова в отсортированном порядке), вы должны использовать Tries. Только для поиска следует использовать HashTable (так как это дает минимальное время поиска).
P.S.: . Помимо этого, деревья троичного поиска (TSTs) были бы отличным выбором. Его время поиска больше, чем у HashTable, но экономит время во всех других операциях. Кроме того, это более экономно, чем пытается.
Есть кое-что, что я не видел, чтобы кто-то прямо упоминал, и думаю, что это важно иметь в виду. Как в хеш-таблицах, так и в попытках различных типов обычно используются операции O (k)
, где k
- длина строки в битах (или эквивалентно в символах). Р>
Предполагается, что у вас есть хорошая хеш-функция. Если вы не хотите " ферму " и «сельскохозяйственные животные»; чтобы хэшировать до того же значения, тогда хеш-функция должна будет использовать все биты ключа, и, таким образом, хэшировать «сельскохозяйственные животные» должно занять примерно вдвое больше времени, чем "ферма" (если вы не находитесь в каком-то сценарии с переменным хэшем, но есть и несколько похожих сценариев сохранения операций с попытками). И с ванильной попыткой понятно, зачем вставлять «фермерские животные» займет примерно вдвое больше времени, чем просто "ферма". В долгосрочной перспективе это верно и для сжатых попыток.
Вставка и поиск в дереве являются линейными с длиной входной строки O (s).
Хеш даст вам O (1) для поиска и вставки, но сначала вы должны вычислить хеш на основе входной строки, которая снова равна O (s).
Заключение, асимптотическая сложность по времени линейна в обоих случаях.
С точки зрения данных у этого дерева есть некоторые дополнительные издержки, но вы можете выбрать сжатый файл, который снова, более или менее, связывает вас с хэш-таблицей.
Чтобы разорвать связь, задайте себе вопрос: мне нужно искать только полные слова? Или мне нужно вернуть все слова, соответствующие префиксу? (Как и в системе интеллектуального ввода текста). Для первого случая перейдите к хешу. Это более простой и понятный код. Проще протестировать и поддерживать. Для более тщательно проработанного варианта использования, где префиксы или суффиксы имеют значение, попробуйте еще раз.
И если вы сделаете это просто для удовольствия, реализация трия поможет вам в воскресенье днем.
Некоторые (обычно встроенные приложения реального времени) требуют, чтобы время обработки не зависело от данных. В этом случае хеш-таблица может гарантировать известное время выполнения, а время обработки зависит от данных.