对其结果迭代应用函数，而不生成seq [英] Iteratively apply function to its result without generating a seq

问题描述

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

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

 （fn-pow inc 0 3）
  

将等同于

  ））
  

使用 iterate ：

 （defn fn-pow-0 
 [fxn] 
（nth（iterate fx） n））
  

，但会创建并丢弃不必要的延迟序列。

从头开始编写函数并不难。以下是一个版本：

 （defn fn-pow-1 
 [fxn] 
 > n 0）
（recur f（fx）（dec n））
x））
  

我发现这几乎是 fn-pow-0 的两倍快，在上使用Criterium（fn-pow inc 0 10000000 ）。

我不考虑 fn-pow-1 是单一的，但 fn-pow 似乎可能是一个标准的内置函数，或者可能有一些简单的方法来定义它，顺序功能在一个聪明的安排。我也没有成功地发现。

解决方案

您正在寻找的内置大概是 dotimes 。

时间

您正在测试的是什么基准测试主要是间接级别的开销。当是非常快的函数时，（nth（iterate ...）n）仅是两倍于编译为循环的速度是令人惊讶/鼓舞。如果 f 是一个更昂贵的函数，那个开销的重要性减少。 （当然，如果您的 f 是低级别和快速，那么您应该使用低级别循环结构。）

<$ p < （Thread / sleep 1）（inc x））

这些将需要约1秒 - 差别是约2％而不是100％。

 （bench（fn-pow- 0 my-inc 0 1000））
（bench（fn-pow-1 my-inc 0 1000））
  

b $ b

空格

另一个问题是 iterate 正在创建一个不必要的序列。但是，如果你不坚持头部，只是做一个 nth ，那么你不是真正创建一个序列本身，但依次创建，使用和放弃 LazySeq 对象。换句话说，你使用一个恒定的空间量，虽然产生的垃圾与 n 成比例。但是，除非您的 f 是原始或变异其参数，否则 c $ c> n 生成自己的中间结果。

减少垃圾

fn-pow-0 和 fn-pow-1 将是

 defn fn-pow-2 [fxn]（reduce（fn [x _]（fx））x（range n）））
  

由于范围对象知道如何智能地减少自己，这不会创建额外垃圾与 n 。它也归结为一个循环。这是范围的 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 code>。

变异

如果你在时间或空间上迭代一个可能很昂贵的函数，如矩阵操作，那么你可能想要使用（以一种包含的方式）一个 f ，它改变其参数以消除垃圾开销。因为突变是副作用，你想要的副作用 n 次， dotimes 是自然的选择。 p>

为了举例，我将使用 atom 作为替代，但想象一下可变矩阵。

 （def my-x（atom 0））
 
（defn my-inc！[x ]（thread / sleep 1）（swap！x inc））
 
（defn fn-pow-3！[f！xn]（dotimes [in] b  

This is one of those "Is there a built-in/better/idiomatic/clever way to do this?" questions.

I want a function--call it fn-pow--that will apply a function f to the result of applying f to an argument, then apply it to the result of applying it to its result, etc., n times. For example,

(fn-pow inc 0 3)

would be equivalent to

(inc (inc (inc 0)))

It's easy to do this with iterate:

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

but that creates and throws away an unnecessary lazy sequence.

It's not hard to write the function from scratch. Here is one version:

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

I found this to be almost twice as fast as fn-pow-0, using Criterium on (fn-pow inc 0 10000000).

I don't consider the definition of fn-pow-1 to be unidiomatic, but fn-pow seems like something that might be a standard built-in function, or there may be some simple way to define it with a couple of higher-order functions in a clever arrangement. I haven't succeeded in discovering either. Am I missing something?

解决方案

The built-in you are looking for is probably dotimes. I'll tell you why in a round-about fashion.

Time

What you are testing in your benchmark is mainly the overhead of a level of indirection. That (nth (iterate ...) n) is only twice as slow as what compiles to a loop when the body is a very fast function is rather surprising/encouraging. If f is a more costly function, the importance of that overhead diminishes. (Of course if your f is low-level and fast, then you should use a low-level loop construct.)

Say your function takes ~ 1 ms instead

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

Then both of these will take about 1 second -- the difference is around 2% rather than 100%.

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

Space

The other concern is that iterate is creating an unnecessary sequence. But, if you are not holding onto the head, just doing an nth, then you aren't really creating a sequence per se but sequentially creating, using, and discarding LazySeq objects. In other words, you are using a constant amount of space, though generating garbage in proportion to n. However, unless your f is primitive or mutating its argument, then it is already producing garbage in proportion to n in producing its own intermediate results.

Reducing Garbage

An interesting compromise between fn-pow-0 and fn-pow-1 would be

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

Since range objects know how to intelligently reduce themselves, this does not create additional garbage in proportion to n. It boils down to a loop as well. This is the reduce method of range:

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;
}

This was actually the fastest of the three (before adding primitive type-hints on n in the recur version, that is) with the slowed down my-inc.

Mutation

If you are iterating a function potentially expensive in time or space, such as matrix operations, then you may very well be wanting to use (in a contained manner) an f that mutates its argument to eliminate the garbage overhead. Since mutation is a side effect, and you want that side effect n times, dotimes is the natural choice.

For the sake of example, I'll use an atom as a stand-in, but imagine bashing on a mutable matrix instead.

(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)))

这篇关于对其结果迭代应用函数，而不生成seq的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！