我在Clojure中找到了以下代码,用于筛选出前n个质数:
定时结果如下: 对于Clojure:
(defn sieve [n]
(let [n (int n)]
"Returns a list of all primes from 2 to n"
(let [root (int (Math/round (Math/floor (Math/sqrt n))))]
(loop [i (int 3)
a (int-array n)
result (list 2)]
(if (>= i n)
(reverse result)
(recur (+ i (int 2))
(if (< i root)
(loop [arr a
inc (+ i i)
j (* i i)]
(if (>= j n)
arr
(recur (do (aset arr j (int 1)) arr)
inc
(+ j inc))))
a)
(if (zero? (aget a i))
(conj result i)
result)))))))
接着,我用 Scheme(使用 mit-scheme)编写了相应的代码(我认为是这样的)
(define (sieve n)
(let ((root (round (sqrt n)))
(a (make-vector n)))
(define (cross-out t to dt)
(cond ((> t to) 0)
(else
(vector-set! a t #t)
(cross-out (+ t dt) to dt)
)))
(define (iter i result)
(cond ((>= i n) (reverse result))
(else
(if (< i root)
(cross-out (* i i) (- n 1) (+ i i)))
(iter (+ i 2) (if (vector-ref a i)
result
(cons i result))))))
(iter 3 (list 2))))
定时结果如下: 对于Clojure:
(time (reduce + 0 (sieve 5000000)))
"Elapsed time: 168.01169 msecs"
对于mit-scheme:
(time (fold + 0 (sieve 5000000)))
"Elapsed time: 3990 msecs"
有人可以告诉我为什么mit-scheme慢20多倍吗?
更新:“差异在于解释器/编译模式。在我编译 mit-scheme 代码后,它的运行速度相当快。- abo-abo Apr 30 '12 at 15:43”
make-vector
将使用0
填充向量,而在Scheme中它被视为true。将其更改为(make-vector n #f)
会产生更合理的结果。 - Sam Tobin-Hochstadt