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)ヒープなどを使用していることを理解してはいけないと思います。