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) を実行し、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 を使用していました。

4

5 に答える 5

3

You want to compute the power set of a set with 1000 elements? You know that's going to have 2^1000 elements, right? That is so large I can't even find a good way to describe how enormous it is. If you're trying to work with such a set, and you can do so lazily, your problem won't be memory: it will be computation time. Let's say you have a supercomputer with infinite memory, capable of processing a trillion items per nanosecond: that's 10^21 items processed per second, or about 10^29 items per year. Even this supercomputer will take much, much longer than the lifetime of the universe to work through the items of (subsets (range 1000)).

したがって、このコレクションのメモリ使用量について心配するのはやめて、宇宙に存在する原子よりも多くの要素を含むシーケンスをたどらないアルゴリズムに取り組みましょう。

于 2013-04-29T21:42:26.710 に答える
3

問題は、 をsubsets使用しmapcat、mapcat連結する要素の一部を認識して保持する apply を使用するため、十分に怠惰ではないことです。ここで非常に優れた説明を参照してください。そのリンクの lazier 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

問題はapply、でも、でもconcat、でもありません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実装されていますが、完全に遅延して動作します。上記の実装は、単一のパラメーターのみをサポートするため、例のために少し単純化されていますが、可変引数シグネチャ全体で実装しても同じように機能します: full laziness . したがって、ここでの問題は を使用した場合でも、 を使用した場合でもないことを示しました。また、実際の問題は、関数が でどのように実装されているかに関連している必要があることも示しました。それを見てみましょう：clojure.coremapapplyconcatmapclojure.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除いて、以前の「簡略化された」バージョンとまったく同じであることがわかります。基本的に、チャンクされたシーケンスである入力シーケンスを処理するための特別なケースがあります。trueif (chunked-seq? s)clojure.core/map

チャンク シーケンスは、一度に厳密に 1 つずつ評価するのではなく、32 のチャンクで評価することにより、遅延性を妥協します。これは、 の場合のように、深くネストされたチャンク シーケンスを評価するときに痛々しいほど明白になりsubsetsます。チャンク シーケンスは Clojure 1.1 で導入され、多くのコア関数がアップグレードされ、それらを別の方法で認識して処理するようになりましたmap。それらを導入した主な目的は、特定のストリーム処理シナリオでのパフォーマンスを向上させることでしたが、間違いなく、プログラムの遅延特性を判断するのが非常に難しくなります。チャンク化されたシーケンスについては、こちらとこちらで読むことができます。こちらの質問もご覧ください。

本当の問題は、rangeがチャンク化された seq を返し、 によって内部的に使用されることsubsetsです。内部で作成されたシーケンスをアンチャンクするために、 David Jamesパッチが推奨する修正。subsetsrange

于 2013-07-20T10:47:15.943 に答える
0

コマンド ライン引数がない場合、JVM の起動ヒープ サイズ パラメータはさまざまな人間工学によって決定されます。

デフォルト (JDK 6) は

   
   初期ヒープ サイズ メモリ / 64
   最大ヒープサイズ MIN(メモリ / 4, 1GB)

-Xmxただし、および引数を使用して絶対値を強制する-Xmsことができます 詳細はこちら

于 2013-04-29T15:15:08.147 に答える