如何提高eratosthenes算法的clojure筛选性能？

我正在通过euler项目学习clojure，并且正在处理第10个问题（查找所有素数低于200万的数据总和）。我为eratosthenes筛选实现了一个非常字面的算法，但它的运行速度太慢，高达两百万是有用的。我试图与环RECUR实现它不产生任何新的框架，但没有对性能有很大的影响。如何提高eratosthenes算法的clojure筛选性能？

(defn find-primes-sum [last-prime nums] 
    (loop [p last-prime n nums sum 0] 
     (println p) 
     (if (empty? n) 
     sum 
      (recur (first n) (doall (remove #(zero? (mod % (first n))) n)) (+ sum (first n)))))) 

(defn sieve-primes-until [limit] 
    (find-primes-sum 2 (filter odd? (range 2 (inc limit))))) 

(println (sieve-primes-until 2000000))

来源

2011-06-17 Scott

有这个页面，你会发现有趣的相关部分的几个问题。 – 2011-06-17 14:53:33

就个人而言，我想不同的结构代码。我已经实现了这个问题，首先生成所有素数的懒序列，然后总计第一个2,000,000个项目。在clojure 1.2中需要16秒，但除了使用重复之外，它几乎没有优化。

与输入范围相比，您还做了很多不必要的工作; (remove #(zero? (mod % (first n))) n)测试所有候选人对所有奇数，这是胡说八道，尤其是当你强迫它与doall。实际上，您只需要针对所有已知的素数< = sqrt（x）测试候选素数x，并在找到您的第一个匹配项时放弃候选人。

**我刚刚注意到你的算法并不那么愚蠢，但我仍然建议你重写你的算法，因为一个懒惰seq发现“下一个素数”给定了以前的素数和候选数。

来源

2011-06-17 13:26:21

抽象是很好的眼睛和优化。编写更小，更好的函数比优化复杂函数更直观。正如@ Joost-Diepenmaat所说，至少要分开总理和总结。尽管如此，不要过多地讨论这个特殊的问题。有些人为他们的博士写了筛选算法！ – 2011-06-17 13:53:51

(set! *unchecked-math* true) 

(defmacro iloop [[b t n] & body] 
    `(loop [[email protected]] 
    (when ~t 
     [email protected] 
     (recur ~n)))) 

(defn count-primes [^long n] 
    (let [c (inc n) 
     ^booleans prime? (make-array Boolean/TYPE c)] 
    (iloop [(i 2) (<= i n) (inc i)] 
     (aset prime? i true)) 
    (iloop [(i 2) (<= (* i i) n) (inc i)] 
     (if (aget prime? i) 
     (iloop [(j i) (<= (* i j) n) (inc j)] 
      (aset prime? (* i j) false)))) 
    (areduce prime? i r 0 
     (if (aget prime? i) 
     (inc r) 
     r))))

该版本的目标是Clojure 1.3.0 alpha。它在我的机器上在2秒内计算出1e8的质数。它可以很容易地改变来收集它们。最初的写法是为了表明您可以实现筛选，以便运行速度与可比较的Java相同。

http://dosync.posterous.com/lispers-know-the-value-of-everything-and-the

来源

2011-06-18 15:04:15 dnolen

如何提高eratosthenes算法的clojure筛选性能？

回答

相关问题