algorithm - resolucion - ¿Por qué los mapas Haskell se implementan como árboles binarios equilibrados en lugar de tablas hash tradicionales?
tablas hash c++ (4)
Por mi conocimiento limitado de Haskell, parece que se supone que los mapas (de Data.Map) se usan mucho como un diccionario o una tabla hash en otros idiomas, y sin embargo, se implementan como árboles de búsqueda binaria con equilibrio automático.
¿Por qué es esto? El uso de un árbol binario reduce el tiempo de búsqueda a O (log (n)) en lugar de O (1) y requiere que los elementos estén en Ord. Ciertamente hay una buena razón, entonces, ¿cuáles son las ventajas de usar un árbol binario?
También:
¿En qué aplicaciones sería un árbol binario mucho peor que una tabla hash? ¿Qué hay del revés? ¿Hay muchos casos en los que uno sería muy preferible al otro? ¿Hay un hashtable tradicional en Haskell?
¿Por qué es esto? El uso de un árbol binario reduce el tiempo de búsqueda a O (log (n)) en lugar de O (1)
La búsqueda es solo una de las operaciones; La inserción / modificación puede ser más importante en muchos casos; También hay consideraciones de memoria. La razón principal por la que se eligió la representación en árbol es probablemente que es más adecuada para un lenguaje funcional puro. Como dice "Real World Haskell":
Los mapas nos dan las mismas capacidades que las tablas hash en otros idiomas. Internamente, un mapa se implementa como un árbol binario equilibrado. En comparación con una tabla hash, esta es una representación mucho más eficiente en un lenguaje con datos inmutables. Este es el ejemplo más visible de cómo la programación funcional profundamente pura afecta la forma en que escribimos el código: elegimos las estructuras de datos y los algoritmos que podemos expresar de manera limpia y con un rendimiento eficiente, pero nuestras opciones para tareas específicas a menudo son diferentes a sus equivalentes en idiomas imperativos.
Esta:
y requiere que los elementos estén en ord.
No parece una gran desventaja. Después de todo, con un mapa hash necesitas claves para ser Hashable , que parece ser más restrictivo.
¿En qué aplicaciones sería un árbol binario mucho peor que una tabla hash? ¿Qué hay del revés? ¿Hay muchos casos en los que uno sería muy preferible al otro? ¿Hay un hashtable tradicional en Haskell?
Desafortunadamente, no puedo proporcionar un análisis comparativo extenso, pero hay un paquete de mapa hash , y puedes ver sus detalles de implementación y cifras de rendimiento en esta publicación del blog y decidir por ti mismo.
Las tablas hash no se pueden implementar de manera eficiente sin un estado mutable, porque se basan en la búsqueda de matrices. La clave está en hash y el hash determina el índice en una matriz de cubos. Sin un estado mutable, la inserción de elementos en la tabla hash se convierte en O (n) porque se debe copiar la matriz completa (las implementaciones alternativas sin copia, como DiffArray, introducen una penalización de rendimiento significativa ). Las implementaciones de árbol binario pueden compartir la mayor parte de su estructura, por lo que solo es necesario copiar un par de punteros en las inserciones.
Haskell ciertamente puede soportar tablas hash tradicionales, siempre que las actualizaciones estén en una mónada adecuada. El paquete hashtables es probablemente la implementación más utilizada.
Una de las ventajas de los árboles binarios y otras estructuras no mutantes es que son persistentes: es posible mantener copias antiguas de los datos sin una contabilidad adicional. Esto podría ser útil en algún tipo de algoritmo de transacción, por ejemplo. También son seguros para subprocesos automáticamente (aunque las actualizaciones no serán visibles en otros subprocesos).
Las tablas hash tradicionales se basan en la mutación de memoria en su implementación. La memoria mutable y la transparencia referencial están en los extremos, por lo que relega implementaciones de tabla hash a las mónadas IO o ST . Los árboles se pueden implementar de manera persistente y eficiente dejando las hojas antiguas en la memoria y devolviendo nuevos nodos raíz que apuntan a los árboles actualizados. Esto nos permite tener Map puros.
La referencia por excelencia es la estructura de datos puramente funcionales de Chris Okasaki.
Mi respuesta a la ventaja de usar árboles binarios sería: consultas de rango. Requieren, semánticamente, un pre-pedido total, y se benefician de una organización de árbol de búsqueda equilibrada algorítmicamente. Para una búsqueda simple, me temo que solo puede haber buenas respuestas específicas de Haskell, pero no buenas respuestas en sí mismas: la búsqueda (y, por supuesto, el hashing) solo requiere un setoid (igualdad / equivalencia en su tipo de clave), que admite el hashing eficiente en punteros (que, por buenas razones, no están ordenados en Haskell). Al igual que varias formas de intentos (p. Ej., Intentos ternarios para la actualización de elementwise, otros para las actualizaciones masivas), el hashing en matrices (abierto o cerrado) suele ser considerablemente más eficiente que la búsqueda elemental en árboles binarios, tanto espaciales como temporales. Hashing y Tries se pueden definir de forma genérica, aunque esto se debe hacer a mano. GHC no lo deriva (¿aún?). Las estructuras de datos como Data.Map tienden a estar bien para la creación de prototipos y para el código fuera de los puntos de acceso, pero cuando están calientes, fácilmente se convierten en un cuello de botella en el rendimiento. Afortunadamente, los programadores de Haskell no tienen que preocuparse por el rendimiento, solo sus gerentes. (Por alguna razón, actualmente no puedo encontrar una manera de acceder a la función de canje de claves de los árboles de búsqueda entre las más de 80 funciones de Data.Map: una interfaz de consulta de rango. ¿Estoy buscando el lugar equivocado?)