16
¿Existen implementaciones de una estructura de datos soft heap puramente funcional en cualquier idioma?Pilas blandas puramente funcionales
A
Respuesta
20
Una búsqueda rápida de la biblioteca digital de ACM indica que la estructura de montón blando de Chazelle, a pesar de ser muy interesante, ha recibido relativamente poco estudio y que los montones suaves persistentes/funcionales son un tema de investigación abierto.
Así que diría que no, no hay enfoques conocidos para los acumulados suaves persistentes. Describir uno sería un resultado publicable (puede reducirse a agregar copia en la que mutarías la estructura original e identificar oportunidades de intercambio).
+3
@Jon, si planeas abordar este problema, y aún no has leído * Estructuras de Datos Puramente Funcionales *, te sugiero que lo hagas. A pesar de que no cubre los montones suaves, le enseñará los principios básicos del diseño de la estructura de datos funcionales que serán útiles para abordar este problema. –
+1
Hay una implementación de OCaml con todas las funciones de montones oblicuos binomiales de Okasaki en mi biblioteca Oni CF: http://bitbucket.org/jhw/oni –
0
Este proyecto tiene un código Java que puede no ser demasiado terrible para traducir a Scala ... y luego hacerlo más funcional.
https://github.com/lowasser/SoftSelect
Pero como se señaló anteriormente el puramente funcional libro Estructuras de datos tiene el código de Haskell que puede ser más fácil adoptar a Soft Montones, especialmente teniendo en cuenta el ejemplo de código Java.
+0
También estoy viendo este documento del ACM donde SoftHeaps está hecho con binarios Árboles: http://dl.acm.org/citation.cfm?id=1496823 – RudeDude
1
El Haim Kaplan, Robert E. Tarjan, Uri Zwick documento describe pero no analiza completamente variante puramente funcional. Se puede encontrar en:
Cuestiones relacionadas
- 1. Montones eficientes en idiomas puramente funcionales
- 2. ¿Existen esquemas o Lisps puramente funcionales?
- 3. ¿Hay enlaces de lenguaje puramente funcionales disponibles para Selenium2/WebDriver?
- 4. Estructuras de datos puramente funcionales con copy-on-write?
- 5. Árboles rojos-negros persistentes (puramente funcionales) en el rendimiento del disco
- 6. Programación multiprocesador: pilas sin bloqueo
- 7. Pilas de conmutación en C++
- 8. Asignación de pilas y montones
- 9. ¿Cómo usar las redes neuronales para resolver soluciones "blandas"?
- 10. Pruebas funcionales Authlogic?
- 11. BDD y pruebas funcionales
- 12. Control padre horizontal de relleno de pilas
- 13. ¿El iOS SDK proporciona colas y pilas?
- 14. Pilas NFC en el sistema operativo Android
- 15. Pilas de interpretación en Minivolcados de Windows
- 16. ¿Son las pilas de Bitnami eficientes?
- 17. P/Invoque una biblioteca puramente C++?
- 18. Cargando FMOD puramente de código nativo
- 19. ¿Pruebas unitarias o pruebas funcionales?
- 20. Diagramación en los lenguajes funcionales
- 21. Índices funcionales de Rails Postgres
- 22. claves candidatas de dependencias funcionales
- 23. resolver ecuaciones funcionales mediante programación
- 24. Escribiendo especificaciones funcionales para juegos
- 25. Especificaciones funcionales vs. Requisitos Documento
- 26. Scala Literales funcionales con Implicits
- 27. ¿Qué son las partes funcionales y no funcionales de una aplicación?
- 28. ¿Incluye un volcado del heap Java pilas de hilos
- 29. ¿Por qué usar dos pilas para hacer una cola?
- 30. Experiencias con pilas de TCP/IP (gratuitas) integradas
llegué a través de un poco de ella la noche anterior; No he verificado las complejidades de tiempo, pero parecen incorrectas log (1/e) donde e es 0
nlucaroni
¡Genial! El registro solo es negativo para argumentos menores que 1, pero 1/ε no es porque 0 <ε <1 por lo tanto 1 <ε⁻¹ <∞. –
Oh, por supuesto. Sí, tiene usted razón. Estaba claramente (o no supongo), pensando en log (ε). Entonces, cuando dice que todas las operaciones se amortizan cuestan 0, ¿está hablando de un factor constante? – nlucaroni