project euler 7

pe_7.clj

;; 去年最初に解いたとき答え
;; 
;; "Elapsed time: 106406.52058 msecs"
;; 今やっても時間が1分40秒もかかってしまうので、だめー。

;; 考えかた
;; ある数Nが素数であるかどうかは、√N以下の素数に割りきれるものがあるかどうかで判定します。
;; そのためには、そこまでに発見した素数を保持する必要があります。
;; あとは、2以上の数について、素数であるかどうかでフィルターします。

(defn is-prime-sub? [target prm-list]
  (zero? (count (filter #(zero? (rem target %))
                        (take-while #(<= % (Math/sqrt target)) prm-list)))))

(defn find-prime [n]
  (loop [prime-list '(2 3 5)
         target 6]
    (if (>= (count prime-list) n)
      prime-list
      (if (is-prime-sub? target prime-list)
        (recur (concat prime-list (list target)) (inc target))
        (recur prime-list (inc target))))))

(drop 10000 (find-prime 10001))

pe_7_2.clj

;; 基本を変えずに、ちょっと直した。

;; "Elapsed time: 3681.558842 msecs"
;; この程度の修正で劇的に速くなりますね。

(defn is-prime-sub? [target prm-list]
  (zero? (count (filter #(zero? (rem target %))
                        (take-while #(<= % (Math/sqrt target)) prm-list)))))

;; 修正点
;; -ループの引数に、リストの個数を持たせて、終了判定のcount関数の呼び出しをなくした。
;; -持ち回っている素数リストをベクタにして、concatの代りにconjを使うようにした。
;; -探索対象を奇数のみにした ((+ target 2)のところ)
;; -初期値を無くした。 (気持だけの問題)
(defn find-prime [n]
  (loop [prime-list [2]
         target 3
         count 0]
    (if (>= count n)
      prime-list
      (if (is-prime-sub? target prime-list)
        (recur (conj prime-list target) (+ target 2) (inc count))
        (recur prime-list (inc target) count)))))

;; last にしてみたけど、たいして変らない。
(last (find-prime 10001))

pe_7_3.clj

;; 素数列を吐く関数をベースにして解く方法を考えてみた。

;; こんな風に解きたい 
;;    (first (drop 10000 (prime-list)))) 
;;でも、素数判定に素数列を使うというコンセプトがなので、素数判定とは分離したほうがよさそう。
;; ということで、こんな風になりました。
;;
;; "Elapsed time: 2095.031585 msecs"
;;  想像してたのより速かった。 2番目と同じくらいかと思ってた。

;; ある数が素数であるかどうか判定する関数を作る関数。
;; ただし、小さい数から順に呼ばれることが必須。
;; Let Over Lambda ですね。
;; 12/18
;; @enamon001さんからいただいたコメントの部分を変更しました。
;; >> (zero? (count (filter pred coll))) の部分は (not-any? pred coll)の方が理解しやすいと思います。
;; 理解しやすいだけでなく、激早です。
;; "Elapsed time: 673.130129 msecs"
;; ループの中の効率化が速度に大きく影響する好例ですね。
;;
(defn make-is-prime? []
  (let [prm-list (atom [2])]
    (fn [target]
      (if (not-any? #(zero? (rem target %))
                    (take-while #(<= % (Math/sqrt target)) @prm-list))
        (do (swap! prm-list conj target)
            true)
        false))))

;; 素数列を作る関数。
;; 素数かどうか判定する関数を取って、それで判定した素数の列を小さいものから全部吐く。
(defn prime-list [is-prime?]
  (filter is-prime? (cons 2 (iterate #(+ % 2) 3))))

;; こっちの方がすっきりしているけど、時間が倍くらいかかる。
;;(defn prime-list [is-prime?]
;;  (filter is-prime? (iterate inc 2)))

(first (drop 10000 (prime-list (make-is-prime?))))

pe_7_4.clj

;;  clojure docにあるエラトステネスの篩の実装を使ってみたんだけど、
;;  スタックオーバーフローで落ちる。 lazy-seqなのになぜ？
;;  調べてみると、878はOKで879はだめ。

;; この実装、すごくいい。これが書けるようになりたい。
(defn sieve [s]
  (cons (first s)
        (lazy-seq (sieve (filter #(not= 0 (mod % (first s)))
                                 (rest s))))))

(first (drop 10000 (sieve (iterate inc 2))))

;; clojure docにあるエラトステネスの篩の実装を使ってみたんだけど、
;; スタックオーバーフローで落ちる。 lazy-seqなのになぜ？

私も試してみましたが，スタックオーバーフローしました．きっと，2 とか 3 とか，小さい素数で篩ったときの filter をいつまでも全部保持しているからだと思います．

なるほど。 考えてみれば、無限シーケンスに対するフィルターが遅延シーケンスになるけれども、それをさらにフィルターするので、積み上ってしまうわけですね。

すっきりした実装なので、ちゃんと動くとかっこいいんですが、なかなかうまく行かないものですね。

いろいろな解き方がしてあって参考になります.
CommonLisp 風と言って良いのでしょうか pe_7_3.clj 良いですね.
思いつかなかったです. 引き出しに入れておきます.

私担当の Problem 10 (2000000未満の素数の総和) の方でも,
「素数列を生成する」という方針のみですが, 少し詳しめに解説書いてますので, ご参考まで.

解答がたくさんあり、読んでいて楽しかったです。
適切なコメントがコードを読む助けになっていたので、僕も参考にします。

一点、(zero? (count (filter pred coll))) の部分は (not-any? pred coll) の方が理解しやすいと思います。

---

以前 4Clojure でほとんど同じ問題を解いたので、せっかくなので解答を(若干改変して)載せておきます。

• 問題: https://www.4clojure.com/problem/67
• 解答: https://github.com/emanon001/4clojure-answers/blob/master/src/four_clojure_answers/problem_067.clj

(def primes
  (map first
       (iterate (fn [[n & more]]
                  (filter #(not= 0 (rem % n)) more))
                (iterate inc 2))))

(is (= (nth primes (dec 6)) 13))

pe_7_4.clj とほとんど同じ解き方です。そして、同様にスタックオーバーフローします……。

@enamon001 さん
not_any? とか some とかバッと出てこなくて、いつも、こんな書きかたになっちゃうんですよね。 勉強します。

pe_7_4.clj のsieveかっこいいです。なんでstack overflowするのか、まだよくわかっていないので考えているのですが、後ろの方にある要素を取ろうとするときになって、最初の方のfilterから順に一気に適用されていくから、みたいなイメージをしています。
not= とかも語彙ふやしたいです。

pe_7_3.clj 副作用いいですね。私が以前clojureに挫折したのは副作用の扱いだったのですが、このくらいの規模の例から慣らしていきたいです。

@enamon001 さんにいただいたコメントのとおり、pe_7_3.cljを修正しました。 処理時間が1/3以下になりました。

@plasterさん
pe_7_4.cljのスタックオーバーフローについては、僕も同様の理解です。遅延シーケンスなので、適用すべき関数が全て持ち越されているのでしょう。

クロージャーの中にatomを入れるのはProject Euler解くときぐらいですね。 たいていは、namespaceにatomを閉じこめて、アクセス用の関数で出し入れします。 namespaceをクラスのように扱う感じですかね。大きくなったら、atomのところをDBに移します。
また、このところ、STMは使わずに、atomだけで状態/データ管理していく方向に進んでいるそうです。datomicも、DBの本体は1つのatomに入っているそうな。

同じく, namespace に atom とアクセス関数を置いて, オンメモリDBとして使っています.