7

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 question 中解释的那样“保持头脑清醒” 。

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

更新

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

我运行 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文件夹重新安装了所有依赖项。

我的项目.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 上。

4

5 回答 5

3

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

所以我想说，不要再担心这个集合的内存使用情况，而是研究一种算法，它不涉及遍历元素多于宇宙中原子数的序列。

于 2013-04-29T21:42:26.710 回答
3

问题是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!
于 2013-04-29T01:44:55.117 回答
2

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

dAni 的答案，他重新实现的地方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它的实现方式与 in完全相同clojure.core，但它完全是惰性的。为了示例，上面的map实现稍微简化了一点，因为它只支持单个参数，但即使使用整个可变参数签名来实现它也会起作用：完全懒惰。所以我们证明了这里的问题既不是 withapply也不是 with 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实现和我们之前的“简化”版本完全一样，除了表达式的true分支。if (chunked-seq? s)本质clojure.core/map上具有处理分块序列的输入序列的特殊情况。

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

真正的问题是它range返回一个分块的序列，并由subsets. David James推荐的修复补丁subsets来取消内部创建的序列range。

于 2013-07-20T10:47:15.943 回答
1

此问题已在项目的票证跟踪器上提出：Clojure JIRA: OutOfMemoryError with combinatorics/subsets。在那里，您可以找到 Andy Fingerhut 的补丁。它对我有用。请注意，该补丁不同于另一个答案建议的 mapcat 变体。

于 2013-06-24T12:11:13.387 回答
0

在没有命令行参数的情况下，JVM 的启动堆大小参数由各种人体工程学决定

默认值（JDK 6）是

   
   初始堆大小内存 / 64
   最大堆大小 MIN(内存 / 4, 1GB)

-Xmx但是您可以使用和-Xmsargs强制使用绝对值您可以在此处找到更多详细信息

于 2013-04-29T15:15:08.147 回答