clojure - 迭代地将函数应用于其结果而不生成 seq

Question

这是其中之一“有内置/更好/惯用/聪明的方法来做到这一点吗？”问题。

我想要一个函数——称之为 fn-pow --这会将函数 f 应用于将 f 应用于参数的结果，然后将其应用于将其应用于其结果的结果，等等，n次。例如，

(fn-pow inc 0 3)

相当于

(inc (inc (inc 0)))

使用 iterate 可以轻松做到这一点:

(defn fn-pow-0
  [f x n]
  (nth (iterate f x) n))

但这会创建并丢弃不必要的惰性序列。

从头开始编写该函数并不难。这是一个版本:

(defn fn-pow-1
  [f x n]
  (if (> n 0) 
    (recur f (f x) (dec n))
    x))

我发现这几乎是 fn-pow-0 的两倍，在 (fn-pow inc 0 10000000) 上使用标准.

我不考虑 fn-pow-1 的定义不惯用，但是 fn-pow看起来可能是一个标准的内置函数，或者可能有一些简单的方法可以通过巧妙安排的几个高阶函数来定义它。我也没有成功发现。我错过了什么吗？

Answer 1

您正在寻找的内置函数可能是dotimes。我会以迂回的方式告诉你原因。

时间

您在基准测试中测试的主要是间接级别的开销。当主体是一个非常快的函数时，(nth (iterate ...) n)仅比编译成循环的速度慢两倍，这是相当令人惊讶/令人鼓舞的。如果 f 是一个成本更高的函数，那么该开销的重要性就会降低。 (当然，如果您的 f 是低级且快速的，那么您应该使用低级循环构造。)

假设你的函数需要大约 1 毫秒

(defn my-inc [x] (Thread/sleep 1) (inc x))

然后两者都需要大约 1 秒 - 差异约为 2%，而不是 100%。

(bench (fn-pow-0 my-inc 0 1000))
(bench (fn-pow-1 my-inc 0 1000))

空间

另一个问题是迭代正在创建不必要的序列。但是，如果您没有捕获头部，只是执行nth，那么您真正并没有创建一个序列本身，而是按顺序创建创建、使用和丢弃 LazySeq 对象。换句话说，您使用的空间量是恒定的，但产生的垃圾与n成比例。但是，除非您的 f 是原始的或者变异其参数，否则它已经按照n的比例产生垃圾产生自己的中间结果。

减少垃圾

fn-pow-0 和 fn-pow-1 之间的一个有趣的折衷方案是

(defn fn-pow-2 [f x n] (reduce (fn [x _] (f x)) x (range n)))

由于 range 对象知道如何智能地减少自身，因此这不会按 n 的比例创建额外垃圾。它也归结为一个循环。这是 range 的 reduce 方法:

public Object reduce(IFn f, Object start) {
    Object ret = f.invoke(start,n);
    for(int x = n+1;x < end;x++)
            ret = f.invoke(ret, x);
    return ret;
}

这实际上是三个中最快的(即在 recur 版本中的 n 上添加原始类型提示之前)，但 my 速度较慢-inc.

突变

如果您正在迭代一个可能在时间或空间上昂贵的函数，例如矩阵运算，那么您很可能希望(以包含的方式)使用 f 将其参数转变为消除垃圾开销。由于突变是一种副作用，并且您希望该副作用 n 次，因此 dotimes 是自然的选择。

为了举例，我将使用 atom 作为替代品，但想象一下对可变矩阵进行攻击。

(def my-x (atom 0))

(defn my-inc! [x] (Thread/sleep 1) (swap! x inc))

(defn fn-pow-3! [f! x n] (dotimes [i n] (f! x)))