math.combinatorics中的Clojure延迟序列导致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似乎没有像" Stack Overflow"问题中所解释的那样"保持头脑" .

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

更新

正如评论所暗示的,它似乎适用于某些人的计算机.所以我将发布我的系统配置

我运行Mac(10.8.3)并使用Homebrew安装Clojure(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!