ruby - 可能效率低下的算法

Question

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

这是codewars.com的套路，通过了初步测试。但是，当我提交它时，我收到一条错误消息，指出由于我的算法效率低下，它需要太多时间(8000 毫秒以上)。

谁能告诉我究竟是什么导致代码变慢，应该如何优化？

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

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