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

Question

我查看了 Maps 的源代码，它基本上一直在创建惰性序列。我原本认为迭代集合并添加到瞬态向量会更快，但显然不是这样。我对 Clojure 的性能行为有什么误解？

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

- Core

Answer 1

按照预测的相对结果排序：

1. 你的 do-with 函数使用 nth 来访问输入集合中的单个项。 nth 在范围上的操作是线性的，使得 do-with 是二次的。不用说，在大型集合上这将会严重影响性能。

2. range 生成分块序列，map 对其进行高效处理。（基本上它通过循环遍历每个输入块的内部数组，以及对应地将结果放置在输出块的内部数组中，来产生最多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与向量避免了涉及序列遍历的所有中间分配)。

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

- Michał Marczyk

---

感谢您详细而全面的回答。看起来我需要更加关注对什么类型的数据结构执行何种类型的操作。 - Core