紅寶石 - 可能效率低下的算法

這是我對一個函數的解決方案，它應該返回第一對兩個素數，間隔g與極限m，n之間的間隔g，否則爲零。紅寶石 - 可能效率低下的算法

這是來自codewars.com的kata，它通過了初步測試。但是，當我提交它時，我收到一條錯誤消息，說由於算法效率低下，它需要很多時間（8000ms +）。

有人能告訴我什麼是減慢代碼，以及它應該如何優化？

require 'prime' 

def gap(g, m, n) 
    range = (m..n).to_a 
    primes = [] 
    range.each { |num| primes.push(num) if Prime.prime?(num)} 


    primes.each_index do |count| 
    prv , nxt = primes[count], primes[count+1] 
    if !nxt.is_a? Integer 
     return nil 
    end 

    if nxt - prv == g 
     return [prv, nxt] 
    end 
    end 
end

來源

2016-10-03 Rafael Viana

感謝提示。但是，我仍然得到相同的錯誤信息：進程被終止。花了超過8000ms完成 –

如果您可以使用Ruby主模塊，我會在該模塊中查找將爲您生成範圍內的素數的方法，而不是使用p對範圍內的所有數字進行霧測試。通常這些模塊的優化可能比大多數專業程序員都要好得多。一個小的優化示例，其中模塊的主要生成器中可能會有更多更復雜的示例，您不需要對任何偶數進行主要測試（就像您當前所做的那樣）。 –

你也可以考慮https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes，具有指定差距的素數是否必須是連續的？ – user12341234

試試這個：

require 'prime' 

def gap(g, m, n) 
    primes = Prime.each(n).select { |p| p >= m } 
    primes[0..-2].zip(primes[1..-1]).find { |a, b| b - a == g } 
end 

gap(2, 1, 1000) 
#=> [3, 5] 

gap(6, 1, 1000) 
#=> [23, 29]

Prime.each(n).select { |p| p >= m }回報你m和n之間的所有質數的列表。這比建立一個所有數字在m和n之間的數組並且檢查數組中的每個數字（如果它是素數）的性能要好。值得注意的是，Prime.each使用eratosthenes的篩選算法作爲默認值。

primes[0..-2].zip(primes[1..-1])構建每對的數組。這不是迭代primes數組中每對的最有效方式，但我認爲它比處理索引讀得更好。

這可能是另一種選擇：

require 'prime' 
require 'set' 

def gap(g, m, n) 
    primes = Set.new(Prime.each(n).select { |p| p>= m }) 
    primes.each { |prime| return [prime, prime + g] if primes.include?(prime + g) } 
end

第二個版本不建立與所有對一個新的數組，但如果prime + g包含在primes數組中太，而不是僅僅檢查每一個素數。我用一個Set，因爲它提高include?查找到O(1)（而include?對數組會O(n)。

我不知道哪個版本將更快，這可能是值得的運行一些基準測試，第一個版本需要更多內存，但是計算量較少，性能可能取決於範圍的大小

來源

2016-10-03 06:03:55 spickermann

請注意，第一個解決方案將只能找到由間隙隔開的*個連續*素數對。例如，對於'g = 6'，它會找到'[23,29]'，但不是'[5,11]'。第二個解決方案會找到兩者。 – Amadan

你是對的，@Amadan。我錯過了我的優化的副作用。如果第二個例子甚至是一個選項，我認爲這取決於規範。在他的例子中，OP可能不得不使用第一個版本。但我會在答案中保留第二個版本，因爲它可能會幫助其他人。 *過早優化是萬惡之源--Donald Knuth * – spickermann

正如你所說，這取決於任務。根據OP的說法，我確實認爲你的*第一個*版本是不正確的：P：D但是真的，目前還不清楚哪一個是真正的任務。 – Amadan

紅寶石 - 可能效率低下的算法

回答

相關問題