clojure - 为什么这个循环函数比 map 慢？

Question

我查看了基本上不断创建惰性序列的 map 源代码。我认为迭代集合并添加到 transient 向量会更快，但显然不是。我对 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

按照对相对结果的推测影响排序:

do-with 函数使用 nth 访问输入集合中的各个项目。 nth 在范围内以线性时间运行，使 do-with 成为二次方。不用说，这会降低大型集合的性能。

range 产生分块序列，map 非常有效地处理这些序列。 (本质上，它生成最多 32 个元素的块——这里实际上正好是 32 个——通过依次在每个输入块的内部数组上运行紧密循环，将结果放入输出块的内部数组中。)

使用 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))))