这是我对一个函数的解决方案,该函数应该返回第一对两个质数,如果这些数字存在,则在限制 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
最佳答案
试试这个:
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
第二个版本不会构建包含所有对的新数组,而是仅检查每个素数 if prime + g
包含在primes
中阵也。我用 Set
,因为它改进了include?
查找O(1)
(而数组上的 include?
将为 O(n)
。
我不确定哪个版本会更快,并且运行一些基准测试可能是值得的。第一个版本需要更多内存,但计算量较少。性能可能取决于范围的大小。
关于ruby - 可能效率低下的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39824898/