Ternary Tree Vs Hash Tabla

Question

Necesito saber si un ternary tree es mejor que un hash table.

Me encontré con esta pregunta en una respuesta a another question I had donde alguien dijo que los árboles ternarios a menudo son más rápidos que las tablas hash. Me resulta difícil de creer, así que decidí investigar un poco sobre eso.

This one website from Princeton parece ser la fuente de la creencia. Eché un vistazo al algoritmo que se describe como O (log n + k) donde n es el número de palabras almacenadas, yk es la longitud de la clave.

Me parece que la única forma en que esto podría ser más rápido es si a menudo busca elementos que aún no están almacenados. Otra cosa que me molesta es que el rastreo no continuo de un trie tiende a provocar que accedas a las páginas que se han intercambiado, pero si este es un efecto importante solo se puede ver a través de los puntos de referencia.

Ahora sé que probablemente haya ventajas y desventajas para ambos, y si es así, quiero saber cuáles son. Los puntos de referencia también son útiles.

Answer 1

Esto es muy intrigante para mí también. Pero desde el wiki que leí, decía que el árbol ternario es más rápido en la mayoría de los problemas de búsqueda. Esto no es sorprendente, porque a pesar de que la tabla hash tiene una búsqueda O (1), todavía necesita tiempo para realizar el hash. Por lo tanto, no es realmente O (1) sino más bien O (k) donde k no depende de N (número de elementos en la estructura de datos). Esto puede dar la impresión de que Hash Table es más rápido. Sin embargo, si se trata de estructuras grandes, la k se suma rápidamente y llegará un punto en el que la velocidad de búsqueda de las Tablas Hash se vuelve más lenta que el Árbol Ternario.

Answer 2

Esto es lo que deduzco de la Dr. Dobbs Article accesible desde el enlace de Princeton que diste:

1. ternarios búsqueda árboles son hasta 10% más rápido que las tablas hash sobre algunos problemas de búsqueda. A veces son más lentos, dependiendo en gran medida de la máquina utilizada.
2. Las TRT son una estructura de datos personalizada ajustada por dos de las mejores mentes de la informática: Jon Bentley y Robert Sedgewick escribieron goodtextbooks, y han hecho su parte de la programación práctica. Las tablas hash se consideran run-of-the-mill.
3. Las constantes involucradas son importantes, como dice Hao Wooi Lin.
4. En general, esto depende del problema que está resolviendo. El tiempo de desarrollo más rápido y el soporte casi omnipresente para tablas hash en muchos lenguajes de programación a menudo son más importantes que una mejora del diez por ciento en el tiempo de ejecución.

Answer 3

log (n) crece lentamente, por lo que a menudo puede requerir una gran cantidad de datos antes de que sea más lento que un algoritmo O (1) cuando se tiene en cuenta el factor constante.

Answer 4

La única manera de responder a esta pregunta es empíricamente. La respuesta depende de los detalles de su implementación, qué tipo de búsquedas hace, qué hardware tiene y qué compilador está utilizando. Puedes copiar el código C de Princeton.Si quieres probar un lenguaje funcional, Standard ML tiene tablas hash (mirar SML/NJ), y he aquí algo de ML para ternarios árboles de búsqueda:

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 5

Usted puede echar un vistazo a tstdb: http://code.google.com/p/tstdb/

Esta kv-store se basa en el Árbol de búsqueda ternario y es compatible con Memcached. Además, tstdb admite la búsqueda de prefijos y la consulta de rango facilitada por el Árbol de búsqueda de ternario.