如何優化這一點的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 

我這樣做是爲了一個「提交問題的解決方案，因爲你有時間殺」的網站。我選擇了紅寶石作爲我的impl語言，但是我宣佈超時。 我做了一些基準

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

紅寶石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) 

紅寶石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 VM ...直到我不得不去與C＃:)比較一下

UPDATE： 竟然是我的「放 - 埃拉托色尼到恥辱適應」畢竟:) 消除不必要的循環迭代是主要的優化。如果有人對細節感興趣..你可以閱讀here;反正這個問題太長了。

Answer 1

我不知道它是如何比較速度，但是這是一個相當小的，簡單的環境狀況實施，對我工作得很好：

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（和相當沉重的至強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＃解決方案几乎可以保證數量級的提高。

Answer 2

Eratosthenes的篩子可以很好地作爲尋找素數的說明性方式，但我會實施它有點不同。其實質是，你不必檢查已知素數的倍數。現在，不是使用數組來存儲這些信息，還可以創建一個所有連續素數的列表，直到您正在檢查的數字的平方根，然後通過素數列表來檢查素數就足夠了。

如果你想到它，這就是你在圖像上所做的，但是以更「虛擬」的方式。

編輯：快速砍死實現我的意思（不是從網上覆制;））：

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; 
    } 
    } 

我慢的機器上使用大約67ms ....測試程序：

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); 
    } 
} 

Answer 3

我會先看看你的內循環。 sieve_array[(factor).. (y-1)]將在每次執行時創建一個新數組。相反，嘗試用正常的索引循環替換它。

Answer 4

我還會注意到，根據我的經驗，Ruby在Windows系統上比在* nix上慢很多。當然，我不確定你有什麼速度處理器，但是在Ruby 1.9的Ubuntu盒子上運行此代碼需要大約10秒鐘，而1.8.6花費了30分鐘。

Answer 5

使用ruby-prof進行基準測試。它可以吐出像kcachegrind這樣的工具，可以查看代碼速度慢的地方。

然後，一旦你使ruby快速，使用RubyInline來優化你的方法。

Answer 6

很顯然，每臺計算機都會以不同的方式進行基準測試，但是通過使用每個模塊刪除陣列上的循環，並且通過使得該計算機（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