7

Clojureについて質問があります。ProjectEulerを使用して言語を学習しようとしていますが、内部で何が起こっているのかわかりません。次のコードは、までのすべての素数のリストを返すように設計されていますlim。limまでのすべての数値のリストを作成し、最初の数値を新しいリストに移動しながら1つずつフィルターで除外するため、ヒープスペースではO（n）である必要があると思います。（私は実際に毎回新しいリストを作成していることを知っていますが、それらがより多くのメモリを必要とするとは思いませんでしたか？）とにかく私はこれを実行しています

(defn getAllPrimes [lim] 
  (defn getPrimes [primes numlist]
    (if (not-empty numlist) ;base case;
    (recur (cons (first numlist) primes) ;put the prime on to the prime list 
           (filter
        (fn [x] (not (div? x (first numlist)))) ;remove the prime and all its multiples from the numlist
        (rest numlist)))
      primes)); return the primes
  (getPrimes () (range 2 lim))) ;call the recursive function with and empty prime list to be filled up and a full numlist to be emptied

そして、電話をかけると、ヒープスペースが不足し続けます

(apply + (getAllPrimes 2000000))

、しかし私は上のスペースを使い果たしていません

(apply + (filter even? (range 2000000)))

したがって、リストがrecurの呼び出しでガベージコレクションされ、実際にO（n * n）ヒープなどを使用していることを理解してはいけないと思います。

4

1 に答える 1

6

問題は、再帰のたびに、最後のシーケンスを参照する新しい遅延シーケンスを作成しているため、数回の反復の後、seq のヘッドを保持する seq のヘッドを保持する seq を保持していることだと思いますseq の先頭を保持します。... すべての中間 seq がヒープをいっぱいにしています。

素数ふるいを書くことは価値のある演習ですが、答えを知りたい場合は、Clojure の標準ライブラリー clojure.contrib.lazy-seqs/primes に素数のシーケンスが含まれています。この特定のオイラー問題の標準的な解決策は、ワンライナーです。

スタイル ポイントとして、内部定義はお勧めできません。実際の効果は、defn が最上位にある場合と同じですが、私が間違っていなければ、getAllPrimes が呼び出されるたびに var が再割り当てされ、実行時に vars を再定義することは非常に推奨されません。コードは var を定義しているだけなので、getPrimes は getAllPrimes と同じように表示されます。この場合、 getPrimes は、匿名または名前付きの内部関数を持たないループ/再帰として簡単に書き直すことができます。これは lazy-seq のチェーンの問題には役立ちませんが、コードをもう少し標準的なものにします。

(defn getAllPrimes [lim]
  (loop [primes ()
         numlist (range 2 lim)]
    (if (not-empty numlist)
      (recur (cons (first numlist) primes)
             (filter (fn [x] (not (div? x (first numlist))))
                     (rest numlist)))
      primes)))

また、キャメルケースの使用も避けます。この関数の Clojure 標準名は get-all-primes です。

ただし、実際の問題に戻ると、コードを機能させるためにできる最小限の作業は、反復ごとに各 seq を強制することです。つまり、フィルター呼び出しを doall でラップすることです。私はこれを試しましたが、まだゆっくりと実行されていますが、少なくともヒープを使い果たすことなく最後まで実行されます:

(defn get-all-primes [lim]
  (loop [primes ()
         numlist (range 2 lim)]
    (if (not-empty numlist)
      (recur (cons (first numlist) primes)
             (doall (filter #(not (div? % (first numlist)))
                            (rest numlist))))
      primes)))
于 2010-08-11T00:36:27.857 に答える