He leído un poco sobre las siguientes estructuras de datos:
- El hachís ideal de Bagwell intenta
- Tablas hash dinámicas de Larson
- Árboles rojo-negro
- Arboles patricia
... y estoy seguro de que hay muchos otros por ahí. He visto muy poco en la forma en que cada uno es más adecuado, o por qué elegiría uno sobre el otro. Entonces, aquí hay algunas preguntas en este sentido:
- ¿Qué estructuras funcionales de datos de diccionario son importantes para conocer?
- ¿Cuáles son los pros y los contras de estos enfoques?
- ¿Cuándo tiene sentido usar una estructura de datos más imperativa?
Sin embargo, los números 2 y 3 son los más importantes. :-)
Respuestas:
Realmente no puedo responder el # 2 sin perderme (hay muchas dimensiones a lo largo de las cuales puedes comparar estas estructuras), pero para el # 3 la respuesta es bastante simple.
Use una estructura de datos imperativa si: (a) no hay absolutamente ningún aliasing, o (b) realmente necesita usar aliasing para una transmisión eficiente.
Si no hay alias de su estructura de datos, entonces no está aprovechando el hecho de que las estructuras de datos funcionales son persistentes. Por lo tanto, no hay razón para pagar su costo. Hay dos advertencias a este consejo. Primero, puede preferir la simplicidad de la implementación de una estructura de datos funcional: implementar la eliminación de un árbol rojo-negro funcional lo hará maldecir, pero implementar la eliminación en un árbol rojo-negro imperativo con punteros principales lo dejará contemplando el suicidio. En segundo lugar, la asignación puede ser más costosa de lo que espera en un lenguaje gc'd, ya que las escrituras pueden sacar las estructuras de datos de la generación joven. Realmente no tenemos una buena teoría de los efectos de caché y gc, por lo que no tiene más remedio que hacer una evaluación comparativa.
En segundo lugar, si necesita un canal de transmisión, una estructura de datos compartidos es una excelente manera de hacerlo. Con una actualización de tiempo constante, puede decir arbitrariamente a muchas otras personas que un valor ha cambiado. (Esta es la razón por la cual union-find es una estructura de datos tan excelente). Con una configuración puramente funcional, necesita modificar a todas esas otras personas o darles punteros abstractos en un estado que codifica manualmente (que es una especie de obtuso cosas que hacer).
Si no desea razonar sobre el alias y la propiedad del objeto, o si necesita varias versiones de la misma estructura de datos (necesita una versión nueva y una antigua, por ejemplo), simplemente use una estructura de datos funcional.
El lugar donde encuentro que sigue estos consejos lo más difícil es con algoritmos gráficos. Hay muchos algoritmos de gráficos imperativos realmente elegantes, pero a menudo es el caso (por ejemplo, al escribir compiladores) que también desea persistencia. Por lo general, las personas intentan dividir la diferencia y usan el algoritmo imperativo genial, pero intentan atornillar las versiones a un lado para obtener persistencia. Esto generalmente es bastante horrible, está lleno de errores y es propenso a perder la ventaja de rendimiento del algoritmo imperativo.
fuente
Los árboles binarios de altura equilibrada y sus intentos son un buen compromiso general. También:
Los árboles binarios de altura equilibrada y sus intentos son un buen compromiso integral para las claves atómicas. Los intentos son los mismos para las teclas que son secuencias, por ejemplo, las teclas de cadena.
Los árboles de Patricia pueden ser varias veces más rápidos pero solo permiten claves enteras.
Los intentos de hash pueden ser varias veces más rápidos que los árboles binarios equilibrados, especialmente si el hash es más barato que la comparación y el polimorfismo tiene una sobrecarga (por ejemplo, cadenas en .NET) y la escritura de punteros en el montón es rápida (por ejemplo, máquinas virtuales como JVM y CLR que han sido optimizado para lenguajes imperativos en lugar de lenguajes funcionales). Los intentos de hash también permiten el uso interno de la mutación como una optimización.
Los árboles rojo-negros son menos importantes porque no tienen ningún beneficio significativo sobre los árboles de altura equilibrada, pero tienen la desventaja significativa de que no permiten una unión, intersección y diferencia eficientes.
Del mismo modo, los árboles de dedos no son mucho mejores en la práctica.
Cuando su diccionario se llena una vez y luego se usa solo para búsquedas, es decir, congelado.
Cuando necesita rendimiento (una tabla hash decente como .NET
Dictionarysuele ser 10-40 × más rápida que cualquier diccionario genérico puramente funcional).Cuando necesita un diccionario débil porque no se conoce un diccionario débil puramente funcional.
fuente