懒惰序列还是重复数学幂函数？

Question

作为练习,我实现了数学幂函数.一旦使用recur:

(defn power [a n]
  (let [multiply (fn [x factor i]
                   (if (zero? i)
                     x
                     (recur (* x factor) factor (dec i))))]
  (multiply a a (dec n))))

user=> (time (dotimes [_ 10000] (power 2 512)))
"Elapsed time: 1839.406746 msecs"

有一次使用lazy-seq:

(defn power [a n]
  (letfn [(multiply [a factor]
            (lazy-seq
              (cons a (multiply (* a factor) factor))))]
  (nth (multiply a a) (dec n))))

user=> (time (dotimes [_ 10000] (power 2 512)))
"Elapsed time: 2162.297827 msecs"

您认为哪种实施方式更优越？我真的不知道..(我会使用复发,因为它更容易理解.)

我读到lazy-seq很快,因为它使用内部缓存.但我在样本中看不到缓存的任何机会.我忽略了什么吗？

更新
我发布了样本的时间.似乎复发在这里稍快一些.

定期递归也不会太糟糕:

(defn power [a n]
   (if (== n 1)
      a
      (* a (power a (dec n)))))

user=> (time (dotimes [_ 10000] (power 2 512)))
"Elapsed time: 1877.34521 msecs"

Answer 1

首先,通常的建议是首先选择正确的算法,稍后担心实现细节(如果您的代码实际上对性能敏感或者可能在上下文中使用).

然后有审美考虑因素.在recur似乎清洁剂给我,只是因为它的去了解这个问题的非常自然的方式.当他们以某种方式输入语义图片时使用序列是有意义的,否则,使代码更容易编写/理解/提高性能.这里没有类似的情况.

最后,我肯定希望recur整体更快,只是因为它避免了不必要的分配和GC.最初的时间支持这一点.确实没有机会从这里获得任何类型的缓存,因为无论何时power调用都会从头开始生成序列,并且在返回后永远不会保留它.