python - 用 C、Clojure、Python、Ruby、Scala 和其他语言解释基准

Question

免责声明

我知道人为的基准是邪恶的。他们只能在非常具体的狭窄情况下显示结果。我不认为一种语言比另一种更好，因为一些愚蠢的板凳。但是我想知道为什么结果如此不同。请在底部查看我的问题。

数学基准描述

Benchmark 是简单的数学计算，用于查找相差 6 的素数对(所谓的 sexy primes) 例如。低于 100 的性感素数将是:(5 11) (7 13) (11 17) (13 19) (17 23) (23 29) (31 37) (37 43) (41 47) (47 53) (53 59) (61 67) (67 73) (73 79) (83 89) (97 103)

结果表

表格中:计算时间，以秒为单位 运行:除 Factor 之外的所有设备都在 VirtualBox 中运行(Debian 不稳定的 amd64 guest ，Windows 7 x64 主机) CPU:AMD A4-3305M

  Sexy primes up to:        10k      20k      30k      100k               

  Bash                    58.00   200.00     [*1]      [*1]

  C                        0.20     0.65     1.42     15.00

  Clojure1.4               4.12     8.32    16.00    137.93

  Clojure1.4 (optimized)   0.95     1.82     2.30     16.00

  Factor                    n/a      n/a    15.00    180.00

  Python2.7                1.49     5.20    11.00       119     

  Ruby1.8                  5.10    18.32    40.48    377.00

  Ruby1.9.3                1.36     5.73    10.48    106.00

  Scala2.9.2               0.93     1.41     2.73     20.84

  Scala2.9.2 (optimized)   0.32     0.79     1.46     12.01

[*1] - 恐怕要花多少时间

代码 list

C:

int isprime(int x) {
  int i;
  for (i = 2; i < x; ++i)
    if (x%i == 0) return 0;
  return 1;
}

void findprimes(int m) {
  int i;
  for ( i = 11; i < m; ++i)
    if (isprime(i) && isprime(i-6))
      printf("%d %d\n", i-6, i);
}

main() {
    findprimes(10*1000);
}

鲁比:

def is_prime?(n)
  (2...n).all?{|m| n%m != 0 }
end

def sexy_primes(x)
  (9..x).map do |i|
    [i-6, i]
  end.select do |j|
    j.all?{|j| is_prime? j}
  end
end

a = Time.now
p sexy_primes(10*1000)
b = Time.now
puts "#{(b-a)*1000} mils"

斯卡拉:

def isPrime(n: Int) =
  (2 until n) forall { n % _ != 0 }

def sexyPrimes(n: Int) = 
  (11 to n) map { i => List(i-6, i) } filter { _ forall(isPrime(_)) }

val a = System.currentTimeMillis()
println(sexyPrimes(100*1000))
val b = System.currentTimeMillis()
println((b-a).toString + " mils")

Scala 优化了 isPrime(与 Clojure 优化中的想法相同):

import scala.annotation.tailrec

@tailrec // Not required, but will warn if optimization doesn't work
def isPrime(n: Int, i: Int = 2): Boolean = 
  if (i == n) true 
  else if (n % i != 0) isPrime(n, i + 1)
  else false

Clojure:

(defn is-prime? [n]
  (every? #(> (mod n %) 0)
    (range 2 n)))

(defn sexy-primes [m]
  (for [x (range 11 (inc m))
        :let [z (list (- x 6) x)]
        :when (every? #(is-prime? %) z)]
      z))

(let [a (System/currentTimeMillis)]
  (println (sexy-primes (* 10 1000)))
  (let [b (System/currentTimeMillis)]
    (println (- b a) "mils")))

Clojure 优化 is-prime?:

(defn ^:static is-prime? [^long n]
  (loop [i (long 2)] 
    (if (= (rem n i) 0)
      false
      (if (>= (inc i) n) true (recur (inc i))))))

Python

import time as time_

def is_prime(n):
  return all((n%j > 0) for j in xrange(2, n))

def primes_below(x):
  return [[j-6, j] for j in xrange(9, x+1) if is_prime(j) and is_prime(j-6)]

a = int(round(time_.time() * 1000))
print(primes_below(10*1000))
b = int(round(time_.time() * 1000))
print(str((b-a)) + " mils")

因素

MEMO:: prime? ( n -- ? )
n 1 - 2 [a,b] [ n swap mod 0 > ] all? ;

MEMO: sexyprimes ( n n -- r r )
[a,b] [ prime? ] filter [ 6 + ] map [ prime? ] filter dup [ 6 - ] map ;

5 10 1000 * sexyprimes . .

重击(zsh):

#!/usr/bin/zsh
function prime {
  for (( i = 2; i < $1; i++ )); do
    if [[ $[$1%i] == 0 ]]; then
      echo 1
      exit
    fi
  done
  echo 0
}

function sexy-primes {
  for (( i = 9; i <= $1; i++ )); do
    j=$[i-6]
    if [[ $(prime $i) == 0 && $(prime $j) == 0 ]]; then
      echo $j $i
    fi
  done
}

sexy-primes 10000

问题

1. 为什么 Scala 这么快？是因为静态类型吗？或者它只是非常有效地使用 JVM？
2. 为什么 Ruby 和 Python 之间有如此巨大的差异？我认为这两者并没有完全不同。也许我的代码是错误的。请赐教!谢谢。 UPD 是的，那是我的代码中的错误。 Python 和 Ruby 1.9 相当。
3. Ruby 版本之间的生产力飞跃确实令人印象深刻。
4. 我可以通过添加类型声明来优化 Clojure 代码吗？会有帮助吗？

Answer 1

粗略的回答:

1. Scala 的静态类型在这里帮了大忙 - 这意味着它可以非常高效地使用 JVM，而无需太多额外的努力。
2. 我不太确定 Ruby/Python 的区别，但我怀疑 (2...n).all? 函数中的 is-prime? 可能在 Ruby 中得到了很好的优化(编辑:听起来确实是这样，有关更多详细信息，请参阅 Julian 的答案...)
3. Ruby 1.9.3 得到了更好的优化
4. Clojure 代码当然可以加速很多!虽然 Clojure 默认是动态的，但在许多情况下，您可以在需要时使用类型提示、原始数学等来接近 Scala/纯 Java 的速度。

Clojure 代码中最重要的优化是在 is-prime? 中使用类型化的原始数学，例如:

(set! *unchecked-math* true) ;; at top of file to avoid using BigIntegers

(defn ^:static is-prime? [^long n]
  (loop [i (long 2)] 
    (if (zero? (mod n i))
      false
      (if (>= (inc i) n) true (recur (inc i))))))

通过这项改进，我让 Clojure 在 0.635 秒内完成 10k(即在您的列表中第二快，击败了 Scala)

P.S. 请注意，在某些情况下，您会在基准测试中打印代码 - 这不是一个好主意，因为它会扭曲结果，尤其是在使用类似 print 的函数时第一次导致初始化 IO 子系统或类似的东西!