¿Sigue siendo una buena idea para las arquitecturas modernas?

Question

Una de mis estructuras de datos favoritas en la universidad fue el Trie. Es una gran estructura de datos para mantener un gran conjunto de cadenas si los prefijos se comparten. Las búsquedas también son agradables, ya que se realizan en O (| longitud |) de la cadena independientemente de cuántas cadenas hay en el conjunto.

En comparación, un árbol equilibrado sería O (log N) en el número de elementos establecidos, más lo que pague por las comparaciones. Una tabla hash implicaría el cálculo de hash, comparación, etc.

Me sorprende que there is no Trie implementation in the standard library of most languages.

La única razón por la que se me ocurrió fue la posibilidad de que los costos de acceso a la memoria lo hagan demasiado caro. En lugar de investigar ubicaciones O (log N) si realiza una búsqueda en árbol, no está haciendo O (| longitud |) ubicaciones diferentes, con todas las consecuencias. Si las cuerdas son largas, esto podría terminar siendo demasiado.

Así que me pregunto: ¿cuánto es lo que acabo de describir una preocupación? ¿Qué haces cuando necesitas almacenar un conjunto grande o un mapa de cadenas?

Answer 1

No había pensado en esto como un área de preocupación antes, pero ahora que lo menciona, hay momentos en que una implementación estándar de Trie podría ser útil. Por otro lado, hasta donde yo sé, Tries es usado por Python y Perl y otros lenguajes que uso ahora.

La última vez que revisé, que era hace años, el código del kernel BSD usaba Tries (Patricia Tries) en el código para seleccionar la mejor interfaz para enviar paquetes. Parece Wikipedia has some info.

Answer 2

Podrías crear dos aplicaciones de muestra y ver cuál funciona mejor. El acceso a la memoria es económico, suponiendo que no se produce un error de página. Entonces es muy caro Para el desarrollo de aplicaciones cliente, casi siempre es mejor procesar que acceder a la memoria por esta misma razón. Los procesadores modernos son ridículamente rápidos, pero las fallas de caché aún duelen.

Answer 3

Hice algunas pruebas de rendimiento en C# con un Trie y un diccionario (una tabla hash fuertemente tipada). Encontré que el diccionario era 5-10 veces más rápido que el Trie. Tal vez mi implementación del Trie podría optimizarse un poco, pero apenas lo suficiente como para ser mucho más rápido que (o incluso tan rápido) como el Diccionario. El método ContainsKey en el diccionario está cerca de una operación O (1) (dependiendo de qué tan bueno sea el algoritmo hash), por lo que no es fácil crear una colección que supere eso siempre que el algoritmo hash sea razonablemente rápido. .

Con un IEqualityComparer personalizado puede usar casi cualquier cosa como clave en un Diccionario, lo que lo hace bastante flexible. Un Trie es un poco más limitado en lo que puedes usar como clave, por lo que limita un poco la utilidad.