Esta pregunta está inspirada en otra pregunta sobre las novedades en PFDS desde la publicación del libro de Okasaki en 1998 .
Comenzaré con dos preguntas que tengo:
- ¿Existe una estructura de datos de conjunto puramente funcional que se aproxime a la velocidad de las tablas hash? Los intentos aún no están allí.
- ¿Hay árboles de dedos puramente funcionales con O (1) anexar? Lo mejor hasta ahora es O (lg lg n), ideado por Kaplan y Tarjan.
¿Qué otros problemas de estructura de datos puramente funcionales están abiertos?
big-list
ds.data-structures
functional-programming
revs jbapple
fuente
fuente
Respuestas:
Interpretaré la pregunta un poco liberalmente. Para las estructuras de datos de estilo Okasaki, la memorización es una forma de mutación implícita que tiene un efecto secundario en el tiempo de ejecución. Por lo tanto, tomaré la pregunta sobre estructuras de datos persistentes en sentido estricto, en lugar de estructuras de datos con una implementación puramente funcional, que son un subconjunto de las primeras. Por estricto quiero decir que debe poder acceder a versiones anteriores de una estructura de datos sin penalización, el árbol de versiones puede ramificarse arbitrariamente, etc.
En ese contexto, considero que UNION-FIND persistente es un importante problema abierto. Está el papel de Conchon-Filliâtre que se mencionó en el otro hilo. Un comentarista ya planteó un problema con su llamado arreglo persistente: en realidad es solo semipersistente. Pero suponga que lo reemplaza con un hash trie u otra matriz verdaderamente persistente que se comporta mejor en el peor (y posiblemente promedio) pero peor en el mejor de los casos. Eso todavía deja una cuestión importante abierta:
El documento da una prueba formal de corrección en Coq. Pero no abordan la complejidad amortizada ni formal ni informalmente. No me queda claro que la complicada mutación detrás de escena resulte en la complejidad amortizada esperada en todos los casos. Cuando lo pensé por última vez, me sentí algo confiado de poder construir un contraejemplo si ponía esfuerzo en ello. Incluso si me equivoco sobre esa última parte, la falta de un análisis adecuado es una brecha importante; Está claro que el análisis clásico de amortización de Trajan de UNION-FIND no se transfiere directamente.
fuente
Aquí hay uno:
¿Cuál es el equivalente puramente funcional de una tabla hash débil?
fuente