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

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

13 голосов
/ 05 мая 2009

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

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

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

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

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

Ответы [ 5 ]

7 голосов
/ 05 мая 2009

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

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

Единственный способ ответить на этот вопрос - опытным путем. Ответ зависит от деталей вашей реализации, от того, какие поиски вы выполняете, какое у вас оборудование и какой компилятор вы используете. Вы можете скопировать код 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
1 голос
/ 05 мая 2009

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

0 голосов
/ 04 марта 2012

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

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

0 голосов
/ 05 мая 2009

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

...