Clojure中快速素数生成

Question

我一直在努力解决Clojure中的Project Euler问题,以便变得更好,而且我已经遇到了几次素数.我的问题是它只是花了太长时间.我希望有人可以帮我找到一种以Clojure-y方式做到这一点的有效方法.

当我拳头做到这一点时,我粗暴地强迫它.这很容易做到.但是计算10001个素数在Xeon 2.33GHz上用了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))])))))

通过将新的例程替换为考虑了一些额外规则(例如6n +/- 1属性)的next-prime-slow,我能够将速度提高到大约70秒.

接下来,我试着在纯粹的Clojure中筛选出Eratosthenes.我不认为我得到了所有的错误,但我放弃了,因为它太慢了(我认为甚至比上面更糟糕).

(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较小,它还会导致堆栈溢出.尽管事实上我正在使用复发.那可能是我的错.

接下来,我尝试使用Java ArrayList上的Java方法筛选.这需要相当多的时间和记忆.

我最近的尝试是使用Clojure哈希映射的筛子,在筛子中插入所有数字然后分解不是素数的数字.最后,它采用密钥列表,它是它找到的素数.找到10000个素数需要大约10-12秒.我不确定它是否已经完全调试过了.它也是递归的(使用recur和loop),因为我试图成为Lispy.

因此,对于这些问题,问题10(总计2000000以下的所有素数)正在扼杀我.我最快的代码提出了正确的答案,但它需要105秒才能完成,并需要相当多的内存(我给它512 MB只是所以我不必大惊小怪).我的其他算法花了这么长时间我总是先停止它们.

我可以使用筛子来快速计算Java或C中的许多质数,而不需要使用太多的内存.我知道我必须在我的Clojure/Lisp风格中遗漏导致问题的东西.

有什么我做错了吗？Clojure对大序列有点慢吗？阅读一些项目的欧拉讨论,人们已经在不到100毫秒的时间内计算了其他Lisps中的前10000个素数.我意识到JVM可能会减慢速度并且Clojure相对年轻,但我不希望它有100倍的差异.

有人可以通过快速的方式启发我来计算Clojure中的素数吗？

Answer 1

这是另一种庆祝的方法Clojure's Java interop.这需要在2.4 Ghz Core 2 Duo上运行374ms(运行单线程).我让Miller-RabinJava中的高效实现BigInteger#isProbablePrime处理primality检查.

(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)))))

Miller-Rabin对于比这大得多的数字,5 的确定性可能不是很好.这种确定性等于96.875%确定它是素数(1 - .5^certainty)

Answer 2

我意识到这是一个非常古老的问题,但我最近最终寻找相同的东西,这里的链接不是我正在寻找的东西(尽可能限制功能类型,懒洋洋地生成〜每个我想要的素数) .

我偶然发现了一个很好的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))    

Answer 3

聚会很晚,但我会举一个例子,使用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"

Answer 4

请参阅此处的最后一个示例: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)

Answer 5

这是一个很好且简单的实现：

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

...但它是为 Clojure 1.0 之前的版本编写的。请参阅Clojure Contrib 中的lazy_seqs，了解适用于该语言当前版本的seqs。