5

我有以下 Clojure 代码来计算具有特定“可分解”属性的数字。（代码的确切作用是次要的）。

(defn factor-9
  ([]
    (let [digits (take 9 (iterate #(inc %) 1))
          nums (map (fn [x] ,(Integer. (apply str x))) (permutations digits))]
      (some (fn [x] (and (factor-9 x) x)) nums)))
  ([n]
      (or
        (= 1 (count (str n)))
        (and (divisible-by-length n) (factor-9 (quot n 10))))))

现在，我进入 TCO 并意识到 Clojure 只有在使用recur关键字明确告知时才能提供尾递归。所以我重写了代码来做到这一点（用 recur 替换 factor-9 是唯一的区别）：

(defn factor-9
  ([]
    (let [digits (take 9 (iterate #(inc %) 1))
          nums (map (fn [x] ,(Integer. (apply str x))) (permutations digits))]
      (some (fn [x] (and (factor-9 x) x)) nums)))
  ([n]
      (or
        (= 1 (count (str n)))
        (and (divisible-by-length n) (recur (quot n 10))))))

据我所知，TCO 有双重好处。第一个是它没有像非尾递归调用那样大量使用堆栈，因此不会在更大的递归上破坏它。第二个，我认为因此它更快，因为它可以转换为循环。

现在，我做了一个非常粗略的基准测试，但没有看到这两种实现之间有任何区别。我的第二个假设是错误的，还是这与在 JVM（没有自动 TCO）上运行并recur使用技巧来实现它有关？

谢谢你。

4

4 回答 4

6

recur 的使用确实加快了速度，但在递归调用上只提高了大约 3 纳秒（实际上）。当事情变得那么小时，它们可能会隐藏在其余测试的噪音中。我写了四个测试（下面的链接）能够说明性能的差异。

我还建议在进行基准测试时使用诸如标准之类的东西。（堆栈溢出不会让我发布超过 1 个链接，因为我没有名声可言，所以你必须用谷歌搜索它，也许是“clojure criterium”）

出于格式原因，我将测试和结果放在了这个gist中。

简单来说，相对比较，如果递归测试为1，则循环测试约为0.45，TCO测试约为0.87，递归和TCO测试的绝对差值在3ns左右。

当然，所有关于基准测试的警告都适用。

于 2011-01-09T22:51:33.570 回答
2

在优化任何代码时，最好从潜在或实际瓶颈开始并首先对其进行优化。

在我看来，这段特定的代码占用了你大部分的 CPU 时间：

 (map (fn [x] ,(Integer. (apply str x))) (permutations digits))

这与 TCO 无关——它以相同的方式执行。因此，这个特定示例中的尾调用将允许您不使用所有堆栈，但为了获得更好的性能，请尝试优化它。

于 2011-01-09T13:17:25.777 回答
1

只是一个外邦人提醒，clojure 没有 TCO

于 2011-01-09T19:54:54.730 回答
-1

在评估factor-9 (quot n 10)an之后，必须先评估 an and，or然后函数才能返回。因此它不是尾递归的。

于 2011-01-09T13:17:09.110 回答