6

为什么使用 reducers 库进行映射/归约的性能比普通的 map/reduce 差？

user=> (time (reduce + (map inc (range 100000000))))
"Elapsed time: 14412.627966 msecs"
5000000050000000

user=> (time (reduce + (r/map inc (range 100000000))))
... (C-c)

user=> (time (r/reduce + (r/map inc (range 100000000))))
....(C-c)

我有两个杀死后两个，因为它需要无限长的时间。这里有什么问题？

编辑： 似乎其他语言也有类似的问题。Scala 似乎只突破了一百万。为什么 Scala 并行集合有时会导致 OutOfMemoryError？. 虽然 clojure reducers 在 100 万时比正常速度快。

4

3 回答 3

6

为了补充@a-webb 的答案，这是一个编译器错误，需要真正修复。（有关详细信息，请参阅此帖子。）

解决此问题的另一种方法是使用保险丝：

(defn once-seq
  "Returns a sequence on which seq can be called only once."
  [coll]
  (let [a (atom coll)]
    (reify clojure.lang.Seqable
      (seq [_]
        (let [coll @a]
          (reset! a nil)
          (seq coll))))))

接着：

=> (time (r/reduce + (r/map inc (once-seq (range 100000000)))))
"Elapsed time: 3692.765 msecs"
5000000050000000
于 2014-02-26T09:44:54.350 回答
2

由于内存耗尽，性能正在停止。如果您继续等待，您很可能会遇到内存错误。创建一个 reducer 将集合的头部保存在一个闭包中。因此，巨大的惰性序列在实现时会占用内存。

这是正在发生的事情，提炼的

user=> (def n 100000000)
#'user/n

user=> (time (dorun (range n)))
"Elapsed time: 12349.034702 msecs"

现在一样，但来自一个闭包

user=> (defn foo [x] (fn [f] (f x)))
#'user/foo

user=> (time ((foo (range n)) dorun))
OutOfMemoryError GC overhead limit exceeded ... (sometime later)

相比于

(time (do (doall (range n)) nil))
OutOfMemoryError GC overhead limit exceeded ... (sometime later)

减速器中的可疑关闭

user=> (source r/folder)
(defn folder
  "Given a foldable collection, [...]"
  {:added "1.5"}
  ([coll xf]
     (reify
      clojure.core.protocols/CollReduce
      (coll-reduce [_ f1]
                   (clojure.core.protocols/coll-reduce coll (xf f1) (f1)))
   ...

Christophe Grand有一篇关于如何以懒惰的方式编写减速器的好帖子。

于 2014-02-26T06:54:34.087 回答
1

Reducers 不能很好地处理惰性列表，而普通的 reduce 可以。

要从 reducer 中获得真正的好处，您需要一个非惰性集合，例如向量，并且您需要使用 fold 而不是 reduce。

 (def v (into [] (range 10000000)))
 (time (reduce + (map inc v)))
 ;; "Elapsed time: 896.79 msecs"
 (time (reduce + (r/map inc v)))
 ;; "Elapsed time: 671.947 msecs" 
 (time (r/fold + (r/map inc v)))
 ;; "Elapsed time: 229.45 msecs"

Reducers 与需要大量数据的 fork/join 框架一起工作。在惰性（分块）序列中，您没有这些大块，因此 fork/join 无法正常工作。

Rich Hickey 有一个关于减速器的演讲，很好地解释了这些概念：https ://vimeo.com/45561411

于 2014-02-26T06:57:36.523 回答