10

我在 Clojure 中找到了这段代码来筛选出前n 个素数：

(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 方案：

(time (fold + 0 (sieve 5000000)))
"Elapsed time: 3990 msecs"

谁能告诉我为什么 mit-scheme 慢了 20 倍以上？

更新：“不同之处在于迭代/编译模式。在我编译了 mit-scheme 代码后，它的运行速度相当快。– abo-abo 2012 年4 月 30 日 15:43 ”

4

2 回答 2

15

与解释型语言相比，Java 虚拟机的现代版本具有极好的性能。大量的工程资源进入了 JVM，特别是热点 JIT 编译器、高度优化的垃圾收集等。

我怀疑你看到的差异主要是因为这个。例如，如果您查看Java 程序是否更快？您可以看到 java 与 ruby​​ 的比较，这表明 java 在其中一个基准测试中的表现要好 220 倍。

你没有说你正在运行你的 clojure 基准测试的 JVM 选项。尝试使用-Xint以纯解释模式运行的标志运行 java，看看有什么区别。

此外，您的示例可能太小而无法真正预热 JIT 编译器。使用更大的示例可能会产生更大的性能差异。

让您了解 Hotspot 对您的帮助程度。我在我的 MBP 2011（四核 2.2Ghz）上运行了您的代码，使用带有默认选项（-server 热点）和解释模式（-Xint）的 java 1.6.0_31，并看到了很大的不同

; with -server hotspot (best of 10 runs)
>(time (reduce + 0 (sieve 5000000)))
"Elapsed time: 282.322 msecs"
838596693108

; in interpreted mode using -Xint cmdline arg
> (time (reduce + 0 (sieve 5000000)))
"Elapsed time: 3268.823 msecs"
838596693108
于 2012-04-30T14:33:18.857 回答
5

至于比较 Scheme 和 Clojure 代码，在 Clojure 端有一些事情需要简化：

  • 不要在循环中重新绑定可变数组；
  • 删除许多显式的原始强制，性能没有变化。从 Clojure 1.3 开始，如果这样的函数签名可用，函数调用中的文字将编译为原语，并且通常性能差异非常小，以至于它很快就会被循环中发生的任何其他操作所淹没；
  • 将原始长注释添加到 fn 签名中，从而消除 n 的重新绑定；
  • 不需要调用 Math/floor —— int 强制具有相同的语义。

代码：

(defn sieve [^long n]
 (let [root (int (Math/sqrt n))
       a (int-array n)]
   (loop [i 3, result (list 2)]
     (if (>= i n)
       (reverse result)
       (do
         (when (< i root)
           (loop [inc (+ i i), j (* i i)]
             (when (>= j n) (aset a j 1) (recur inc (+ j inc)))))
         (recur (+ i 2) (if (zero? (aget a i))
                          (conj result i)
                          result)))))))
于 2012-05-02T08:54:30.090 回答