ある整数にもっとも近い素数を求める（Enumerable#each_consとEnumerable#lazyを使う） #Ruby

概要

先日の投稿がRubyっぽくなかったので、Enumerable#each_consとEnumerable#lazyを使って書き直してみる。

方針

今回求めたい直近の素数は、対象の整数より小さい場合も大きい場合もある
Prime#eachに引数を与えることで、その引数以下の素数を列挙することはできるが、次の素数は列挙されない
Prime#eachに引数を与えない（nil）と無限に素数を列挙する
Enumerable#each_consを使って連続する2つの素数の組を列挙する
その素数の組から、対象の整数を挟むものを選び、対象の整数からの距離が小さいものを直近の素数とする

Prime.each(13).to_a
# => [2, 3, 5, 7, 11, 13]

Prime.each(13).each_cons(2).to_a
# => [[2, 3], [3, 5], [5, 7], [7, 11], [11, 13]]

# 対象の整数をmとして、
# Prime.each.each_cons(2).select { |p, n| p < m && m < n }.first.min_by { |e| (m - e).abs }
# としたいところだが、Prime.each.each_cons(2)が無限のEnumeratorを返すので、selectのブロックが無限に繰り返されてしまう、、

#Enumerable#lazyを使って遅延評価する
Prime.each.each_cons(2).lazy.select { |p, n| p < m && m < n }.first.min_by { |e| (m - e).abs }
# => mに最も近い素数

コード

まとめると、

require 'prime'

class Prime
  def nearest_prime (m)
    return m if self.prime? m
    self.each.each_cons(2).lazy
      .select { |p, n| p < m && m < n }
      .first
      .min_by { |e| (m - e).abs }
  end
end

Prime.nearest_prime 30000
# => 29989

Prime.nearest_prime 50000
# => 49999

となり、見た目がRubyっぽくなった。

パフォーマンス

先日の単純ループによる実装と比較するためベンチマークをとってみる。

require 'benchmark'

class Prime
  def nearest_prime_loop (n)
    d = 0
    loop do
      p = n + d
      break p if self.prime? p
      p = n - d
      break p if self.prime? p
      d += 1
    end
  end
end

Benchmark.bm do |x|
  x.report("each:") { Prime.nearest_prime 100}
  x.report("each:") { Prime.nearest_prime 1000}
  x.report("each:") { Prime.nearest_prime 10000}
  x.report("each:") { Prime.nearest_prime 100000}
  x.report("each:") { Prime.nearest_prime 1000000}
  x.report("each:") { Prime.nearest_prime 10000000}
  x.report("each:") { Prime.nearest_prime 100000000}
end
       user     system      total        real
each:  0.000000   0.000000   0.000000 (  0.000000)
each:  0.000000   0.000000   0.000000 (  0.000000)
each:  0.000000   0.000000   0.000000 (  0.006001)
each:  0.078000   0.000000   0.078000 (  0.096005)
each:  0.437000   0.000000   0.437000 (  0.432025)
each:  3.541000   0.000000   3.541000 (  3.638208)
each:1351.515000   4.758000 1356.273000 (1404.176314)

Benchmark.bm do |x|
  x.report("loop:") { Prime.nearest_prime_loop 100}
  x.report("loop:") { Prime.nearest_prime_loop 1000}
  x.report("loop:") { Prime.nearest_prime_loop 10000}
  x.report("loop:") { Prime.nearest_prime_loop 100000}
  x.report("loop:") { Prime.nearest_prime_loop 1000000}
  x.report("loop:") { Prime.nearest_prime_loop 10000000}
  x.report("loop:") { Prime.nearest_prime_loop 100000000}
end
       user     system      total        real
loop:  0.000000   0.000000   0.000000 (  0.000000)
loop:  0.000000   0.000000   0.000000 (  0.000000)
loop:  0.000000   0.000000   0.000000 (  0.000000)
loop:  0.000000   0.000000   0.000000 (  0.000000)
loop:  0.000000   0.000000   0.000000 (  0.001000)
loop:  0.000000   0.000000   0.000000 (  0.002000)
loop:  0.000000   0.000000   0.000000 (  0.007001)

課題

上記パフォーマンス問題。
100000000の直近の素数を求めるのに20分以上かかってる。
桁が大きい素数ほど知りたいので、どうにかしたいところ。

あと、

Prime.nearest_prime 30000

は本来、30011と29989（どちらも30000との差が11）の２つであるが、
Enumerable#min_byは最小の要素が複数ある場合の返す要素が不定なので、今回は29989となっている。
両方、もしくはどちらかを返すようにしたい。