如何优化这段 Ruby 代码以提高速度？

Question

这是一个实现埃拉托斯特尼筛法的程序。

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 作为我的实现语言，但我被声明超时了。我做了一些基准测试。

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

ruby 1.9.1p0 (2009-01-30 revision 21907) [i386-mswin32]

可以翻译为：Ruby 1.9.1p0（2009年1月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 patchlevel 0) [i386-mswin32]

可以翻译为：Ruby 1.8.6（2007年3月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#比较为止：）

更新： 结果证明这确实是我的“超越欧拉筛”的问题 :) 消除不必要的循环迭代 是主要的优化。如果有人对细节感兴趣，可以在这里阅读；反正这个问题太长了。

- Gishu

Answer 1

显然，每台计算机的基准测试结果都会有所不同，但是通过使用each块来消除数组循环，并使内部循环检查更少的数字，我能够使此程序在我的机器上（Ruby 1.8.6）运行速度提高约50倍。

factor=2
while factor < position_when_we_can_stop_checking 
    number = factor
    while number < y-1
      sieve_array[number-1] = 0 if isMultipleOf(number, factor)
      number = number + factor; # Was incrementing by 1, causing too many checks
    end
  factor = factor +1
end

- mmc

---

是的，按因子跳跃也是另一种节省时间的方法。 - Gishu

Answer 2

我建议先看一下你的内层循环。每次执行sieve_array[(factor).. (y-1)]都会创建一个新的数组。相反地，尝试用普通的索引循环来替换它。

- Dave Ray

---

这让我的时间缩短了8秒。 - Gishu

Answer 3

埃拉托斯特尼筛法是一种寻找质数的示例方法，但我会稍微改进它。其实质就是你不必检查已知质数的倍数。现在，你可以创建一个包含所有顺序质数的列表，直到要检查的数字的平方根，而不是使用数组来存储这些信息，然后只需遍历质数列表以检查质数即可。

如果你考虑一下，这做了你在图像上所做的事情，但以更“虚拟”的方式。

编辑：快速实现我的意思（不是从网上复制的）：

  public class Sieve {
    private readonly List<int> primes = new List<int>();
    private int maxProcessed;

    public Sieve() {
      primes.Add(maxProcessed = 2); // one could add more to speed things up a little, but one is required
    }

    public bool IsPrime(int i) {
      // first check if we can compare against known primes
      if (i <= primes[primes.Count-1]) {
        return primes.BinarySearch(i) >= 0;
      }
      // if not, make sure that we got all primes up to the square of i
      int maxFactor = (int)Math.Sqrt(i);
      while (maxProcessed < maxFactor) {
        maxProcessed++;
        bool isPrime = true;
        for (int primeIndex = 0; primeIndex < primes.Count; primeIndex++) {
          int prime = primes[primeIndex];
          if (maxProcessed % prime == 0) {
            isPrime = false;
            break;
          }
        }
        if (isPrime) {
          primes.Add(maxProcessed);
        }
      }
      // now apply the sieve to the number to check
      foreach (int prime in primes) {
        if (i % prime == 0) {
          return false;
        }
        if (prime > maxFactor) {
          break;
        }
      }
      return true;
    }
  }

在我的慢速计算机上使用约67毫秒...测试应用程序：

class Program {
    static void Main(string[] args) {
        Stopwatch sw = new Stopwatch();
        sw.Start();
        Sieve sieve = new Sieve();
        for (int i = 10000; i <= 100000; i++) {
            sieve.IsPrime(i);
        }
        sw.Stop();
        Debug.WriteLine(sw.ElapsedMilliseconds);
    }
}

- Lucero

Answer 4

我不知道它在速度方面如何比较，但这是一个相当小而简单的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)

我停止了运行一百万个案例，因为等待的时间太长，让我感到无聊。

所以我认为这是你的算法问题。 ;-)

然而，使用C#解决方案可以保证比其它解决方案快上几个数量级。

- Mike Woodhouse

---

谢谢。理解你的代码片段很有趣，感受到了重新成为程序员的喜悦。此外，它的简洁性符合 Ruby 的风格。 - Gishu

还有，您选择使用sieve_to(y)-sieve_to(x-1)来获取结果的原因是什么，而不是使用sieve_to(y).select{|prime| (prime >= x)}？ - Gishu

谢谢。我一直在玩Project Euler：有几个问题需要大量的质数列表，所以我已经调整到了我能力范围内。 嗯。当我注意到between(x,y)时，sieve_to() - sieve_to()这件事是我脑海中最先想到的。你的方法可能更适合大x。或者，将sieve_to更改为从x向上压缩数组。 :) - Mike Woodhouse

Answer 5

我还要指出，根据我的经验，Ruby在Windows系统上比*nix慢得多。当然，我不知道你的处理器速度是多少，但在我的Ubuntu机器上运行这段代码需要大约10秒钟，在Ruby 1.8.6上需要30秒钟。

- Greg Campbell

Answer 6

使用ruby-prof进行基准测试，它可以输出类似kcachegrind的工具，以查看代码哪里运行缓慢。

然后，一旦使Ruby变快，使用RubyInline为您优化方法。

- Daniel Huckstep