math.combinatorics 中的 Clojure 惰性序列会导致 OutOfMemory (OOM) 错误

Question

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

但是，如果我尝试运行 subsets有大量数据，

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

我收到内存不足错误。

正在运行

(last (range))

会消耗 CPU，但不会返回错误。

Clojure 似乎并不像解释的那样“保持头脑清醒”in this Stack Overflow question .

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

更新

正如评论所暗示的那样，它似乎可以在某些人的计算机上运行。所以我将发布我的系统配置

我运行 Mac (10.8.3) 并安装了 Clojure (1.5.1) 与 Homebrew .

我的 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 来实现并保存一些元素被连接起来。请参阅a very nice explanation here 。在子集中使用该链接的惰性 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!