解释C，Clojure，Python，Ruby，Scala等基准测试[关闭]

13 回答

• 16

  粗糙的答案：

  • Scala的静态类型在这里帮助了很多 - 这意味着它可以非常有效地使用JVM而无需太多额外的工作 .

  • 我不太确定Ruby / Python的区别，但我怀疑函数 is-prime? 中的 (2...n).all? 可能在Ruby中得到了很好的优化（编辑：听起来确实如此，请参阅Julian的答案以获取更多细节 . ..）

  • Ruby 1.9.3的优化程度要高得多

  • 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子系统的初始化或类似的事情！

  回复于 2024-04-28T18:54:54+08:00
• 3

  这是一个快速的Clojure版本，使用相同的基本算法：

  (set! *unchecked-math* true)
  
  (defn is-prime? [^long n]
    (loop [i 2]
      (if (zero? (unchecked-remainder-int n i))
        false
        (if (>= (inc i) n)
          true
          (recur (inc i))))))
  
  (defn sexy-primes [m]
    (for [x (range 11 (inc m))
          :when (and (is-prime? x) (is-prime? (- x 6)))]
      [(- x 6) x]))
  

  它比我的机器上的原始速度快20倍 . 这是一个利用1.5中新的reducers库的版本（需要Java 7或JSR 166）：

  (require '[clojure.core.reducers :as r]) ;'
  
  (defn sexy-primes [m]
    (->> (vec (range 11 (inc m)))
         (r/filter #(and (is-prime? %) (is-prime? (- % 6))))
         (r/map #(list (- % 6) %))
         (r/fold (fn ([] []) ([a b] (into a b))) conj)))
  

  这比原来的快40倍 . 在我的机器上，这是1.5秒内的100k .

  回复于 2024-04-28T18:54:54+08:00
• 2

  我'll answer just #2, since it'是我在 is_prime 中创建中间列表的唯一一个，而你在Ruby的_987306中使用 .map 只是迭代 .

  如果您将 is_prime 更改为：

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

  他们是平等的 .

  我可以进一步优化Python，但是我的Ruby没有更多的优势（例如，使用 xrange 使Python在我的机器上获胜，但是我不记得你使用的Ruby系列是否在内存中创建了整个范围） .

  EDIT: 没有太愚蠢，使Python代码看起来像：

  import time
  
  def is_prime(n):
      return all(n % j 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")
  

  对于我而言，它的变化不大，为1.5秒，而且，使用PyPy进行操作时，将其放在.3s为10K，21s为100K .

  回复于 2024-04-28T18:54:54+08:00
• 4

  通过将 isPrime 方法修改为，可以使Scala更快

  def isPrime(n: Int, i: Int = 2): Boolean = 
      if (i == n) true 
      else if (n % i != 0) isPrime(n, i + 1)
      else false
  

  不太简洁，但该程序在40％的时间内运行！

  我们删除了多余的 Range 和匿名 Function 对象，Scala编译器识别尾递归并将其转换为while循环，JVM可以将其转换为或多或少的最佳机器代码，所以它不应该太远C版 .

  另见：How to optimize for-comprehensions and loops in Scala?

  回复于 2024-04-28T18:54:54+08:00
• 7

  这是我的并行和非并行的scala版本，只是为了好玩:(在我的双核计算中，并行版本需要335ms而非并行版本需要655ms）

  object SexyPrimes {
    def isPrime(n: Int): Boolean = 
      (2 to math.sqrt(n).toInt).forall{ n%_ != 0 }
  
    def isSexyPrime(n: Int): Boolean = isPrime(n) && isPrime(n-6)
  
    def findPrimesPar(n: Int) {
      for(k <- (11 to n).par)
        if(isSexyPrime(k)) printf("%d %d\n",k-6,k)
    }
  
    def findPrimes(n: Int) {
      for(k <- 11 to n)
        if(isSexyPrime(k)) printf("%d %d\n",k-6,k)
    }
  
  
    def timeOf(call : =>Unit) {
      val start = System.currentTimeMillis
      call
      val end = System.currentTimeMillis
      println((end-start)+" mils")
    }
  
    def main(args: Array[String]) {
      timeOf(findPrimes(100*1000))
      println("------------------------")
      timeOf(findPrimesPar(100*1000))
    }
  }
  

  编辑：根据Emil H的建议，我已经改变了我的代码以避免IO和jvm热身的影响：

  结果显示在我的计算中：

  列表（3432,1934,3261,1716,3229,1654,3214,1700）

  object SexyPrimes {
    def isPrime(n: Int): Boolean = 
      (2 to math.sqrt(n).toInt).forall{ n%_ != 0 }
  
    def isSexyPrime(n: Int): Boolean = isPrime(n) && isPrime(n-6)
  
    def findPrimesPar(n: Int) {
      for(k <- (11 to n).par)
        if(isSexyPrime(k)) ()//printf("%d %d\n",k-6,k)
    }
  
    def findPrimes(n: Int) {
      for(k <- 11 to n)
        if(isSexyPrime(k)) ()//printf("%d %d\n",k-6,k)
    }
  
  
    def timeOf(call : =>Unit): Long = {
      val start = System.currentTimeMillis
      call
      val end = System.currentTimeMillis
      end - start 
    }
  
    def main(args: Array[String]) {
      val xs = timeOf(findPrimes(1000*1000))::timeOf(findPrimesPar(1000*1000))::
               timeOf(findPrimes(1000*1000))::timeOf(findPrimesPar(1000*1000))::
               timeOf(findPrimes(1000*1000))::timeOf(findPrimesPar(1000*1000))::
               timeOf(findPrimes(1000*1000))::timeOf(findPrimesPar(1000*1000))::Nil
      println(xs)
    }
  }
  

  回复于 2024-04-28T18:54:54+08:00
• 8

  别介意基准;问题让我感兴趣，我做了一些快速调整 . 这使用了 lru_cache 装饰器，它记忆了一个函数;所以当我们打电话给 is_prime(i-6) 时，我们基本上可以免费获得优质支票 . 这一变化将工作大致减少了一半 . 也，我们可以通过奇数来调整 range() 调用，将工作大致减半 .

  http://en.wikipedia.org/wiki/Memoization

  http://docs.python.org/dev/library/functools.html

  这需要Python 3.2或更高版本来获取 lru_cache ，但如果您安装提供 lru_cache 的Python配方，则可以使用较旧的Python . 如果您使用的是Python 2.x，那么您应该使用 xrange() 而不是 range() .

  http://code.activestate.com/recipes/577479-simple-caching-decorator/

  from functools import lru_cache
  import time as time_
  
  @lru_cache()
  def is_prime(n):
      return n%2 and all(n%i for i in range(3, n, 2))
  
  def primes_below(x):
      return [(i-6, i) for i in range(9, x+1, 2) if is_prime(i) and is_prime(i-6)]
  
  correct100 = [(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)]
  assert(primes_below(100) == correct100)
  
  a = time_.time()
  print(primes_below(30*1000))
  b = time_.time()
  
  elapsed = b - a
  print("{} msec".format(round(elapsed * 1000)))
  

  以上只需很短的时间进行编辑 . 我决定更进一步，并使素数测试只尝试素数除数，并且只测试被测数的平方根 . 我这样做的方式只有在按顺序检查数字时才有效，所以它可以积累所有素数;但是这个问题已经按顺序检查了数字，所以很好 .

  在我的笔记本电脑上（没什么特别的;处理器是1.5 GHz AMD Turion II“K625”）这个版本在8秒内产生了100K的答案 .

  from functools import lru_cache
  import math
  import time as time_
  
  known_primes = set([2, 3, 5, 7])
  
  @lru_cache(maxsize=128)
  def is_prime(n):
      last = math.ceil(math.sqrt(n))
      flag = n%2 and all(n%x for x in known_primes if x <= last)
      if flag:
          known_primes.add(n)
      return flag
  
  def primes_below(x):
      return [(i-6, i) for i in range(9, x+1, 2) if is_prime(i) and is_prime(i-6)]
  
  correct100 = [(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)]
  assert(primes_below(100) == correct100)
  
  a = time_.time()
  print(primes_below(100*1000))
  b = time_.time()
  
  elapsed = b - a
  print("{} msec".format(round(elapsed * 1000)))
  

  上面的代码很容易用Python，Ruby等编写，但在C语言中会更加难以理解 .

  您无法将此版本的数字与其他版本的数字进行比较，而无需重写其他版本以使用类似的技巧 . 我不想在这里证明什么;我只是觉得问题很有趣，我想看看我能收集哪些简单的性能改进 .

  回复于 2024-04-28T18:54:54+08:00
• 30

  别忘了Fortran！ （大多是开玩笑，但我希望与C相似） . 带感叹号的语句是可选的，但风格很好 . （ ! 是fortran 90中的评论字符）

  logical function isprime(n)
  IMPLICIT NONE !
  integer :: n,i
  do i=2,n
     if(mod(n,i).eq.0)) return .false.
  enddo
  return .true.
  end
  
  subroutine findprimes(m)
  IMPLICIT NONE !
  integer :: m,i
  logical, external :: isprime
  
  do i=11,m
     if(isprime(i) .and. isprime(i-6))then
        write(*,*) i-6,i
     endif
  enddo
  end
  
  program main
  findprimes(10*1000)
  end
  

  回复于 2024-04-28T18:54:54+08:00
• 6

  我无法抗拒为C版本进行一些最明显的优化，这使得100k测试现在在我的机器上花费0.3秒（比问题中的C版本快5倍，都使用MSVC 2010 / Ox编译） .

  int isprime( int x )
  {
      int i, n;
      for( i = 3, n = x >> 1; i <= n; i += 2 )
          if( x % i == 0 )
              return 0;
      return 1;
  }
  
  void findprimes( int m )
  {
      int i, s = 3; // s is bitmask of primes in last 3 odd numbers
      for( i = 11; i < m; i += 2, s >>= 1 ) {
          if( isprime( i ) ) {
              if( s & 1 )
                  printf( "%d %d\n", i - 6, i );
              s |= 1 << 3;
          }
      }
  }
  
  main() {
      findprimes( 10 * 1000 );
  }
  

  这是Java中完全相同的实现：

  public class prime
  {
      private static boolean isprime( final int x )
      {
          for( int i = 3, n = x >> 1; i <= n; i += 2 )
              if( x % i == 0 )
                  return false;
          return true;
      }
  
      private static void findprimes( final int m )
      {
          int s = 3; // s is bitmask of primes in last 3 odd numbers
          for( int i = 11; i < m; i += 2, s >>= 1 ) {
              if( isprime( i ) ) {
                  if( ( s & 1 ) != 0 )
                      print( i );
                  s |= 1 << 3;
              }
          }
      }
  
      private static void print( int i )
      {
          System.out.println( ( i - 6 ) + " " + i );
      }
  
      public static void main( String[] args )
      {
          // findprimes( 300 * 1000 ); // for some JIT training
          long time = System.nanoTime();
          findprimes( 10 * 1000 );
          time = System.nanoTime() - time;
          System.err.println( "time: " + ( time / 10000 ) / 100.0 + "ms" );
      }
  }
  

  使用Java 1.7.0_04，它的运行速度几乎与C版本一样快 . 客户端或服务器VM没有显示出太大差异，除了JIT培训似乎有助于服务器VM（~3％），而它对客户端VM几乎没有影响 . Java中的输出似乎比C中的输出慢 . 如果在两个版本中输出都替换为静态计数器，则Java版本的运行速度比C版本快一些 .

  这些是我运行100k的时间：

  用/ Ox编译

  • 319ms C并输出到> NIL：
    用/ Ox和静态计数器编译

  • 312ms C.
    输出为> NIL的

  • 324ms Java客户端VM：

  • 299ms带有静态计数器的Java客户端VM

  和1M运行（16386结果）：

  用/ Ox和静态计数器编译

  • 24.95s C.

  • 25.08s带有静态计数器的Java客户端VM

  • 24.86s带有静态计数器的Java服务器VM

  虽然这并没有真正回答你的问题，但它表明小的调整会对性能产生显着的影响 . 因此，为了能够真正比较语言，您应尽量避免所有算法差异 .

  它还提示了为什么Scala看起来相当快 . 它在Java VM上运行，因此可以从其令人印象深刻的性能中受益 .

  回复于 2024-04-28T18:54:54+08:00
• 4

  在Scala中尝试使用Tuple2而不是List，它应该更快 . 只需删除单词'List'，因为（x，y）是Tuple2 .

  Tuple2专门用于Int，Long和Double，这意味着它不必对这些原始数据类型进行打包/取消装箱 . Tuple2 source . 列表不专业 . List source .

  回复于 2024-04-28T18:54:54+08:00
• 23

  这是Go（golang.org）版本的代码：

  package main
  
  import (
      "fmt"
  )
  
  
  func main(){
      findprimes(10*1000)
  }
  
  func isprime(x int) bool {
      for i := 2; i < x; i++ {
          if x%i == 0 {
              return false
          }
      }
      return true
  }
  
  func findprimes(m int){
      for i := 11; i < m; i++ {
          if isprime(i) && isprime(i-6) {
              fmt.Printf("%d %d\n", i-6, i)
          }
      }
  }
  

  它的运行速度与C版本一样快 .

  Using an Asus u81a 英特尔酷睿2双核T6500 2.1GHz，2MB二级高速缓存，800MHz FSB . 4GB RAM

  100k版本： C: 2.723s Go: 2.743s

  使用1000000（1M而不是100K）： C: 3m35.458s Go: 3m36.259s

  但我认为使用Go的内置多线程功能并将该版本与常规C版本（没有多线程）进行比较是公平的，因为使用Go进行多线程处理几乎太容易了 .

  更新：我在Go中使用Goroutines做了一个并行版本：

  package main
  
  import (
    "fmt"
    "runtime"
  )
  
  func main(){
      runtime.GOMAXPROCS(4)
      printer := make(chan string)
      printer2 := make(chan string)
      printer3 := make(chan string)
      printer4 := make(chan string)
      finished := make(chan int)
  
      var buffer, buffer2, buffer3 string
  
      running := 4
      go findprimes(11, 30000, printer, finished)
      go findprimes(30001, 60000, printer2, finished)
      go findprimes(60001, 85000, printer3, finished)
      go findprimes(85001, 100000, printer4, finished)
  
      for {
        select {
          case i := <-printer:
            // batch of sexy primes received from printer channel 1, print them
            fmt.Printf(i)
          case i := <-printer2:
            // sexy prime list received from channel, store it
            buffer = i
          case i := <-printer3:
            // sexy prime list received from channel, store it
            buffer2 = i
          case i := <-printer4:
            // sexy prime list received from channel, store it
            buffer3 = i
          case <-finished:
            running--
            if running == 0 {
                // all goroutines ended
                // dump buffer to stdout
                fmt.Printf(buffer)
                fmt.Printf(buffer2)
                fmt.Printf(buffer3)
                return
            }
        }
      }
  }
  
  func isprime(x int) bool {
      for i := 2; i < x; i++ {
          if x%i == 0 {
              return false
          }
      }
      return true
  }
  
  func findprimes(from int, to int, printer chan string, finished chan int){
      str := ""
      for i := from; i <= to; i++ {
          if isprime(i) && isprime(i-6) {
              str = str + fmt.Sprintf("%d %d\n", i-6, i)
        }
      }
      printer <- str
      //fmt.Printf("Finished %d to %d\n", from, to)
      finished <- 1
  }
  

  并行化版本平均使用2.743秒，与常规版本使用的完全相同 .

  并行版本在1.706秒内完成 . 它使用的RAM不到1.5 Mb .

  奇怪的是：我的双核kubuntu 64bit从未在两个内核中达到顶峰 . 看起来Go只使用了一个核心 . 通过调用 runtime.GOMAXPROCS(4) 修复

  更新：我运行了paralellized版本高达1M的数字 . 我的一个CPU内核一直是100％，而另一个根本没有使用（奇数） . 它花了整整一分钟比C和常规Go版本 . :(

  使用1000000（1M而不是100K）：

  C: 3m35.458s Go: 3m36.259s Go using goroutines: 3m27.137s 2m16.125s

  100k版本：

  C: 2.723s Go: 2.743s Go using goroutines: 1.706s

  回复于 2024-04-28T18:54:54+08:00
• 4

  只是为了它的乐趣，这是一个并行的Ruby版本 .

  require 'benchmark'
  
  num = ARGV[0].to_i
  
  def is_prime?(n)
    (2...n).all?{|m| n%m != 0 }
  end
  
  def sexy_primes_default(x)
      (9..x).map do |i|
          [i-6, i]
      end.select do |j|
          j.all?{|j| is_prime? j}
      end
  end
  
  def sexy_primes_threads(x)
      partition = (9..x).map do |i|
          [i-6, i]
      end.group_by do |x|
          x[0].to_s[-1]
      end
      threads = Array.new
      partition.each_key do |k|
         threads << Thread.new do
              partition[k].select do |j|
                  j.all?{|j| is_prime? j}
              end
          end
      end
      threads.each {|t| t.join}
      threads.map{|t| t.value}.reject{|x| x.empty?}
  end
  
  puts "Running up to num #{num}"
  
  Benchmark.bm(10) do |x|
      x.report("default") {a = sexy_primes_default(num)}
      x.report("threads") {a = sexy_primes_threads(num)}
  end
  

  在我的1.8GHz Core i5 MacBook Air上，性能结果如下：

  # Ruby 1.9.3
  $ ./sexyprimes.rb 100000
  Running up to num 100000
                   user     system      total        real
  default     68.840000   0.060000  68.900000 ( 68.922703)
  threads     71.730000   0.090000  71.820000 ( 71.847346)
  
  # JRuby 1.6.7.2 on JVM 1.7.0_05
  $ jruby --1.9 --server sexyprimes.rb 100000
  Running up to num 100000
                  user     system      total        real
  default    56.709000   0.000000  56.709000 ( 56.708000)
  threads    36.396000   0.000000  36.396000 ( 36.396000)
  
  # JRuby 1.7.0.preview1 on JVM 1.7.0_05
  $ jruby --server sexyprimes.rb 100000
  Running up to num 100000
               user     system      total        real
  default     52.640000   0.270000  52.910000 ( 51.393000)
  threads    105.700000   0.290000 105.990000 ( 30.298000)
  

  看起来JVM的JIT在默认情况下为Ruby提供了不错的性能提升，而真正的多线程帮助JRuby在线程情况下执行速度提高了50％ . 更有趣的是JRuby 1.7通过 Health 改善了JRuby 1.6得分17％！

  回复于 2024-04-28T18:54:54+08:00
• 22

  基于x4u's answer，我使用递归编写了一个scala版本，并且我通过仅使用sqrt而不是x / 2作为主要检查函数来改进它 . 我得到约250毫秒，100k，约600毫秒，1M . 我继续前进，在6s内达到了10M .

  import scala.annotation.tailrec
  
  var count = 0;
  def print(i:Int) = {
    println((i - 6) + " " + i)
    count += 1
  }
  
  @tailrec def isPrime(n:Int, i:Int = 3):Boolean = {
    if(n % i == 0) return false;
    else if(i * i > n) return true;
    else isPrime(n = n, i = i + 2)
  }      
  
  @tailrec def findPrimes(max:Int, bitMask:Int = 3, i:Int = 11):Unit = {
    if (isPrime(i)) {
      if((bitMask & 1) != 0) print(i)
      if(i + 2 < max) findPrimes(max = max, bitMask = (bitMask | (1 << 3)) >> 1, i = i + 2)
    } else if(i + 2 < max) {
      findPrimes(max = max, bitMask = bitMask >> 1, i = i + 2)
    }
  }
  
  val a = System.currentTimeMillis()
  findPrimes(max=10000000)
  println(count)
  val b = System.currentTimeMillis()
  println((b - a).toString + " mils")
  

  我还回过头来写了一个CoffeeScript（V8 JavaScript）版本，通过使用一个计数器（忽略I / O），得到100k约为15ms，1M为250ms，10M为6s . 如果我打开输出，100k需要~150ms，1M需要1s，10M需要12s . 遗憾的是，不能在这里使用尾递归，所以我不得不将它转换回循环 .

  count = 0;
  print = (i) ->
    console.log("#{i - 6} #{i}")
    count += 1
    return
  
  isPrime = (n) ->
    i = 3
    while i * i < n
      if n % i == 0
        return false
      i += 2
    return true
  
  findPrimes = (max) ->
    bitMask = 3
    for i in [11..max] by 2
      prime = isPrime(i)
      if prime
        if (bitMask & 1) != 0
          print(i)
        bitMask |= (1 << 3)
      bitMask >>= 1
    return
  
  a = new Date()
  findPrimes(1000000)
  console.log(count)
  b = new Date()
  console.log((b - a) + " ms")
  

  回复于 2024-04-28T18:54:54+08:00
• 7

  问题＃1的答案是，是的，JVM非常快，是静态打字有帮助 .

  从长远来看，JVM应该比C更快，甚至可能比“普通”汇编语言更快 - 当然，您可以通过手动运行时分析并为每个CPU创建单独的版本来手动优化汇编以击败任何东西，您只需必须非常好，知识渊博 .

  Java速度的原因是：

  JVM可以在运行时分析您的代码并对其进行手动优化 - 例如，如果您有一个方法可以在编译时静态分析为真正的函数，并且JVM注意到您经常使用相同的方法调用它参数，它实际上可以完全消除调用，只是注入最后一次调用的结果（我不确定Java是否真的这样做，但它确实做了很多这样的事情） .

  由于静态类型化，JVM可以在编译时了解您的代码，这可以让它预先优化很多东西 . 它还允许编译器单独优化每个类，而无需了解另一个类计划如何使用它 . 此外，Java没有任意指向内存位置的指针，它知道内存中的哪些值可能也可能不会更改，因此可以进行优化 .

  堆分配比C更有效，Java的堆分配更像是C的堆栈速度分配 - 但更通用 . 很多时候已经进入了这里使用的不同的algroithim，它是一门艺术 - 例如，所有具有短寿命的对象（如C的堆栈变量）被分配到“已知”的自由位置（不搜索自由点）有足够的空间）并且在一个步骤中都被释放（就像堆栈弹出一样） .

  JVM可以了解有关CPU架构的怪癖，并专门为给定的CPU生成机器代码 .

  JVM可以在您发送代码后很长时间加快代码速度 . 就像将程序移动到新的CPU可以加快速度一样，将它移动到JVM的新版本也可以为你提供巨大的速度性能，这些性能在你最初编译你的代码时甚至不存在，而物理上不可能没有重新推荐 .

  顺便说一句，java速度的大部分坏代表都来自加载JVM的漫长启动时间（有一天有人会将JVM构建到操作系统中，这将会消失！）以及许多开发人员在编写时非常糟糕的事实GUI代码（特别是线程）导致Java GUI经常变得无响应和毛病 . 简单易用的Java和VB等语言的缺点是，普通程序员的能力往往低于更复杂的语言 .

  回复于 2024-04-28T18:54:54+08:00