7

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

1 回答 1

14

按照推测对相关结果的影响顺序：

  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))))
于 2013-08-05T07:40:54.597 回答