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

Ответ 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 поддерживает поиск по префиксам и запрос диапазона, которым способствует тройное дерево поиска.