可能的低效算法

Question

这是我对一个函数的解，该函数应返回两个素数的第一对，如果这两个素数存在，则在极限m, n之间间隔为g，否则为nil。

这是一个来自codewars.com的数据，它通过了初步测试。但是，当我提交它时，我收到一条错误消息，说由于我的算法效率低下，它需要太多时间(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

Answer 1

试试这个:

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使用埃拉托色尼的筛选算法作为默认值。

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))。

我不确定哪个版本会更快，可能值得运行一些基准测试。第一个版本需要更多的内存，但计算更少。性能可能取决于范围的大小。