Les ana- / catamorphismes sont-ils simplement plus lents?

Question

Après l'écriture de cet article j'ai décidé de mettre mon argent là où ma bouche et a commencé à convertir un précédent projet de la mine d'utilisation recursion-schemes.

La structure de données en question est un paresseux kdtree. Jetez un oeil à des mises en oeuvre avec explicite et implicite de la récursivité.

C'est surtout une simple conversion, le long des lignes de:

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

pour

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

Maintenant, après évaluation tout le toutim, je trouve que l' KDTreeF version est environ deux fois plus lent que la normale version (trouver l'ensemble de la course ici).

C'est juste de la supplémentaire Fix wrapper qui ralentit moi ici-bas? Et est-ce que je pouvais faire contre cela?

Mises en garde:

• Pour le moment ce n'est spécialisé (V3 Double).
• C'est cata - après anamorphism application. Hylomorphism n'est pas adapté pour kdtrees.
• J'utilise cata (fmap foo algebra) plusieurs fois. Est-ce une bonne pratique?
• J'utilise Edwards recursion-schemes package.

Edit 1:

Est-ce lié? https://ghc.haskell.org/trac/ghc/wiki/NewtypeWrappers Est - newtype Fix f = Fix (f (Fix f)) est pas "libre"?

Edit 2:

Juste un autre tas de repères. Cette fois, j'ai testé la construction de l'arbre et de la déconstruction. Référence ici: https://dl.dropboxusercontent.com/u/2359191/2014-05-15-kdtree-bench-03.html

Alors que le centre de sortie indique que les structures de données ne sont pas complètement supprimé et il n'est pas surprenant que le linéaire des recherches dominent maintenant, l' KDTreeFs sont maintenant légèrement plus rapide que l' KDTrees. N'a pas d'importance très bien.

Answer 1

J'ai juste mis en œuvre l' Thing + ThingF + Base instance variante de l'arbre. Et devinez quoi ... il est étonnamment rapide.

J'étais sous l'impression que celle-ci serait la plus lente de toutes les variantes. J'ai vraiment dû lire mon propre post ... la ligne où j'écris:

il n'y a aucune trace de la TreeF structure pour être trouvé

Laissez-les chiffres parlent d'eux-mêmes, kdtreeu est la nouvelle variante. Les résultats ne sont pas toujours aussi claire que pour ces cas, mais dans la plupart des cas, ils sont au moins aussi vite que la récursion explicite (kdtree dans la référence).

Answer 2

Je n'étais pas à l'aide de schémas de récursion, mais plutôt de mes propres "roulés à la main" cata, ana, Fix/libérer de faire de la génération de listes de) et l'évaluation des programmes dans une petite langue dans l'espoir de trouver un correspondant à une liste d' (entrée, sortie) paires.

Dans mon expérience, la cata, optimisé mieux que la récursivité directe et a donné un boost de vitesse. Également IME, ana empêché erreurs de dépassement de pile que mon naïf générateur était à l'origine, mais qui ont centré autour de la génération de la liste finale.

Donc, ma réponse serait que non, ils ne sont pas toujours plus lente, mais je ne vois pas de problèmes évidents, de sorte qu'ils peuvent tout simplement être plus lente dans votre cas. Il est également possible que la récursivité-régimes de lui-même est tout simplement pas optimisé pour la vitesse.