为什么这个循环函数与map相比如此之慢？

Question

我查看了地图源代码,它基本上不断创建延迟序列.我认为迭代一个集合并添加到一个瞬态向量会更快,但显然它不是.关于clojures性能行为,我不了解什么？

;=> (time (do-with / (range 1 1000) (range 1 1000)))
;"Elapsed time: 23.1808 msecs"
;
; vs
;=> (time (doall (map #(/ %1 %2) (range 1 1000) (range 1 1000))))
;"Elapsed time: 2.604174 msecs"
(defn do-with
  [fn coll1 coll2]
  (let [end (count coll1)]
    (loop [i   0
           res (transient [])]
        (if
          (= i end)
            (persistent! res)
            (let [x (nth coll1 i)
                  y (nth coll2 i)
                  r (fn x y)]
              (recur (inc i) (conj! res r))) 
                  ))))

Answer 1

为了推测相对结果的影响:

1. 您的do-with函数用于nth访问输入集合中的各个项目.nth在范围内以线性时间运行,制作do-with二次方.毋庸置疑,这将扼杀大型集合的性能.

2. range生成分块序列并map极其有效地处理这些序列.(基本上它通过在每个输入块的内部数组上依次运行紧密循环,将结果放在输出块的内部数组中,产生最多32个元素的块 - 这里实际上恰好是32个 -

3. 基准测试time不会给你稳定的状态表现.(这就是为什么人们应该真正使用适当的基准测试库;在Clojure的情况下,Criterium是标准解决方案.)

顺便说一下,(map #(/ %1 %2) xs ys)可以简单地写成(map / xs ys).

更新:

我使用Criterium 对map版本,原始版本do-with和新do-with版本进行了基准测试,(range 1 1000)在每种情况下使用两个输入(如问题文本中所示),获得以下平均执行时间:

;;; (range 1 1000)
new do-with           170.383334 µs
(doall (map ...))     230.756753 µs
original do-with       15.624444 ms

另外,我使用存储在Var中的向量作为输入而不是范围(即,(def r (vec (range 1 1000)))在开始时使用r并在每个基准测试中用作两个集合参数)重复基准测试.不出所料,原始do-with的第一个 - nth在向量上非常快(加上使用nth向量避免了seq遍历中涉及的所有中间分配).

;;; (vec (range 1 1000))
original do-with       73.975419 µs
new do-with            87.399952 µs
(doall (map ...))     153.493128 µs

这是do-with具有线性时间复杂度的新功能:

(defn do-with [f xs ys]
  (loop [xs  (seq xs)
         ys  (seq ys)
         ret (transient [])]
    (if (and xs ys)
      (recur (next xs)
             (next ys)
             (conj! ret (f (first xs) (first ys))))
      (persistent! ret))))