Ruby - 使用惰性求值查找第一个 N 回文素数

Question

我认为我的代码是正确的 - 但我没有及时返回 N = 200 的数组。错误是“由于超时而终止” 我该怎么做才能提高这段代码的性能？

def is_palindrome? (n)
   n.to_s==n.to_s.reverse
end

def is_prime? (n)
  return false if n< 2
  (2..Math.sqrt(n)).none? {|f| n % f == 0}
end

prime_palindrome =-> (n) do
   1.upto(Float::INFINITY).lazy.select { |n| is_prime?(n) && is_palindrome(n) }.first(n)
end


n = gets.to_i 
p prime_palindrome.call(n)

Answer 1

Ruby 知道如何更快地做到这一点。

require 'prime'

Prime.each.lazy.
    select { |p| p.to_s.then { |s| s == s.reverse } }.
    take(200).to_a

Answer 2

惰性枚举器（如 @Amadan 的答案中使用的）很有用，但似乎因速度有点慢而闻名。我认为在这里做一个简单的基准测试可能会很有趣，将 Amadan 的答案与使用

while

循环的简单计算进行比较。

require 'prime'

惰性枚举器

def amadan(n)
  Prime::EratosthenesSieve.instance.send(:initialize)       
  Prime.each.lazy.
    select { |p| p.to_s.then { |s| s == s.reverse } }.
    take(n).to_a
end

while循环

def cary(n)
  Prime::EratosthenesSieve.instance.send(:initialize)
  arr = []
  enum = Prime.each
  while n > 0
    p = enum.next
    s = p.to_s
    if s == s.reverse
      arr << p
      n -= 1
    end
  end
  arr
end

每个方法的第一行，

Prime::EratosthenesSieve...

都包含在内，以使基准测试更加现实。请参阅评论中的讨论。

基准

require 'fruity'

#

n = 200
compare(amadan: -> { amadan(n) }, cary: -> { cary(n) })

Running each test once. Test will take about 10 seconds.
cary is faster than amadan by 10.000000000000009% ± 1.0%

Results are similar for other values of `n`.

Answer 3

您只是忘记了您编写的第一个代码中的问号“？”。如果我们添加它，您的代码就可以工作，但使用 Prime 是一个更合乎逻辑、更快的解决方案。

def is_palindrome? (n)
    n.to_s==n.to_s.reverse
 end
 
 def is_prime? (n)
   return false if n< 2
   (2..Math.sqrt(n)).none? {|f| n % f == 0}
 end
 
 prime_palindrome =-> (n) do
    1.upto(Float::INFINITY).lazy.select { |n| is_prime?(n) && is_palindrome?(n) }.first(n)
 end
 
 
 n = gets.to_i 
 p prime_palindrome.call(n)