红宝石 - 可能效率低下的算法

这是我对一个函数的解决方案，它应该返回第一对两个素数，间隔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

红宝石 - 可能效率低下的算法

回答

相关问题