35

写完这篇文章后，我决定把钱放在嘴边，并开始转换我以前的项目来使用recursion-schemes.

有问题的数据结构是惰性 kdtree。请查看具有显式和隐式递归的实现。

这主要是一个简单的转换，大致如下：

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

至

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

现在，在对整个 shebang 进行基准测试后，我发现该版本比普通版本慢了KDTreeF大约两倍（在此处找到整个运行）。

只是额外的Fix包装让我在这里放慢了速度吗？有什么我可以做的吗？

注意事项：

  • 目前这是专门用于（V3 Double）的。
  • 这是 cata-after 变形应用。Hylomorphism 不适用于 kdtree。
  • 我用cata (fmap foo algebra)了好几次。这是好习惯吗？
  • 我使用 Edwardsrecursion-schemes包。

编辑1：

这有关系吗？https://ghc.haskell.org/trac/ghc/wiki/NewtypeWrappers 不是newtype Fix f = Fix (f (Fix f))“免费”的吗？

编辑2：

刚刚做了另一组基准测试。这次我测试了树的构造和解构。这里的基准测试：https ://dl.dropboxusercontent.com/u/2359191/2014-05-15-kdtree-bench-03.html

虽然核心输出表明中间数据结构没有被完全删除，并且现在线性搜索占主导地位并不奇怪，但现在KDTreeFs 比KDTrees 略快。不过也没关系。

4

2 回答 2

17

我刚刚实现Thing + ThingF + Base instance了树的变体。猜猜看……这个速度非常快。

我的印象是，这将是所有变体中最慢的。我真的应该阅读我自己的帖子......我写的那一行：

没有找到 TreeF 结构的痕迹

让数字自己说话，kdtreeu是新的变种。结果并不总是像这些情况那样清晰，但在大多数情况下，它们至少与显式递归一样快（kdtree在基准测试中）。

基准测试结果

于 2014-05-17T08:43:14.237 回答
1

我没有使用递归方案，而是我自己的“手卷” cata、ana、Fix/unFix 以一种小语言生成（列表）和评估程序，希望找到与列表匹配的程序（输入，输出）对。

以我的经验，cata 优化比直接递归更好，并提高了速度。IME, ana 也防止了我的幼稚生成器导致的堆栈溢出错误，但该错误以生成最终列表为中心。

所以，我的回答是不，它们并不总是较慢，但我没有看到任何明显的问题；所以在你的情况下它们可能会更慢。递归方案本身也可能没有针对速度进行优化。

于 2014-05-16T19:54:11.410 回答