48

私はClojure でProject Eulerの問題を解決することに取り組んでいますが、すでに数回素数の生成に遭遇しています。私の問題は、時間がかかりすぎることです。Clojure-y の方法でこれを行う効率的な方法を誰かが見つけるのを手伝ってくれることを望んでいました。

私がこぶしでこれをやったとき、私は力ずくでそれをやりました。それは簡単にできました。しかし、Xeon 2.33GHz で 10001 の素数を計算するには、この方法で 2 分かかりました。アルゴリズムは次のとおりです。

(defn next-prime-slow
    "Find the next prime number, checking against our already existing list"
    ([sofar guess]
        (if (not-any? #(zero? (mod guess %)) sofar)
            guess                         ; Then we have a prime
            (recur sofar (+ guess 2)))))  ; Try again                               

(defn find-primes-slow
    "Finds prime numbers, slowly"
    ([]
        (find-primes-slow 10001 [2 3]))   ; How many we need, initial prime seeds
    ([needed sofar]
        (if (<= needed (count sofar))
            sofar                         ; Found enough, we're done
            (recur needed (concat sofar [(next-prime-slow sofar (last sofar))])))))

next-prime-slow を、いくつかの追加ルール (6n +/- 1 プロパティなど) を考慮した新しいルーチンに置き換えることで、約 70 秒まで高速化することができました。

次に純粋なClojureでエラトステネスのふるいを作ってみました。すべてのバグを取り除いたとは思いませんが、単純に遅すぎたのであきらめました (上記よりもさらに悪いと思います)。

(defn clean-sieve
    "Clean the sieve of what we know isn't prime based"
    [seeds-left sieve]
    (if (zero? (count seeds-left))
        sieve              ; Nothing left to filter the list against
        (recur
            (rest seeds-left)    ; The numbers we haven't checked against
            (filter #(> (mod % (first seeds-left)) 0) sieve)))) ; Filter out multiples

(defn self-clean-sieve  ; This seems to be REALLY slow
    "Remove the stuff in the sieve that isn't prime based on it's self"
    ([sieve]
        (self-clean-sieve (rest sieve) (take 1 sieve)))
    ([sieve clean]
        (if (zero? (count sieve))
            clean
            (let [cleaned (filter #(> (mod % (last clean)) 0) sieve)]
                (recur (rest cleaned) (into clean [(first cleaned)]))))))

(defn find-primes
    "Finds prime numbers, hopefully faster"
    ([]
        (find-primes 10001 [2]))
    ([needed seeds]
        (if (>= (count seeds) needed)
            seeds        ; We have enough
            (recur       ; Recalculate
                needed
                (into
                    seeds    ; Stuff we've already found
                    (let [start (last seeds)
                            end-range (+ start 150000)]   ; NOTE HERE
                        (reverse                                                
                            (self-clean-sieve
                            (clean-sieve seeds (range (inc start) end-range))))))))))

これは悪いです。また、数値 150000 が小さい場合、スタック オーバーフローが発生します。これは、recur を使用しているにもかかわらずです。それは私のせいかもしれません。

次に、Java ArrayList で Java メソッドを使用してふるいを試しました。それにはかなりの時間とメモリが必要でした。

私の最新の試みは、Clojure ハッシュマップを使用したふるいです。ふるいにすべての数値を挿入してから、素数ではない数値を分解します。最後に、見つかった素数であるキー リストを取得します。10000 個の素数を見つけるのに約 10 ～ 12 秒かかります。まだ完全にデバッグされているかどうかはわかりません。私は Lispy になろうとしているので、これも再帰的です (recur と loop を使用)。

したがって、この種の問題では、問題 10 (2000000 未満のすべての素数を合計する) が私を殺しています。私の最速のコードは正しい答えを思いつきましたが、それを行うのに 105 秒かかり、かなりの量のメモリが必要でした (私はそれに 512 MB を与えたので、大騒ぎする必要はありませんでした)。私の他のアルゴリズムは時間がかかりすぎて、いつも最初にそれらを止めてしまいました。

ふるいを使用して、Java または C で非常に高速に、多くのメモリを使用せずに多くの素数を計算できます。問題の原因となっている Clojure/Lisp スタイルの何かが欠けているに違いないことはわかっています。

私が本当に間違っていることはありますか？Clojure は大規模なシーケンスでちょっと遅いですか? プロジェクトの Euler に関する議論を読んでいると、人々は他の Lisp で最初の 10000 個の素数を 100 ミリ秒未満で計算しました。JVM によって速度が低下する可能性があり、Clojure が比較的新しいことはわかっていますが、100 倍の違いは期待できません。

Clojure で素数をすばやく計算する方法を教えてもらえますか?

4

16 に答える 16

29

を祝う別のアプローチを次に示しClojure's Java interopます。これは、2.4 Ghz Core 2 Duo (シングルスレッドで実行) で 374 ミリ秒かかります。Miller-RabinJava の効率的な実装にBigInteger#isProbablePrime素数チェックを処理させます。

(def certainty 5)

(defn prime? [n]
      (.isProbablePrime (BigInteger/valueOf n) certainty))

(concat [2] (take 10001 
   (filter prime? 
      (take-nth 2 
         (range 1 Integer/MAX_VALUE)))))

5のMiller-Rabin確実性は、これよりもはるかに大きな数ではおそらくあまり良くありません。96.875%その確実性は確かにそれが素数であることと等しい( 1 - .5^certainty)

于 2011-10-29T20:18:57.527 に答える
21

これは非常に古い質問だと思いますが、最近同じものを探してしまい、ここのリンクは探しているものではありませんでした (可能な限り関数型に制限され、必要なすべての素数を遅延生成します) .

素敵なF# の実装を偶然見つけたので、クレジットはすべて彼のものです。Clojure に移植しただけです。

(defn gen-primes "Generates an infinite, lazy sequence of prime numbers"
  []
  (letfn [(reinsert [table x prime]
             (update-in table [(+ prime x)] conj prime))
          (primes-step [table d]
             (if-let [factors (get table d)]
               (recur (reduce #(reinsert %1 d %2) (dissoc table d) factors)
                      (inc d))
               (lazy-seq (cons d (primes-step (assoc table (* d d) (list d))
                                              (inc d))))))]
    (primes-step {} 2)))

使い方は簡単

(take 5 (gen-primes))
于 2011-10-02T07:58:32.233 に答える
12

遅くなりましたが、Java BitSet を使用した例を紹介します。

(defn sieve [n]
  "Returns a BitSet with bits set for each prime up to n"
  (let [bs (new java.util.BitSet n)]
    (.flip bs 2 n)
    (doseq [i (range 4 n 2)] (.clear bs i))
    (doseq [p (range 3 (Math/sqrt n))]
      (if (.get bs p)
        (doseq [q (range (* p p) n (* 2 p))] (.clear bs q))))
    bs))

これを 2014 Macbook Pro (2.3GHz Core i7) で実行すると、次のようになります。

user=> (time (do (sieve 1e6) nil))
"Elapsed time: 64.936 msecs"
于 2014-03-26T17:40:27.200 に答える
11

ここで最後の例を参照してください: http://clojuredocs.org/clojure_core/clojure.core/lazy-seq

;; An example combining lazy sequences with higher order functions
;; Generate prime numbers using Eratosthenes Sieve
;; See http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
;; Note that the starting set of sieved numbers should be
;; the set of integers starting with 2 i.e., (iterate inc 2) 
(defn sieve [s]
  (cons (first s)
        (lazy-seq (sieve (filter #(not= 0 (mod % (first s)))
                                 (rest s))))))

user=> (take 20 (sieve (iterate inc 2)))
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71)
于 2013-01-10T15:21:28.250 に答える
4

これは素晴らしくシンプルな実装です：

http://clj-me.blogspot.com/2008/06/primes.html

...しかし、Clojureの1.0より前のバージョン用に書かれています。現在のバージョンの言語で動作するものについては、Clojure Contrib の lazy_seqs を参照してください。

于 2009-06-07T07:46:37.050 に答える
3 
(defn sieve
  [[p & rst]]
  ;; make sure the stack size is sufficiently large!
  (lazy-seq (cons p (sieve (remove #(= 0 (mod % p)) rst)))))

(def primes (sieve (iterate inc 2)))

スタック サイズが 10M の場合、2.1Gz の MacBook で 1001 番目のプライムを ~ 33 秒で取得します。

于 2011-02-26T17:51:35.873 に答える
2

これはSchemeの簡単なふるいです:

http://telegraphics.com.au/svn/puzzles/trunk/programming-in-scheme/primes-up-to.scm

10,000 までの素数の実行は次のとおりです。

#;1> (include "primes-up-to.scm")
; including primes-up-to.scm ...
#;2> ,t (primes-up-to 10000)
0.238s CPU time, 0.062s GC time (major), 180013 mutations, 130/4758 GCs (major/minor)
(2 3 5 7 11 13...
于 2011-01-21T16:06:04.560 に答える
2

これがClojureソリューションです。i現在検討中の数pで、これまでに見つかったすべての素数のリストです。some素数による除算の余りがゼロの場合、その数iは素数ではなく、次の数で再帰が発生します。それ以外の場合は、次の再帰で素数が追加さpれます (次の数を続行するだけでなく)。

(defn primes [i p]
  (if (some #(zero? (mod i %)) p)
    (recur (inc i) p)
    (cons i (lazy-seq (primes (inc i) (conj p i))))))
(time (do (doall (take 5001 (primes 2 []))) nil))
; Elapsed time: 2004.75587 msecs
(time (do (doall (take 10001 (primes 2 []))) nil))
; Elapsed time: 7700.675118 msecs

更新:上記のこの回答に基づいた、より洗練されたソリューションを次に示します。基本的に、2 で始まる整数のリストは遅延フィルタリングされます。iフィルタリングは、その数を割った余りがゼロでない素数がない場合にのみ、その数を受け入れることによって実行されます。素数の 2 乗が より小さいか等しい場合、すべての素数が試行されiます。primesは再帰的に使用されますが、Clojure は無限の再帰を回避することに注意してください。また、遅延シーケンスが結果をキャッシュすることにも注意してくださいprimes(そのため、パフォーマンスの結果は一見すると直感に反するものになります)。

(def primes
  (lazy-seq
    (filter (fn [i] (not-any? #(zero? (rem i %))
                              (take-while #(<= (* % %) i) primes)))
            (drop 2 (range)))))
(time (first (drop 10000 primes)))
; Elapsed time: 542.204211 msecs
(time (first (drop 20000 primes)))
; Elapsed time: 786.667644 msecs
(time (first (drop 40000 primes)))
; Elapsed time: 1780.15807 msecs
(time (first (drop 40000 primes)))
; Elapsed time: 8.415643 msecs
于 2020-11-02T14:10:29.890 に答える
1

ウィルのコメントに基づいて、ここに私の見解がありますpostponed-primes：

(defn postponed-primes-recursive
  ([]
     (concat (list 2 3 5 7)
             (lazy-seq (postponed-primes-recursive
                        {}
                        3
                        9
                        (rest (rest (postponed-primes-recursive)))
                        9))))
  ([D p q ps c]
     (letfn [(add-composites
               [D x s]
               (loop [a x]
                 (if (contains? D a)
                   (recur (+ a s))
                   (persistent! (assoc! (transient D) a s)))))]
       (loop [D D
              p p
              q q
              ps ps
              c c]
         (if (not (contains? D c))
           (if (< c q)
             (cons c (lazy-seq (postponed-primes-recursive D p q ps (+ 2 c))))
             (recur (add-composites D
                                    (+ c (* 2 p))
                                    (* 2 p))
                    (first ps)
                    (* (first ps) (first ps))
                    (rest ps)
                    (+ c 2)))
           (let [s (get D c)]
             (recur (add-composites
                     (persistent! (dissoc! (transient D) c))
                     (+ c s)
                     s)
                    p
                    q
                    ps
                    (+ c 2))))))))

比較のための最初の送信:

これは、この素数ジェネレーターを Python から Clojureに移植する試みです。以下は、無限の遅延シーケンスを返します。

(defn primes
  []
  (letfn [(prime-help
            [foo bar]
            (loop [D foo
                   q bar]
              (if (nil? (get D q))
                (cons q (lazy-seq
                         (prime-help
                          (persistent! (assoc! (transient D) (* q q) (list q)))
                          (inc q))))
                (let [factors-of-q (get D q)
                      key-val (interleave
                               (map #(+ % q) factors-of-q)
                               (map #(cons % (get D (+ % q) (list)))
                                    factors-of-q))]
                  (recur (persistent!
                          (dissoc!
                           (apply assoc! (transient D) key-val)
                           q))
                         (inc q))))))]
    (prime-help {} 2)))

使用法：

user=> (first (primes))
2
user=> (second (primes))
3
user=> (nth (primes) 100)
547
user=> (take 5 (primes))
(2 3 5 7 11)
user=> (time (nth (primes) 10000))
"Elapsed time: 409.052221 msecs"
104743

編集：

postponed-primesの再帰呼び出しではなく、これまでに見た素数のキューを使用するパフォーマンス比較postponed-primes:

user=> (def counts (list 200000 400000 600000 800000))
#'user/counts
user=> (map #(time (nth (postponed-primes) %)) counts)
("Elapsed time: 1822.882 msecs"
 "Elapsed time: 3985.299 msecs"
 "Elapsed time: 6916.98 msecs"
 "Elapsed time: 8710.791 msecs"
2750161 5800139 8960467 12195263)
user=> (map #(time (nth (postponed-primes-recursive) %)) counts)
("Elapsed time: 1776.843 msecs"
 "Elapsed time: 3874.125 msecs"
 "Elapsed time: 6092.79 msecs"
 "Elapsed time: 8453.017 msecs"
2750161 5800139 8960467 12195263)
于 2014-07-10T15:38:56.703 に答える
0

このスレッドに来て、すでにここにあるものよりも高速な代替手段を探した後、Christophe Grand による次の記事に誰もリンクしていないことに驚いています。

(defn primes3 [max]
  (let [enqueue (fn [sieve n factor]
                  (let [m (+ n (+ factor factor))]
                    (if (sieve m)
                      (recur sieve m factor)
                      (assoc sieve m factor))))
        next-sieve (fn [sieve candidate]
                     (if-let [factor (sieve candidate)]
                       (-> sieve
                         (dissoc candidate)
                         (enqueue candidate factor))
                       (enqueue sieve candidate candidate)))]
    (cons 2 (vals (reduce next-sieve {} (range 3 max 2))))))

怠惰なバージョンと同様に：

(defn lazy-primes3 []
  (letfn [(enqueue [sieve n step]
            (let [m (+ n step)]
              (if (sieve m)
                (recur sieve m step)
                (assoc sieve m step))))
          (next-sieve [sieve candidate]
            (if-let [step (sieve candidate)]
              (-> sieve
                (dissoc candidate)
                (enqueue candidate step))
              (enqueue sieve candidate (+ candidate candidate))))
          (next-primes [sieve candidate]
            (if (sieve candidate)
              (recur (next-sieve sieve candidate) (+ candidate 2))
              (cons candidate 
                (lazy-seq (next-primes (next-sieve sieve candidate) 
                            (+ candidate 2))))))]
    (cons 2 (lazy-seq (next-primes {} 3)))))
于 2016-04-05T16:30:58.003 に答える