Как мне выбрать между хеш-таблицей и деревом префиксов?

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

Вопрос

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

Хэш-таблицы мгновенно ищутся. как только вы получите индекс.Однако хеширование ключа для получения индекса может легко занять около 50 шагов.

Может ли кто-нибудь дать мне более опытный взгляд на этот вопрос?Спасибо!

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

Решение

Плюсы попыток:

Основы:

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

Новые операции:

  • Вы можете быстро найти префиксы ключей, перечислить все записи с заданным префиксом и т. д.

Преимущества связанной структуры:

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

Преимущества хеш-таблиц:

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

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

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

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

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

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

Использовать дерево:

<Ол>
  • Если вам нужна функция автозаполнения
  • Найдите все слова, начинающиеся с 'a' или 'ax' и т. д.
  • Дерево суффиксов - это особая форма дерева. Суффикс-деревья имеют целый ряд преимуществ, которые хеш не может охватить.
    • Реализация

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

    P.S.: . Помимо этого, деревья троичного поиска (TSTs) были бы отличным выбором. Его время поиска больше, чем у HashTable, но экономит время во всех других операциях. Кроме того, это более экономно, чем пытается.

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

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

    Вставка и поиск в дереве являются линейными с длиной входной строки O (s).

    Хеш даст вам O (1) для поиска и вставки, но сначала вы должны вычислить хеш на основе входной строки, которая снова равна O (s).

    Заключение, асимптотическая сложность по времени линейна в обоих случаях.

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

    Чтобы разорвать связь, задайте себе вопрос: мне нужно искать только полные слова? Или мне нужно вернуть все слова, соответствующие префиксу? (Как и в системе интеллектуального ввода текста). Для первого случая перейдите к хешу. Это более простой и понятный код. Проще протестировать и поддерживать. Для более тщательно проработанного варианта использования, где префиксы или суффиксы имеют значение, попробуйте еще раз.

    И если вы сделаете это просто для удовольствия, реализация трия поможет вам в воскресенье днем.

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

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