data-structures functional-programming statistics avl-tree red-black-tree

data structures - Desempeño estadístico de mapas y conjuntos puramente funcionales



data-structures functional-programming (1)

Estos son básicamente temas de investigación, y los resultados generalmente se dan en forma de conclusiones, mientras que los datos estadísticos están ocultos. Sin embargo, uno puede tener un análisis estadístico de sus propios datos.

Para los puntos de referencia, mejor revise los detalles de implementación.

La tercera parte de la pregunta es muy subjetiva, y las intenciones reales pueden no conocerse al momento de la implementación. Sin embargo, los lenguajes como Perl hacen todo lo posible para implementar soluciones altamente optimizadas para cada operación.

Lo siguiente podría ser de ayuda: Estructuras de Datos Puramente Funcionales por Chris Okasaki http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

Dada una especificación de estructura de datos tal como un mapa puramente funcional con límites de complejidad conocidos, uno tiene que elegir entre varias implementaciones. Existe algo de folclore sobre cómo elegir el adecuado, por ejemplo, se considera que los árboles Rojo-Negros son generalmente más rápidos, pero los árboles AVL tienen un mejor rendimiento en cargas de trabajo con muchas búsquedas.

  1. ¿Hay una presentación sistemática (documento publicado) de este conocimiento (en relación con los conjuntos / mapas)? Idealmente, me gustaría ver el análisis estadístico realizado en el software real. Podría concluir, por ejemplo, que hay N tipos típicos de uso de mapas, y enumerar la distribución de probabilidad de entrada para cada uno.

  2. ¿Hay puntos de referencia sistemáticos que prueban el mapa y establecen el rendimiento en diferentes distribuciones de entradas?

  3. ¿Hay implementaciones que utilizan algoritmos adaptativos para cambiar la representación según el uso real?