ruby - 我如何优化这段 ruby​​ 代码以使其运行得更快？

Question

它是 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:\Gishu\Ruby>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 补丁级别 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 VM 感到惊讶......直到我不得不将它与 C# 进行比较:)

更新:毕竟是我的“put-eratosthenes-to-shame-adaptation”:) Eliminating unnecessary loop iterations 是主要的优化。如果有人对细节感兴趣......你可以阅读它here ;反正这个问题太长了。

Answer 1

我将从查看您的内部循环开始。 sieve_array[(factor).. (y-1)] 将在每次执行时创建一个新数组。相反，请尝试用普通索引循环替换它。