Тройное дерево против хэш-таблицы

Мне нужно знать, если тройное дерево лучше, чем хеш-таблица.

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

Этот веб-сайт из Принстона, по-видимому, является источником веры. Я взглянул на алгоритм, который описывается как O (log n + k), где n - количество сохраненных слов, а k - длина ключа.

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

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

Ответ 1

Вот что я собираю из Dr. Статья Доббса, доступная по ссылке Принстона, которую вы дали:

Тернарные деревья поиска на 10% быстрее, чем хеш-таблицы для некоторых проблем поиска. Они иногда медленнее - в значительной степени зависят от используемой машины.
TRT - это настраиваемая структура данных, настроенная двумя из лучших умов Computer Science - Джон Бентли и Роберт Седжвик оба писали good учебники, и сделали свою долю практического программирования. Хэш-таблицы считаются запущенными.
Применяемые константы значительны, как говорит Хао Ву Линь.
В целом, это зависит от проблемы, которую вы решаете. Более быстрое время разработки и почти повсеместная поддержка хеш-таблиц во многих языках программирования часто более важны, чем десятипроцентное улучшение во время выполнения.

Ответ 2

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

type key = Key.ord_key
type item = Key.ord_key list

datatype set = NODE of { key : key, lt : set, eq : set, gt : set }
             | LEAF

val empty = LEAF

fun member (_, LEAF) = false
  | member (h::t, NODE {key, lt, eq, gt}) =
      (case Key.compare (h, key)
         of EQUAL   => member(t, eq)
          | LESS    => member(h::t, lt)
          | GREATER => member(h::t, gt))
  | member ([], NODE {key, lt, eq, gt}) =
      (case Key.compare (Key.sentinel, key)
         of EQUAL   => true
          | LESS    => member([], lt)
          | GREATER => member([], gt))

exception AlreadyPresent

fun insert(h::t, LEAF) =
      NODE { key = h, eq = insert(t, LEAF), lt = LEAF, gt = LEAF }
  | insert([], LEAF) =
      NODE { key = Key.sentinel, eq = LEAF, lt = LEAF, gt = LEAF }
  | insert(h::t, NODE {key, lt, eq, gt}) =
      (case Key.compare (h, key)
         of EQUAL   => NODE {key = key, lt = lt, gt = gt, eq = insert(t, eq)}
          | LESS    => NODE {key = key, lt = insert(h::t, lt), gt = gt, eq = eq}
          | GREATER => NODE {key = key, lt = lt, gt = insert(h::t, gt), eq = eq})
  | insert([], NODE {key, lt, eq, gt}) =
      (case Key.compare (Key.sentinel, key)
         of EQUAL   => raise AlreadyPresent
          | LESS    => NODE {key = key, lt = insert([], lt), gt = gt, eq = eq}
          | GREATER => NODE {key = key, lt = lt, gt = insert([], gt), eq = eq})

fun add(l, n) = insert(l, n) handle AlreadyPresent => n

Ответ 3

log (n) растет медленно, поэтому часто требуется огромное количество данных, прежде чем он будет медленнее, чем алгоритм O (1) при учете постоянного фактора.

Ответ 4

Это очень интересно для меня. Но из вики, которую я читал, он утверждал, что тройное Дерево быстрее в большинстве проблем поиска. Это неудивительно, потому что, несмотря на то, что таблица хэшей имеет O (1) поиск, вам все равно нужно время для хэширования. Таким образом, это не действительно O (1), а больше похоже на O (k), где k не зависит от N (количество элементов в структуре данных). Это может создать впечатление, что таблица Hash быстрее. Однако, если вы имеете дело с большими структурами, k быстро складывается, и наступит момент, когда скорость поиска Hash Tables становится медленнее, чем Ternary Tree.

Ответ 5

Возможно, вы посмотрите на tstdb: http://code.google.com/p/tstdb/

Это kv-хранилище основано на тройном дереве поиска и совместимо с Memcached. Более того, tstdb поддерживает поиск по префиксам и запрос диапазона, которым способствует тройное дерево поиска.