尾递归函数不应该更快吗？

Question

我有以下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并意识到如果使用recur关键字明确告知Clojure只能提供尾递归.所以我重写了代码来做到这一点(用recur代替因子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使用技巧来实现它有关？

谢谢.

Answer 1

使用recur可以加快速度,但在递归调用时只需要大约3纳秒(真的).当事情变得那么小时,它们就会隐藏在其余测试的噪音中.我写了四个测试(下面的链接),它们能够说明性能上的差异.

我还建议在基准测试时使用类似标准的东西.(Stack Overflow不会让我发布超过1个链接,因为我没有名声可言,所以你必须谷歌它,也许"clojure标准")

出于格式化原因,我将测试和结果放在这个要点中.

简而言之,相对比较,如果递归测试为1,则循环测试约为0.45,TCO测试约为0.87,递归和TCO测试之间的绝对差值约为3ns.

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