或るプログラマの開発日記

日々の勉強したことの備忘録なんかに使っていきます

CodeIQ 「タンジェント・フラクション」問題解答コード

CodeIQ問題の解答公開記事です。
codeiq.jp

問題の概要

今回は以下のような問題でした。

  • 0 < \alpha < \beta < \pi/2を満たす実数\alpha,\betaの組について、tan(\alpha),tan(\beta),tan(\alpha+\beta)がすべて単位分数(分母が自然数、分子が 1 )となるものを考えます。(\alpha,\betaの単位はラジアン)
  • 正の実数{m}に対し、{m\leqq\alpha+\beta}の範囲で題意を満たす{\alpha,\beta}の組の個数を{F(m)}と定義します。
  • 正の実数 m(0.001 < m < 1)が与えられた時のF(m)の値を出力しなさい。

方針

この問題を解くためには、以下の三角関数の公式を使います。

tan(\alpha+\beta) = \displaystyle \frac{tan(\alpha)+tan(\beta)}{1-tan(\alpha)tan(\beta)}

題意から、tan(\alpha),tan(\beta)はそれぞれ単位分数となるので、a,b自然数とした時に、それぞれ\displaystyle \frac{1}{a},\displaystyle \frac{1}{b}とあらわす事が出来ます。これを先の公式に当てはめると、

tan(\alpha+\beta) = \displaystyle \frac{\displaystyle \frac{1}{a}+\frac{1}{b}}{1- \displaystyle \frac{1}{ab}} = \displaystyle \frac{a+b}{ab-1}

となります。

というわけで、tan(m) \le \displaystyle \frac{a+b}{ab-1} を満たし、且つ右辺が単位分数になるような自然数a,bの組み合わせの数を算出すれば良いと言う事になります。

解答コード

こちらが提出したコードになります。

class Codeiq3182
  def solve(m)
    cnt = 0
    tan_m = Math.tan(m)
    max_b = (1 / Math.tan( m / 2.0 )).to_i
    (2..max_b).each do |b|
      i=((b**2 -1).to_f / (2 * b).to_f).ceil
      (i..(b-1)).each do |n|
        (a, r) =  ((n*b) + 1).divmod(b-n)
        next if  (r != 0)
        tan_ab = (a + b).to_f / ((a * b) -1)
        break if(tan_ab < tan_m)
        cnt += 1
      end
    end
    return cnt
  end
end
puts Codeiq3182.new.solve(gets.to_f)

\displaystyle \frac{a+b}{ab-1}が単位分数になるので、n自然数とした時に
\displaystyle \frac{n(a+b)}{ab-1} = 1が成り立つ自然数a,b,nの組を求める方法で解いています。
上記の式を組み変えると、\displaystyle a = \frac{nb+1}{b-1}になるので、右辺を実際に計算して余り0になるb,nの組み合わせの数をカウントしてます。
bの値を定義した時、aの値が計算上1以上になるようにnの初期値を調整しているのが、工夫といえば工夫なのかもしれません。

感想とか

三角関数とか使うのは学生時代以来なので、最初は問題の内容を理解するだけでいっぱいいっぱいでした(><)

記事ではさらっとtanの公式を書いていますが、実際はかなり数学の解説サイトをググって調べてきたものです。もはやこのへんの公式とかは、頭の中からすっぽり抜け落ちてしまってますなー。。


また、今回の解法もかなりしらみつぶし的なやり方で解いているので、もう少し効率の良いやり方があるのかと色々考えては見ましたが、現状ではこれが精一杯ですw

実行速度は、まだまだ改善の余地はありそうですね。

2017年6月の目標

どうも、パイソンです。

気が付けば、もう6月も7日目。先月は月中から月末にかけて記事を書いてきた跳ね返りか、1週間程ブログを放置しておりました。

しかし、このままずるずるとしてると今月は何もしないまま過ぎ去ってしまいそうなので、ここいらで6月の目標を書いてみようかと思います。

6月はRailsの勉強をします!

4月と5月で結構自分なりにRubyの勉強をしてきましたので、ここいらでRailsなるものの勉強を本格的に開始してみたいと思います。

まーRailsを勉強する動機が、「Railsって結構使われているみたいだから、プログラマとしてはチョッと齧っておいた方がいいんじゃね?」という多少拙いものですが、何事も経験して見ることが大事だと言う事で、、。

正直言って、現在の自分にはRailsに関する知識は全くございませんが、Railsに関する書籍なんかも図書館から借りて少しづつコツコツと勉強していこうと思います。

月末には、Herokuあたりにアプリを上げれたらいいなー。。

記事更新について

今月は主にRailsに関する勉強に時間を割きたいので、6月の記事はRailsの勉強メモを中心に投稿します。

ま、それ以外には先月の引き続きでアルゴリズム関係のメモとか、CodeIQの解答記事なんかを投稿していこうかと。



とゆーわけで、6月も頑張ります!

ブログ開始から2ヶ月経過しました

どうも、パイソンです。

今日でブログ開始からちょうど2ヶ月目。先月に引き続きこれまでの振り返りをします。

5月の目標

5月も目標なるものを立てておりました。

  1. rubyでなんか作る
  1. 記事更新は10記事程度を目処に

それぞれどんな感じだったか振り返ります。

rubyでなんか作る

5月前半に、実際どんなものが作れるかなーと色々検討等してみたのですが、現状は未だ形にはなっておりません。(´・ω・`)

実際、「Railsでもさわってみっかー」とか、「ナンプレソルバーでも作ってみっかー」とか色々試して見てはいたんですが、未だ完成の目処は立たずという状態です。

ま、出来なかったものをあれこれ悔やんでもどうしようも無いので、この辺は来月以降も継続してトライすることにします。

記事更新は10記事程度を目処に

5月はこの振り返りを含めて10記事目。一応数はこなしたかという感じですかねー。

思えば、5月1日ゴールデンウィークの初日に記事を書いてから、連休モードで最初の1週間を過ごしてしまい、その勢いで3週間程度更新の間隔が空いてしまいました。そっから月末にかけて帳尻を合わせたという感があります。

やはり、一度サボり癖がついてしまうとそのリカバリが大変という事が今更ながら理解できた気がします。

次月に向けて

1ヶ月は長いようで、気が付けばあっという間に過ぎ去ってしまうもの。次月以降は計画的に更新していけるように頑張ります。

Rubyで素数判定の繰り返しを効率化してみた話

はじめに

とあるプログラミング問題に取り組んでる時、連続する数をそれぞれ素数か否かの判断を結構な回数繰り返す処理をRubyで書いていたのですが、もう少し処理速度が上がらんかなーと試行錯誤した結果、処理が効率化できたー。というお話です。

問題

実際の問題をそのまま紹介すると要点が分かりづらくなるので、今回は例題として以下の問題を考えます。

20,000,000以上21,000,000以下の素数がいくつあるか求めよ。

※あくまで説明の為のサンプル問題になります。

簡単な実装

RubyではPrimeクラスで素数かどうかの判定ができるので、以下のように実装すれば答えは出ます。

require "prime"
val = 20000000
cnt = 0
loop do
  cnt += 1 if Prime.prime?(val)
  val += 1
  break if val > 21000000
end
puts cnt#=>59336

効率化の検討

前述の実装で答えは出ますが、如何せん処理が重たく数十秒程度は掛かってしまいます。そこで、prime?メソッドを効率よく使うことが出来ないか調査してみることにしました。

prime?メソッドを調べてみる

https://docs.ruby-lang.org/ja/latest/class/Prime.html#I_PRIME--3F
ドキュメントに拠れば、prime?メソッドの仕様は以下の通り。

prime?(value, generator = Prime::Generator23.new) -> bool

第1引数のvalueのほかに、どうもgeneratorなるものがあります。そこで、Generator23クラスも調べてみます。

2と3と、3 より大きくて 2 でも 3 でも割り切れない全ての整数を生成します。

ある整数の素数性を疑似素数による試し割りでチェックする場合、このように低精度だが高速でメモリを消費しない疑似素数生成器が適しています。

https://docs.ruby-lang.org/ja/search/query:Prime::Generator23/#entry-0

どうやら、このクラスは疑似素数の配列を生成して、素数の判定に利用しているようです。
ちなみに、実行してみるとこんな感じの値の数列を作ってくれます。

gen = Prime::Generator23.new()
20.times do
  print "%d " % gen.next() 
end
#=>2 3 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 
試行1:Generator23のインスタンスをループ外から渡してみる

じゃ、ループ外で1回インスタンス生成して使い回せば効率良くなるんじゃね?
というわけで、以下のようなコードにしてみました。

require "prime"
val = 20000000
cnt = 0
gen = Prime::Generator23.new
loop do
  cnt += 1 if Prime.prime?(val, gen)
  val += 1
  break if val > 21000000
end
puts cnt
#=>999998

が、これはダメ!
何故か素数判定が上手く行かず、ほとんどの数が素数として扱われてしまったようです。これは失敗例。

prime?の中身を覗いてみる

Eclipseのデバッガを使い、実際prime?メソッドが何してるか覗いてみる。

  def prime?(value, generator = Prime::Generator23.new)
    raise ArgumentError, "Expected a prime generator, got #{generator}" unless generator.respond_to? :each
    raise ArgumentError, "Expected an integer, got #{value}" unless value.respond_to?(:integer?) && value.integer?
    return false if value < 2
    generator.each do |num|
      q,r = value.divmod num
      return true if q < num
      return false if r == 0
    end
  end

このコードを覗いてみると、以下の事が分かります。

  • 引数generatorはeachメソッドを実装していることが必須。
  • generator.eachで得られる数を用いて素数判定をしている。
  • 判定処理で得られた商が除数より小さい時処理を打ち切っている。よってeachメソッドで得られる値が昇順であることが前提。

恐らく、試行1でやったgeneratorのインスタンスを1回だけ生成するやり方では、それぞれの数の素数判定をする際に内部で呼ばれるeachメソッドで得られる値が最初からではなくなるので正常な判定が出来なかったのでしょう。

試行2:素数配列を予めつくっておいて、prime?メソッドに渡す

eachメソッドを実装してれば良いらしいので、素数の配列作っておいて渡せばイケるんじゃね?
ということで以下のコードを書いてみました。なお、素数の配列は判定する値の最大値の平方根までの値があれば十分です。

require "prime"
val = 20000000
cnt = 0
prime_array = Prime.each(Math.sqrt(21000000).to_i).to_a
loop do
  cnt += 1 if Prime.prime?(val, prime_array)
  val += 1
  break if val > 21000000
end
puts cnt#=>59336

今度は、正しく判定できた様です。しかも気持ち処理速度は大分改善されたようです。

試行3:素数配列を予めつくっておいて、判定処理も自作する

しかし、元々Generatorを受け取る前提で作成されたメソッドに、(動くとはいえ)自作の配列を突っ込むのは多少気が引けます。というか、Rubyがバージョンアップした場合にこのコードが正しく動くのかどうか怪しいものです。

ということで、もう素数判定のメソッドも自分で実装することにします。

require "prime"
def is_prime(num, p_array)
  p_array.each do |x|
    q, r = num.divmod(x)
    return false if r == 0
    return true  if q < x
  end
end

val = 20000000
cnt = 0
prime_array = Prime.each(Math.sqrt(21000000).to_i).to_a
loop do
  cnt += 1 if is_prime(val, prime_array)
  val += 1
  break if val > 21000000
end
puts cnt#=>59336

こちらも正しい結果が返ってきました。コードは少し長くなりましたが、標準のメソッドに本来想定してないものを渡してるかも?という気持ち悪さは解消できたと思います。

処理時間計測

今までの処理をベンチマークで計測してみます。

require "prime"
require 'benchmark'
def is_prime(num, p_array)
  p_array.each do |x|
    q, r = num.divmod(x)
    return false if r == 0
    return true  if q < x
  end
end

Benchmark.bm 10 do |x|
  #単純な実装版
  x.report "prime_1" do
    val = 20000000
    cnt = 0
    loop do
      cnt += 1 if Prime.prime?(val)
      val += 1
      break if val > 21000000
    end
    #puts cnt
  end
  #prime?に素数配列を渡す版
  x.report "prime_2" do
    val = 20000000
    cnt = 0
    prime_array = Prime.each(Math.sqrt(21000000).to_i).to_a
    loop do
      cnt += 1 if Prime.prime?(val, prime_array)
      val += 1
      break if val > 21000000
    end
    #puts cnt
  end
  #判定処理自作版
  x.report "prime_3" do
    val = 20000000
    cnt = 0
    prime_array = Prime.each(Math.sqrt(21000000).to_i).to_a
    loop do
      cnt += 1 if is_prime(val, prime_array)
      val += 1
      break if val > 21000000
    end
    #puts cnt
  end
end

結果

                 user     system      total        real
prime_1     25.912000   0.000000  25.912000 ( 25.980192)
prime_2      7.238000   0.000000   7.238000 (  7.253440)
prime_3      6.911000   0.000000   6.911000 (  6.908018)

単純な実装版より、判定処理の自作版の方が3倍以上の効率で処理できました。

まとめ

今回は、標準のメソッドを使わずに自作で判定処理を実装することで処理効率を劇的に上げることが出来ました。

だだ、今回のケースでは以下のような前提条件が揃っているので自作の判定処理の効率の良さが出たと思います。

  • 判定する数の最大値が予め予測できる事
  • 繰り返しの数が多いこと
  • 判定する素数の値自体が大きい数でること

判定する数の最大値が高々1,000程度だったり、判定する回数が数十回程度のケースではわざわざ処理を自作して効率を求めるよりは、コードの可読性という観点からすると標準のメソッドを素直に利用したほうが良いのかもしれません。

というわけで、今回は処理効率を上げる為にはこんな方法もありますよーというお話でした。

Rubyで素因数分解を行う

素因数分解C言語Javaで行う場合、自力で小さい素数から順に割っていく方法なんかが取られるかと思いますが、Rubyでは標準モジュールに素因数分解の処理が用意されていたのでメモ。

Primeクラスのprime_divisionメソッド

Rubyでは、このメソッド一発で素因数分解が出来ます。Ruby便利すぎる。。

使い方
require "prime"
p Prime.prime_division(360)#=>[[2, 3], [3, 2], [5, 1]]
p Prime.prime_division(1683)#=>[[3, 2], [11, 1], [17, 1]]
p Prime.prime_division(65536)#=>[[2, 16]]
p Prime.prime_division(8635844967113809)#=>[[89652331, 1], [96325939, 1]]

prime_divisionメソッドは2次元配列で結果を返してきます。

例として360を素因数分解すると、
360=2^3 \times 3^2 \times 5^1
となります。戻り値は各素因数とそのベキ指数の2要素の配列の配列ということですね。

因みに、prime_divisionメソッドにかなり大きい数の素数を引数に与えると結構処理時間が掛かります。

最大公約数、最小公倍数の求め方/ユーグリットの互除法

今回もアルゴリズムに関して学んだ知識のメモ。ユーグリットの互除法について調べてみました。

ユーグリットの互除法とは

最大公約数を求める手法です。

ユークリッドの互除法ユークリッドのごじょほう、英: Euclidean Algorithm)は、2 つの自然数の最大公約数を求める手法の一つである。

https://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95

高校数学なんかでも学ぶ内容ですし、かなり有名なアルゴリズムですね。

ユーグリットの互除法のアルゴリズム

割り算で求めるやり方と引き算で求めるやり方があります。
以下、それぞれのやり方での整数aとb(a >= b)の最大公約数の求め方を記載します。

割り算バージョン
  1. aをbで割った余りを求める。
  2. 余りが0の場合、bが最大公約数。
  3. 余りが0以外の場合、除数(割った数)を先程の余りで割りその余りを求める。
  4. これを余りが0になるまで繰り返す。余りが0になった時の除数が最大公約数
引き算バージョン
  1. aをbで引いた差を求める。
  2. 差が0の場合、bが最大公約数。
  3. 差が0以外の場合、引いた数と差の大きい方から小さい方を引いた差を求める。
  4. これを差が0になるまで繰り返す。差が0になった時の減数(引いた数)が最大公約数

計算量としては割り算で求めるやり方のほうが少ないかと思われます。

最小公倍数の求め方

最大公約数が求めることができれば、最小公倍数は以下の式で求める事が出来ます。

A,Bの最小公倍数=A×B÷A,Bの最大公約数

実装

というわけで、今回もRubyで実装してみます。

#割り算バージョン
def gcd(a, b)
  a, b = b, a if a < b
  loop do
    m = a % b
    return b if m == 0
    a, b = b, m
  end
end

#引き算バージョン
def gcd2(a, b)
  loop do
    a, b = b, a if a < b
    d = a - b
    return b if d == 0
    a, b = b, d
  end
end

#最小公倍数
def lcm(a, b)
  return ((a * b) / gcd(a, b))
end

puts gcd(1071, 1029)#=>21
puts gcd2(1071, 1029)#=>21
puts lcm(1071, 1029)#=>52479

おまけ

ま、Rubyの場合は標準でメソッドが用意されているんですけどねー。

puts 1071.gcd(1029)#=>21
puts 1071.lcm(1029)#=>52479

解法の中身を理解する事も重要だと思います。

エラトステネスのふるいを実装してみる

アルゴリズムに関する知識も自分の中にストックしておきたいということで、今回は「エラトステネスのふるい」について調査したものをメモ。

エラトステネスのふるいとは

素数の一覧を簡易的に求める手法です。

エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。

https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9

手法としては極めて簡潔で、2以上の整数のリストから先ず2の倍数を削除し、次に3の倍数をリストから削除、次に5の倍数を削除という具合に小さい素数から順にその合成数を削除するというやり方です。

アルゴリズム

或る整数nまでの素数を求める場合

  1. 2からnまでの整数を列挙した探索リストを作成する。
  2. 配列の先頭の数を素数リストに移動し、その数の倍数を配列から篩い落とす。
  3. 上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う。
  4. 探索リストに残った数を素数リストに移動して処理終了。

以上の要領で処理を行います。

実装

Rubyで実装をしてみました。2からMAX_NUMまでの素数リストを作成、出力するプログラムです。

MAX_NUM = 120
array = (2..MAX_NUM).to_a
x = 2
s = Math::sqrt(MAX_NUM)
loop do
  pn = array.find{|num| num >= x }
  array.delete_if{|num| num != pn && num % pn == 0 }
  break if x >= s
  x += 1
end
p array

実行結果

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]

Rubyの標準モジュールPrime

Rubyでは素数を扱うモジュールが標準で用意されています。
(実は、実装した後にこの事実に気づいた。。( ̄▽ ̄;))

class Prime (Ruby 2.4.0)

require "prime"
p Prime.each(120).to_a
#=>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]


なんだか、車輪の再発明みたいになってしまったが、今回仕組みは理解出来たので良しとしておこうか。