haskell - ¿Ana-/Catamorphisms es más lento?

kdtree recursion-schemes

Question

Después de escribir este artículo , decidí poner mi dinero donde está mi boca y comencé a convertir un proyecto mío previo para usar recursion-schemes .

La estructura de datos en cuestión es un kdtree flojo . Por favor, eche un vistazo a las implementaciones con recursión explícita e implícita .

Esto es principalmente una conversión directa en la línea de:

data KDTree v a = Node a (Node v a) (Node v a) | Leaf v a

a

data KDTreeF v a f = NodeF a f f | Leaf v a

Ahora, después de comparar todo el shebang, descubro que la versión de KDTreeF es aproximadamente dos veces más lenta que la versión normal ( encuentre la KDTreeF completa aquí ).

¿Es solo el envoltorio de Fix adicional que me ralentiza aquí? ¿Y hay algo que pueda hacer contra esto?

Advertencias:

• Por el momento esto está especializado para (V3 doble).
• Esto es cata- después de la aplicación de anamorfismo. Hylomorphism no es adecuado para kdtrees.
• Uso cata (fmap foo algebra) varias veces. ¿Es esta una buena práctica?
• Yo uso el paquete de recursion-schemes Edwards.

Editar 1:

¿Esto está relacionado? https://ghc.haskell.org/trac/ghc/wiki/NewtypeWrappers Is newtype Fix f = Fix (f (Fix f)) no es "libre"?

Editar 2:

Acabo de hacer otro grupo de puntos de referencia. Esta vez probé la construcción de árboles y la deconstrucción. Punto de referencia aquí: https://dl.dropboxusercontent.com/u/2359191/2014-05-15-kdtree-bench-03.html

Mientras que la salida del núcleo indica que las estructuras de datos intermedios no se eliminan por completo y no es sorprendente que las búsquedas lineales dominen ahora, las KDTreeF ahora son ligeramente más rápidas que las KDTree s. No importa mucho sin embargo.

Answer 1

Acabo de implementar la variante de Thing + ThingF + Base instance del árbol. Y adivina qué ... este es increíblemente rápido.

Tenía la impresión de que esta sería la más lenta de todas las variantes. Debería haber leído mi propia publicación ... la línea donde escribo:

no hay rastro de la estructura TreeF que se puede encontrar

Deje que los números hablen por sí mismos, kdtreeu es la nueva variante. Los resultados no siempre son tan claros como en estos casos, pero en la mayoría de los casos son al menos tan rápidos como la recursión explícita ( kdtree en el benchmark).

Answer 2

No estaba usando esquemas de recursión, sino más bien mi propia cata "hecha a mano", Fix / unFix para hacer la generación de (listas de) y la evaluación de programas en un lenguaje pequeño con la esperanza de encontrar uno que coincidiera con una lista de pares (entrada, salida).

En mi experiencia, cata optimizó mejor que la recursión directa y dio un impulso de velocidad. También IME, e impidió errores de desbordamiento de pila que mi ingenuo generador estaba causando, pero eso se ha centrado en la generación de la lista final.

Entonces, mi respuesta sería que no, no siempre son más lentos, pero no veo ningún problema obvio; entonces ellos pueden simplemente ser más lentos en su caso. También es posible que los esquemas de recursión en sí no estén optimizados para la velocidad.