如何优化这一段ruby代码以加快速度？

发布时间：2020-12-17 01:44:01 所属栏目：百科来源：网络整理

导读：它是 Sieve of Eratosthenes的实现. class PrimeGenerator def self.get_primes_between( x,y) sieve_array = Array.new(y) {|index| (index == 0 ? 0 : index+1) } position_when_we_can_stop_checking = Math.sqrt(y).to_i (2..position_when_we_can_stop_

它是 Sieve of Eratosthenes的实现.

class PrimeGenerator
  def self.get_primes_between( x,y)
    sieve_array = Array.new(y) {|index|
      (index == 0 ? 0 : index+1)
    }

    position_when_we_can_stop_checking = Math.sqrt(y).to_i
    (2..position_when_we_can_stop_checking).each{|factor|
      sieve_array[(factor).. (y-1)].each{|number|
        sieve_array[number-1] = 0 if isMultipleOf(number,factor)
      }
    }

    sieve_array.select{|element| 
      ( (element != 0) && ( (x..y).include? element) )
    }
  end
  def self.isMultipleOf(x,y)
    return (x % y) == 0
  end
end

现在我这样做是为了“提交问题解决方案,因为你有时间杀死”网站.我选择ruby作为我的impl语言..然而我被宣布超时.
我做了一些基准测试

require 'benchmark'
Benchmark.bmbm do |x|
  x.report ("get primes") { PrimeGenerator.get_primes_between(10000,100000)}
  end

ruby 1.9.1p0(2009-01-30修订版21907)[i386-mswin32]

L:GishuRuby>ruby prime_generator.rb
Rehearsal ----------------------------------------------
get primes  33.953000   0.047000  34.000000 ( 34.343750)
------------------------------------ total: 34.000000sec

                 user     system      total        real
get primes  33.735000   0.000000  33.735000 ( 33.843750)

ruby 1.8.6(2007-03-13 patchlevel 0)[i386-mswin32]

Rehearsal ----------------------------------------------
get primes  65.922000   0.000000  65.922000 ( 66.110000)
------------------------------------ total: 65.922000sec

                 user     system      total        real
get primes  67.359000   0.016000  67.375000 ( 67.656000)

所以我在C#2.0 / VS 2008中重新编写了这个东西 – >
722毫秒

那么现在这让我觉得我的实现是一个问题还是这种语言之间的差异？ (我对1.9 Ruby Ruby感到惊讶……直到我不得不将它与C#进行比较:)

更新：
原本是我的“put-eratosthenes-to-shame-adapt”:)消除不必要的循环迭代是主要的优化.如果有人对细节感兴趣,你可以阅读它here;反正这个问题太长了.

解决方法

我不知道它如何比较速度,但这是一个相当小而简单的SoE实现,对我来说很好用：

def sieve_to(n)
  s = (0..n).to_a
  s[0]=s[1]=nil
  s.each do |p|
    next unless p
    break if p * p > n
    (p*p).step(n,p) { |m| s[m] = nil }
  end
  s.compact
end

还有一些可能的加速,但我认为这是非常好的.

它们并不完全等效,所以你的10_000到1_000_000等于

sieve_to(1_000_000) - sieve_to(9_999)

或者近似的东西.

无论如何,在WinXP上,使用Ruby 1.8.6(和相当大的Xeon CPU),我得到了这个：

require 'benchmark'
Benchmark.bm(30) do |r|
  r.report("Mike") { a = sieve_to(10_000) - sieve_to(1_000) } 
  r.report("Gishu") { a = PrimeGenerator.get_primes_between( 1_000,10_000) }
end

这使

user     system      total        real
Mike                            0.016000   0.000000   0.016000 (  0.016000)
Gishu                           1.641000   0.000000   1.641000 (  1.672000)

(我因为无聊等待而停止了100万箱的运行).

所以我会说这是你的算法.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!