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

Question

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

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

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

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

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

Answer 1

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

1. В некоторых задачах поиска троичные деревья поиска работают на 10% быстрее, чем хеш-таблицы. Иногда они медленнее - в значительной степени зависит от используемой машины.
2. TRT - это пользовательская структура данных, настроенная двумя лучшими умами компьютерной науки - Джон Бентли и Роберт Седжвик, оба написали хорошие учебники и внесли свой вклад в практическое программирование. Хеш-таблицы считаются заурядными.
3. Включенные константы являются значительными, как говорит Хао Вуй Лин.
4. В целом, это зависит от проблемы, которую вы решаете. Более быстрое время разработки и почти повсеместная поддержка хеш-таблиц во многих языках программирования часто важнее, чем десятипроцентное улучшение времени выполнения.

Answer 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

Answer 3

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

Answer 4

Вы можете взглянуть на tstdb: http://code.google.com/p/tstdb/

Этот kv-store основан на Ternary Search Tree и совместим с Memcached. Более того, tstdb поддерживает поиск префиксов и запрос диапазона, что облегчается троичным деревом поиска.

Answer 5

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