起初我使用暴力算法,这很容易实现。但是,在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))])))))
通过使用一个新的程序,它考虑了一些额外的规则(如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更小,它也会导致堆栈溢出。尽管我使用了recur,但这可能是我的错。
接下来,我尝试了一个筛法,使用Java ArrayList上的Java方法。那花了相当长的时间和内存。
我最新的尝试是使用Clojure哈希映射的筛法,将所有数字插入筛子中,然后取消不是质数的数字。最后,它采用键列表,这些键是它找到的质数。查找10000个素数大约需要10-12秒。我不确定它是否完全调试好了。它也是递归的(使用recur和loop),因为我想成为Lispy。
所以对于这些问题,问题10(将2000000以下的所有质数相加)让我感到困扰。我的最快代码得出了正确的答案,但是它花费了105秒才能完成,并且需要相当多的内存(我给了它512 MB,只是为了不必担心它)。我的其他算法太慢了,我总是先停止它们。
我可以使用筛法在Java或C中快速计算出这么多质数,而且不需要使用太多内存。我知道我一定在我的Clojure / Lisp风格中漏掉了什么,导致出现问题。
我做错了什么吗?Clojure对于大序列是否有点慢?阅读一些项目Euler的讨论,人们在其他Lisps中计算出前10000个质数不到100毫秒。我知道JVM可能会减慢速度,而Clojure相对较年轻,但我不希望有100倍的差异。
有人能告诉我在Clojure中快速计算质数的方法吗?