math.combinatorics中的闭包懒惰序列会导致OutOfMemory (OOM)错误

Question

math.combinatorics的文档声明所有函数都返回惰性序列。

但是，如果我尝试使用大量数据运行子集，

(last (combinatorics/subsets (range 20)))
;OutOfMemoryError Java heap space  clojure.lang.RT.cons (RT.java:559)

我得到了一个OutOfMemory错误。

正在运行

(last (range))

烧毁CPU，但不返回错误。

Clojure似乎不像解释的在这个堆栈溢出问题中那样“按住头”。

为什么会发生这种情况，以及我如何在子集中使用更大的范围？

更新

正如评论所暗示的，它似乎适用于某些人的电脑。所以我会发布我的系统配置

我运行Mac (10.8.3)，用自制软件安装克洛尔 (1.5.1)。

我的Java版本是：

% java -version
java version "1.6.0_45"
Java(TM) SE Runtime Environment (build 1.6.0_45-b06-451-11M4406)
Java HotSpot(TM) 64-Bit Server VM (build 20.45-b01-451, mixed mode)

我没有更改任何默认设置。我还通过删除~/.m2文件夹重新安装了所有依赖项。

我的projects.clj。

我用的命令是

% lein repl
nREPL server started on port 61774
REPL-y 0.1.10
Clojure 1.5.1
=> (require 'clojure.math.combinatorics)
nil
=> (last (clojure.math.combinatorics/subsets (range 20)))
OutOfMemoryError Java heap space  clojure.lang.RT.cons (RT.java:570)
or
OutOfMemoryError Java heap space  clojure.math.combinatorics/index-combinations/fn--1148/step--1164 (combinatorics.clj:64)

我在一位同事的笔记本上测试了这个问题，他也有同样的问题，但他也是在Mac电脑上。

Answer 1

问题是subsets使用mapcat，而mapcat不够懒惰，因为它使用apply来实现和保存一些要连接的元素。见很好的解释。在子集中使用更延迟的mapcat版本的链接应该可以解决以下问题：

(defn my-mapcat
   [f coll]
   (lazy-seq
     (if (not-empty coll)
      (concat
      (f (first coll))
     (my-mapcat f (rest coll))))))

(defn subsets
  "All the subsets of items"
  [items]
  (my-mapcat (fn [n] (clojure.math.combinatorics/combinations items n))
  (range (inc (count items)))))

 (last (subsets (range 50))) ;; this will take hours to compute, good luck with it!

Answer 2

你想要计算1000个元素集的幂集吗？你知道那会有2^1000元素，对吧？它太大了，我甚至找不到一个很好的方法来描述它有多大。如果您尝试使用这样的集合，并且可以懒洋洋地这样做，那么您的问题将不是内存:它将是计算时间。假设你有一台拥有无限内存的超级计算机，它能够每毫秒处理1万亿个项目:即每秒处理10^21个项目，或者每年处理10^29个项目。即使是这台超级计算机，也需要比宇宙的生命周期长得多的时间来处理(subsets (range 1000))的项目。

所以我要说的是，不要担心这个集合的内存使用情况，而要研究一种算法，它不需要遍历包含比宇宙中原子更多的元素的序列。

Answer 3

问题既不是apply，也不是concat，也不是mapcat。

丹妮的回答是他重新实现mapcat的地方，他无意中解决了这个问题，但是背后的推理是不正确的。此外，他的回答指向了一篇文章，其中作者说“我相信问题在于应用”。，这显然是错误的，我将在下面解释。最后，手头的问题与另一个无关，因为非懒惰的计算确实是由apply引起的。

如果仔细观察，dAni和那篇文章的作者都实现了mapcat，而不使用map函数。在下一个示例中，我将说明这个问题与map函数的实现方式有关。

要演示该问题与apply或concat都无关，请参阅下面的mapcat实现。它同时使用concat和apply，但仍然实现了完全的懒惰：

(defn map
  ([f coll]
     (lazy-seq
      (when-let [s (seq coll)]
        (cons (f (first s)) (map f (rest s)))))))

(defn mapcat [f & colls]
  (apply concat (apply map f colls)))

(defn range-announce! [x]
  (do (println "Returning sequence of" x)
      (range x)))

;; new fully lazy implementation prints only 5 lines
(nth (mapcat range-announce! (range)) 5)

;; clojure.core version still prints 32 lines
(nth (clojure.core/mapcat range-announce! (range)) 5)

以上代码中的完全延迟是通过重新实现map函数来实现的。事实上，mapcat和clojure.core一样是实现完全一样的，但是它完全是懒惰的。为了示例起见，上面的map实现稍微简化了一些，因为它只支持一个参数，但是即使用整个可变签名实现它，也是一样的：完全惰性。因此，我们证明了这里的问题既不是apply，也不是concat。此外，我们还表明，真正的问题必须与map函数如何在clojure.core中实现有关。让我们看一看：

(defn map
  ([f coll]
   (lazy-seq
    (when-let [s (seq coll)]
      (if (chunked-seq? s)
        (let [c (chunk-first s)
              size (int (count c))
              b (chunk-buffer size)]
          (dotimes [i size]
              (chunk-append b (f (.nth c i))))
          (chunk-cons (chunk b) (map f (chunk-rest s))))
        (cons (f (first s)) (map f (rest s))))))))

可以看出，clojure.core实现与我们之前的“简化”版本完全相同，但if (chunked-seq? s)表达式的true分支除外。本质上，clojure.core/map有一个特殊的情况来处理输入序列，这些输入序列是块序列。

分块的序列通过对32块而不是严格地一次进行评估来减少懒惰。在评估深度嵌套的分块序列时，这一点非常明显，比如subsets。闭包1.1中引入了块序列，并对许多核心功能进行了升级，以不同的方式识别和处理它们，包括map。引入它们的主要目的是提高在某些流处理场景中的性能，但可以说，它们使得对程序的惰性特性进行推理变得非常困难。您可以阅读分块序列这里和这里。还可以查看这个问题，这里。

真正的问题是，range返回一个分块的seq，并在内部由subsets使用。大卫·詹姆斯修补程序subsets推荐的修补程序可以在内部取消range创建的序列块。