Ruby

2012年4月16日 (月)

素数日を求める

最近、自発的にコードを書くことがないなぁ…。

ということで今回も人様のブログのネタからです。何やら「素数日」を求めるらしい。
詳しい説明はこちらを見ていただくことにして…。

 

今回は「Date クラス」を使って実際の日付を出し、それを「yyyymmdd」の形の整数に変換した後に、その数が素数かどうかを調べました。

# -*- coding: utf-8 -*-
#
# 素数日を求める
#

require 'date'


class Integer
  def prime?
    return true  if self == 2 || self == 3
    return false if self.even? || self % 3 == 0 || self <= 1

    limit = (self ** 0.5).to_i
    i = 5
    add = 2
    while limit >= i
      return false if self % i == 0
      i = i + add
      add = 6 - add
    end
    return true
  end
end

d1 = Date.new(2012,  1,  1)     # 開始日
d2 = Date.new(2020, 12, 31)     # 終了日

arr = []
d1.upto(d2) do |d|
  n = d.year * 10000 + d.month * 100 + d.day
  arr.push(d) if n.prime?
end

puts arr.map{|d| d.to_s}
# puts arr.size

このコードは Ruby のみで書かれていますが、「intel Core i5, 2.4GHz」の環境で「2012年1月1日〜2020年12月31日」の期間に存在する素数日を、約0.03秒ですべて求めることができました。

 

 

追記 (2012/04/17) :Ruby1.9 の標準添付ライブラリである「Prime」と Range#select メソッ ドを使ったコードも書いてみました。
こっちの方がすっきりしてていいのかな?

# -*- coding: utf-8 -*-
#
# 素数日を求める
#

require 'date'
require 'prime'

d1 = Date.new(2012,  1,  1)     # 開始日
d2 = Date.new(2020, 12, 31)     # 終了日

arr = (d1 .. d2).select{|d| (d.year * 10000 + d.month * 100 + d.day).prime?}
puts arr.map{|d| d.to_s}
# puts arr.size

HTML generated by org-mode 6.33x in emacs 23

2011年1月 3日 (月)

FizzBuzz 再び : Integer#times の落とし穴

 昨日、「fizzbuzz問題」関係のブログをいくつか見ていたら、Ruby 初心者さん(プログラミング初心者さん)がたまにハマる勘違いを見つけちゃいました。(「fizzbuzz問題」に関してはこちらを参照のこと。普通は 1 〜 100 までの範囲を表示させることが多いですね)

 問題の記事はこちらです。コードを引用してみます(読み易いようにインデントさせました)

100.times{|n| if n % 15 == 0 puts "fizzbuzz" elsif n % 3 == 0 puts "fizz " elsif n % 5 == 0 puts "buzz " else puts "#{n}" end }
 実際にこのコードを走らせると次のようになります。
>ruby test.rb ruby test.rb fizzbuzz 1 2 fizz 4 buzz fizz < 中略 > 94 buzz fizz 97 98 fizz
 皆さんは間違いに気付きましたか?

 この記事を書いた方は「1 〜 100」までの範囲を表示させるつもりで 100.times{|n| .. } と書いています。ところがこう書くと「0 〜 99」までの整数が小さいほうから順に n に代入されていきます。つまり、「100回数える」んだけど、始まりは「0」からなんですね。
 そのため 1 の前に fizzbuzz が表示され、本当は最後に表示されるべき buzz が表示されていません。

 Ruby の Integer#times に限らず、プログラミング言語には「0」から始まるものがたくさんあります。例えば Ruby や C 言語の配列のインデックスや Scheme や Haskell のリストのインデックスも「0」から始まります。
 普通、物を数える時は「1」から数え始めますよね。ところが「0」から数え始めたほうがコンピュータには都合がいいらしいんですね。

 ではこの問題では Integer#times は使えないかというと、そうではありません。ちょっと工夫すれば題意どおりの表示ができます。(以後のコードはすべてメソッドの形にしてあります)

# Integer#times 修正版 def fizzbuzz1 100.times do |m| n = m + 1 if n % 15 == 0 puts "fizzbuzz" elsif n % 3 == 0 puts "fizz " elsif n % 5 == 0 puts "buzz " else puts "#{n}" end end end

 ただ、今回のような場合には Integer#times よりも、開始点と終了点が明示できる Integer#upto を使ったほうが分かり易いと思ます。(elsif を並べるのが好きではないので case を使いました)

# Integer#upto を使う def fizzbuzz2 1.upto(100) do |n| case when n % 15 == 0 puts "fizzbuzz" when n % 3 == 0 puts "fizz" when n % 5 == 0 puts "buzz" else puts n end end end

 さて、話はここで終ってもいいのですが、Ruby には「多様性は善」という言葉もありますから、他の方法も考えてみました。ネットで探せばもっとたくさんの方法が見付かると思います。

# while を使う def fizzbuzz3 n = 1 while (n <= 100) case when n % 15 == 0 puts "fizzbuzz" when n % 3 == 0 puts "fizz" when n % 5 == 0 puts "buzz" else puts n end n += 1 end end # Range#each を使う def fizzbuzz4 (1..100).each do |n| case when n % 15 == 0 puts "fizzbuzz" when n % 3 == 0 puts "fizz" when n % 5 == 0 puts "buzz" else puts n end end end # Range#map を使う def fizzbuzz5 arr = (1 .. 100).map do |n| case when n % 15 == 0 "fizzbuzz" when n % 3 == 0 "fizz" when n % 5 == 0 "buzz" else n end end puts arr end # 剰余演算子を使わない 1 def fizzbuzz6 fizz = ["", "", "fizz"].cycle.take(100) buzz = ["", "", "", "", "buzz"].cycle.take(100) (1 .. 100).zip(fizz, buzz) do |a, b, c| if b == "" && c == "" puts a else puts b + c end end end # 剰余演算子を使わない 2 def fizzbuzz7 nums = (0 .. 100).to_a a = [[3, "Fizz"], [5, "Buzz"], [15, "FizzBuzz"]] a.each{|arr| 0.step(100, arr[0]){|i| nums[i] = arr[1]}} puts nums.drop(1) end

※なお、すべてのコードは Ruby 1.9 を対象に書いてあります。Ruby 1.8 では動かないものがあるかもしれません。

2010年8月 1日 (日)

Ruby の「メソッド」と Python の「関数」の違いは…

 Ruby と Python はどちらも「オブジェクト指向言語」として認識されていると思いますが、違う言語ですから当然文法や言語仕様はそれぞれ独自のものを持っています。そのため、 Python の知識で Ruby を理解しようとすると、ちょっとした誤解を招くことがあります(その逆もまた然り)。

 私がこの記事を書こうと思ったきっかけは、こちらブログでのやりとりでした。
 西尾さんが「引数のない関数呼び出しに括弧がいらない、かつ関数がファーストクラスの言語」の例として Ruby を挙げていらしたので、「それはちょっと違うのでは…」と思い、「ツムジ」の名前でコメントを書いたのですが、どうもうまく誤解を解くことができないようでした。
 以前も同じような記事を書いたことがあったのですが、「同じような勘違いをされている人が結構いるのかも?」と思ったので、自分なりにまとめてみようと思ったのでした。
 私は Ruby との付き合いは結構長いので、 Ruby に関してはある程度知っているつもりです。ところが、 Python に関しては表面をちょっとなぞった程度の知識しかありません。以下の記事の内容で、もし Python に関して間違ったことを書いていた場合は、コメント欄にその旨をご指摘いただけるとありがたいです。

 Python は「オブジェクト指向言語」であると同時に「関数型言語」の要素も持っている(マルチパラダイムってやつですね)ので、「関数オブジェクト」が存在しています。そのため Python では「関数」はファーストクラスになります。
 ところが Ruby はパラダイムとしては「オブジェクト指向」しか持っていません。そのため Ruby には「関数」は存在しません。
 Ruby で Python の「関数」に相当するのは「メソッド」ですが、 言語仕様上 Ruby の「通常のメソッド」はクラス、インスタンス、またはモジュールのいずれかに所属することになっています。そして Ruby における「オブジェクト」は「データ+メソッド」の形をとります。つまり「通常のメソッド」単独では「オブジェクト」として扱われないのでファーストクラスではありません。
 レシーバを指定せずに使える「puts」や「print」などは一見関数のように見えますが、実は「Kernel クラス」のメソッドです。またトップレベルで定義したメソッドもレシーバを指定せずに使えますが、こちらは「Object クラス」のプライベートメソッドとして扱われます。
 西尾さんはこちらブログのコメントに

オブジェクト指向であるかどうかとメソッドや関数がファーストクラスであるかどうかは背反ではなく…
と書いておられますが、「背反する・しない」ではなく Ruby では言語仕様上「通常のメソッド」は単独で「オブジェクト」として扱われないのです。

 また西尾さんは同じくコメントの中で

>> bar = Object.method(:foo) => #<Method: Class(Object)#foo> このメソッドオブジェクトはファーストクラスであるように見えますが、そうではないという主張でしょうか?
と書いておられます。
 これに関しては Ruby マニュアルのclass Methodの項目に
Object#method によりオブジェクト化されたメソッドオブジェクトのクラスです。
と書いてあります。これは「通常のメソッド」が単独では「オブジェクト」になれないので、わざわざ「Object#method」を使って「メソッドをオブジェクト化」するということです。
 ですから、 Ruby に関しては
引数のない関数呼び出しに括弧がいらない、かつ関数がファーストクラスの言語では、逆に「その関数自体」を意味する式をつくるために新しい文法が必要になる。
のではなく、
「メソッド」がもともとファーストクラスではないので、「メソッド」をファーストクラスとして扱うためには「Object#method」や「Method#call」といったものが必要になった。
ということなのです。

2010年4月29日 (木)

人のブログの間違いが気になって……

 基本的に、ほかの人のブログの内容に口を出すのは好きじゃないんですが、どうしても気になることがあるので……。

 

 先日、Ruby に関するこんな記事を見かけました。

Rubyでは、すべてがオブジェクト。じゃないよ!

 この記事を書いた人は、Ruby の根本的なところで勘違いをしているようです。
 ある程度 Ruby や「オブジェクト指向プログラミング」について知識にある人ならすぐに分かる間違いなので、「そのままスルーしてもいいかな?」とも思ったのですが、もし Ruby のことをよく知らない人が読んだら混乱するのではないかと心配になったので、この記事を書くことにしました。

 問題の記事では、冒頭にこんなことが書いてあります。

 Rubyでは、すべてがオブジェクト。と説明される場合があります。確かに、「1」も「+」もクラス自体もすべてオブジェクトです。ですが、「ほぼ」すべてがオブジェクトであって、すべてではないんです。
 例をひとつ。ブロックはオブジェクトではありません。
 確かに Ruby では「すべてがオブジェクトである」と表現されることがあります。しかしこの場合の「すべて」は「すべてのデータ(例えば、文字列、配列など)」という意味になります。
 Ruby には「オブジェクト」以外に「オブジェクト」に属する「メソッド(例えば、 Array#size など)」や「制御構造(例えば、 if や while など)」なども含まれます。そして、一部のメソッド(%, + など)や制御構造(and, or など)は、「演算子」の形をとっています。
 上の文章の例で言えば、「1」はオブジェクトですが、「+」はメソッドです。また「ブロック」は制御構造ということになります。

 さらに記事の最後には

 このように、ブロックはオブジェクトではありません。他にRubyでもオブジェクトでないものに、「and」や「or」、「&&」や「||」などがあります。演算子が特別なのは当たり前だろと思う人は、LISPを調べてみると面白いかもしれません。
といった文章が書いてあります。
 すでに書いたように「ブロック」は制御構造です。「and」、「or」、「&&」、「||」も制御構造です。
 それから、LISP が引き合いに出されていますが、文章の流れからすると「LISP の演算子はすべて手続きである」といったことを表現したかったのでしょうか?
 確かに LISP ほとんどの演算子は手続きといっていいのですが、「and」や「or」など一部の演算子は、引数の評価を通常の手続きと同じようにしてしまうと異常事態に陥る可能性があるため、通常の手続きとは引数の評価のタイミングが違うマクロとして実装されているのが普通です。

 インターネット上のホームページやブログを見ていくと、簡単にいろいろな情報を手に入れることができます。しかし、中には不正確だったり、間違った情報もたくさんあります。
 正しい情報のみをふるい分けるのはなかなか難しいですけどね……。いろいろな記事を見比べたり、人に話を聞いたり、正しい情報を得るにはそれなりに努力が必要ってことでしょうか……。
 かくゆう私のブログの記事も、「思い込み」や「勘違い」で間違った情報を書いている可能性は十分にあります。記事の内容をあんまり鵜呑みにしないほうがいいかも……。

2010年2月 1日 (月)

既約分数クイズ、ファレイ数列、フォードの円

 こちらのブログ「既約分数クイズ」の存在を知りました。

 ちょっと面白そうだったので、Haskell でコードを書いてみました。答えは (分子, 分母) の組がリストの形で出てきます。

irreducibleFraction :: Int -> [(Int, Int)] irreducibleFraction n = [(p, q) | q <- [1 .. n], p <- [0 .. q], gcd p q == 1]
*Main> irreducibleFraction 4 [(0,1),(1,1),(1,2),(1,3),(2,3),(1,4),(3,4)]
 Haskell では条件を書くだけで、何の工夫もせずに答えが出てしまいました。

 「他の解法はないものか?」と調べていたら、既約分数に関連して「ファレイ数列」というものがあることが分かりました。これは既約分数が大きさの順に並んでいるものです。
 そこで、先ほどの関数を使って「ファレイ数列」を作ってみることにしました。ついでにより分数らしく見えるようにしてみました。

import Ratio import Data.List irreducibleFraction :: Int -> [(Int, Int)] irreducibleFraction n = [(p, q) | q <- [1 .. n], p <- [0 .. q], gcd p q == 1] farey :: Int -> [(Int, Int)] farey n = sortBy comp (irreducibleFraction n) where comp (p1, q1) (p2, q2) = compare (p1 % q1) (p2 % q2) fareyToStr :: [(Int, Int)] -> String fareyToStr ns = init $ concat $ map toStr ns where toStr (a, b) = show a ++ "/" ++ show b ++ " "
*Main> fareyToStr $ farey 4 "0/1 1/4 1/3 1/2 2/3 3/4 1/1"
 さらに調べると、「ファレイ数列」には「中関数」を使って求める方法があるようなので、自分でも考えて見ました。
farey2 :: Int -> [(Int, Int)] farey2 n = farey' [(0, 1), (1, 1)] where farey' ((x1, y1) : xs@((x2, y2) : _)) | y1 + y2 > n = (x1, y1) : farey' xs | otherwise = farey' ((x1, y1) : (x1 + x2, y1 + y2) : xs) farey' xs = xs
*Main> fareyToStr $ farey2 4 "0/1 1/4 1/3 1/2 2/3 3/4 1/1"

 

 ところで Wikipedia の「ファレイ数列」の項には「フォードの円」という図が載っています。
 「これって、自作の "Turtle Graphics on Ruby/SDL" で描けるかな?」ということでコードを書いてみました。

# -*- coding: utf-8 -*- require 'turtle_graphics' # # == ファレイ数列 # def farey(n) q_arr = (1 .. n).to_a p_arr = Array.new f_arr = Array.new farey = q_arr.each do |q| p_arr = (0 .. q).to_a f_arr.push(p_arr.map {|p| [p, q]}) end f_arr = f_arr.flatten(1).select{|p, q| p.gcd(q) == 1} return f_arr.sort_by{|p, q| p / q.to_f} return end # # == フォードの円を描く # class Screen def ford_circle(p, q, c) q = q.to_f r = 1 / (2 * q * q) draw_circle(p / q, r, r, c).update # draw_circle(p / q, 1 - r, r, c).update end end sc = Screen.create(600, 600) sc.set_range(0, 1, 0, 1) # 描画範囲 (x_min, x_max, y_min, y_max) farey(10).each do |p, q| sc.ford_circle(p, q, White) end sc.main_loop

Screenshotturtle_graphics_on_rubysd

 Wikipedia には F5 の図が載っていますが、今回のコードでは F10 の図を描いてみました。
 当然、コードを書き換えれば F50 だろうが F100 だろうが表示してくれます(相当時間がかかると思われますが……)
 また、描画範囲を書き換えて拡大表示させれば、小さい円もそれぞれしっかり他の円に接しているのがわかります。
 ただし、あまり大きく拡大表示すると、0/1 の円と 1/1 の円の表示が乱れるようです。これは "turtle_graphics.rb" の "Screen#draw_circle" 内で使用している、"draw_aa_circle" というメソッドの問題のようです。この部分を "draw_circle" に書き換えれば、どんなに拡大しても表示は乱れないと思われます。

2009年9月16日 (水)

Project Euler - Problem 61 : 0.06s (Ruby 1.9)

問題はこちらをご覧ください。


まずはコードから……

# -*- coding: utf-8 -*- class Integer def triangle # 三角数 return (self + 1) * self / 2 end def square # 四角数 return self * self end def pentagon # 五角数 return (3 * self * self - self) / 2 end def hexagon # 六角数 return 2 * self * self - self end def heptagon # 七角数 return self * (5 * self - 3) / 2 end def octagon # 八画数 return self * (3 * self - 2) end end def search_ans(arr) arr.each do |flag, old_arr| if old_arr.size == 7 return unless old_arr.first == old_arr.last ans = Array.new 6.times{|i| ans.push(old_arr[i] * 100 + old_arr[i + 1])} print "#{ans.inject(:+)} : #{ans}\n" exit else new_arr = make_new_arr(flag, old_arr) search_ans(new_arr) end end end def make_new_arr(flag, arr) ans = Array.new flag.each_with_index do |bool, i| next if bool vals = $poly_num[i][arr.last] next unless vals vals.each do |n| new_flag = Array.new(flag) new_flag[i] = true ans.push([new_flag, arr + [n]]) end end return ans end func = [lambda{|x| x.octagon }, lambda{|x| x.heptagon}, lambda{|x| x.hexagon }, lambda{|x| x.pentagon}, lambda{|x| x.square }, lambda{|x| x.triangle}] $poly_num = Array.new 6.times do |i| $poly_num[i] = Hash.new 1.upto(1/0.0) do |j| n = func[i].call(j) break if n > 9999 next if n < 1000 key, val = n.divmod(100) $poly_num[i][key] = Array.new unless $poly_num[i][key] $poly_num[i][key].push(val) if val > 9 end end # $poly_num : [{10=>[45], 11=>[60], 12=>[81], 14=>[], ...}, # {10=>[71], 11=>[77], 12=>[88], 14=>[], ...}, # {10=>[35], 11=>[28], 12=>[25], 13=>[26], ...}, # {10=>[80], 11=>[62], 12=>[47], 13=>[35], ...}, # {10=>[24, 89], 11=>[56], 12=>[25, 96], ...}, # {10=>[35, 81], 11=>[28, 76], 12=>[25, 75], ...}] $poly_num[0].each do |key, vals| flag = [true] + Array.new(5, nil) arr = Array.new vals.each{|n| arr.push([Array.new(flag), [key, n]])} search_ans(arr) end

今回はちょっと込み入ったデータを扱うことになってしまいました。

"$poly_num" は 6 個の要素を持つ配列になっています。

それぞれの要素には 4 桁の八角数、七角数、六角数、五角数、四角数、三角数が、上位 2 桁をキーにして下位 2 桁を値にしたハッシュテーブルの形で入っています。

このデータ構造を作るために、"Integer#octagon", "Integer#heptagon" といった一部のメソッドが違うだけで他は同じような処理を書くのが嫌だったので、lambda を使ってメソッドを含むブロックを proc 化したうえで高階関数のような処理をしてみました。

そして、この "poly_num" のデータを使って答えとなる数の組み合わせを探しました。

実際には要素の数が一番少ない八画数のキーから値を取り出し、その値がキーとなるような数字が他の多角数の中にあるかを調べていきました。さらにその値が他の多角数につながるかを調べていって、最終的な答えを導き出しました。

その際に同じ多角数に属する数字を重複して選ばないように、選んだ多角数は "true" 、選ばれていない多角数は "nil" としたフラグを一緒にデータで持たせました。

今回も Problem 60 と同様に、初めは同じような処理が入れ子になったのですが、再帰的な処理にまとめることが出来ました。

データの構造を工夫したのが良かったのか、Ruby 1.9 で約 0.06 秒で答えが出ました。

2009年9月15日 (火)

Project Euler - Problem 60 : 私のこだわり

問題はこちらをご覧ください。


私には、Project Euler の問題を解くに当たって、こだわっていることがあります。それは「探索範囲の決め方」です。

問題文の中に探索範囲が明示されていない場合、数学的な考察で探索範囲を絞り込めない場合、探索範囲を設定せずに解けるようなアルゴリズムを考えるようにしています。

この問題も、その方針に従って、探索範囲の上限を決めずに答えを求められるような解き方を考えました。

そのため、答えが出るまで Ruby 1.9 で 30 秒近くかかってしまいました。


ネットで探してみると、結構多くの人が適当に上限を決めた上でこの問題を解いていました。

探索範囲を勝手に決めることで、かなり速く答えが出るものありましたが、そういった解き方に限って、最初の探索範囲の設定を変えると答えが出なかったり、間違った答えが出るものが多いようでした。

「試行錯誤をしながら探索範囲を決めていく」というやり方も間違いではないのでしょうが、私はそういった解き方が嫌いなので、今回はこの解法で良としました。


require 'prime' require 'math_tool' def concat_prime?(s1, s2) return ((s1 + s2).to_i.prime? and (s2 + s1).to_i.prime?) end def find_chain(arr, rest) if rest.size == 5 ans = rest.map{|i| i.to_i} print "#{ans.inject(:+)} : #{ans}\n" exit else arr.each do |i| arr1 = arr & $primes[i] find_chain(arr1, rest + [i]) end end end $primes = Hash.new Prime.each do |n| n_str = n.to_s arr = Array.new $primes.each do |key, val| arr.unshift(key) if concat_prime?(n_str, key) end if arr.size >= 4 find_chain(arr, [n_str]) end $primes[n_str] = arr end

少しだけコードの解説を……。

素数を小さい順に求めていって、その素数を「キー」にした $primes とうハッシュテーブルを作ります。(後の処理を考えて、すべて文字列にしてあります)

それぞれの「キー」には、「キー」の数字未満の素数で「キー」の数字と連結して別の素数を生成することができる素数の集合が「値」として関連付けられています。

例えば、

{"2"=>[],"3"=>[],"5"=>[],"7"=>["3"],... "109"=>["7", "3"],...}

といった具合です。

ここで「キー」が "109" の場合に注目してもらうと、その「値」は ["7", "3"] となっています。そして「キー」が "7" の時の「値」は ["3"] となっています。

これをみて分かるとおり、ある「キー」の「値」の中の数字を「キー」としてみた場合、それぞれの「値」に同じ数字が含まれていた場合、その数字はそれぞれの「キー」の数字と連結して別の素数を生成できます。

そこで、ある「キー」の「値」が 4 個以上になった場合、その「値」に含まれる数字が「キー」となる値をチェックしていくことによって、この問題の条件に合う数字が見つけられます。


最初に考えたコードでは、同じようなループが入れ子状態になっていて、不格好だったのですが、頑張って "find_chain" という再帰的な処理にすることが出来ました。これでコード自体がすっきりしたと思います。

2009年9月 4日 (金)

"Python + Psyco" vs "Ruby 1.9" ??

今日、「Python+Psycoが速い」という記事をを見つけました。

なにやら素数列を生成する速度をいろんな言語で比べているのですが、 "Python + Psyco" というのが爆速らしい。

自分は Ruby 使いなので Python のことは詳しくはないのですが、興味があったので自分の環境でも確かめてみました。

試したコードは上記の記事に乗っていたものをコピーして使用しました。上限は記事と同じ "10000000" にしました。

結果は……確かに "Psyco" は速かった。

Python + Psyco : 0m19.395s Python : 2m54.042s Ruby 1.9 : 2m2.096s

でもね…… Ruby には Ruby なりのやり方があるのですよ。

同じ結果を求めるだけなら、添付ライブラリの "prime.rb" を使うととても速くなります。

# prime_test1.rb require 'prime' primes = Prime.each(ARGV[0].to_i).to_a
$ time ruby prime_test1.rb 10000000 real 0m29.568s user 0m29.230s sys 0m0.108s

これだったら "Python + Psyco" の結果と遜色無いのでは?


さらに、自作の "math_tool.rb" に含まれている "prime_list" メソッドを使えば、もっと速く同じ結果が出せます。

"prime_list" は「エラトステネスの篩」の原理を使っているので、メモリは少々使いますが、探索する上限が決まっていればかなり高速に結果が出ます。

# prime_test2.rb def prime_list(n) return [] if n < 2 return [2] if n == 2 limit = (n ** 0.5).to_i arr = (1 .. n).step(2).to_a arr[0] = 2 len = arr.size i = 0 while true i = i + 1 j = arr[i] next unless j break if j > limit k = 2 * i * (i + 1) while k <= len arr[k] = nil k = k + j end end arr.compact! return arr end primes = prime_list(ARGV[0].to_i)
$ time ruby prime_test2.rb 10000000 real 0m3.153s user 0m3.084s sys 0m0.024s

なんと "Python + Psyco" の 6 〜 7 倍の速さです。


で、結局何が言いたいかというと…… Python が羨ましい……ではなくて、やり方次第で少々のスピードの遅さはカバーできる事もあるということです(ちょっと、負け惜しみも含まれていますが……)。

Ruby は直感的なコードが書きやすいので、コードを書くのがそんなに負担になりません。そこでいろいろなアルゴリズムのコードを試しに書いてみて、検討しやすいと思います。

もともと速ければ、あまりアルゴリズムにこだわらずに、そこそこのコードで満足してしまうかもしれません。でも、私はアルゴリズムにこだわって行きたいと思っています。


追記(2009/09/08) : prime_list にちょっとしたバグを発見したため、修正しました。

2009年9月 3日 (木)

平方根の求め方

みずぴーさんのブログを見ていたら、面白い記事を見つけました。

"奇数を順に引いていくだけで平方根が求められる" というのです。


リンクをたどって行って、『平方根の求め方』というホームページにたどり着きました。

なんでも、歯車式の計算機で平方根を求める方法らしいです。

ホームページの説明をよく見てみると……平方数の考え方を使って平方根を求めているのですね。こんな方法を考えつくなんてすごいです。(ホームページの説明は正方形の面積を使って平方数をイメージできるようになっていて、非常にわかりやすかったです)


面白そうだったので、早速 Ruby でコードを書いてみました。

# -*- coding: utf-8 -*- # # = root.rb # # from 『平方根の求めかた』 (http://www.wizforest.com/gear/tiger/sqrt/) # class Numeric # call-seq: # n.root -> float # # * n の平方根を返す。 # # === Example # 2.root #=> 1.4142135623731 # def root n = self d1 = 0 # 整数部が 2 桁以下になるように繰り下げる。 n, d1 = n / 100.0, d1 - 1 while n >= 100 # 整数部が 1 桁以上になるように繰り上げる。 n, d1 = n * 100.0, d1 + 1 while n < 1 ans = 0 odd = 1 # 引いていく奇数 0.upto(1/0.0) do |d2| # d2 : ans の桁数 0.upto(1/0.0) do |c| if n < odd ans = ans * 10 + c break end n = n - odd odd = odd + 2 end if (d2 > 16 || n == 0) return ans / 10.0 ** (d1 + d2) end n = n * 100 odd = (odd - 1) * 10 + 1 end end end if __FILE__ == $0 n = ARGV[0].to_f puts n.root end

他のメソッドからも呼び出せるように最後の答えを float 型で返すようにしたので、有効桁数に制限がありますが、"Math#sqrt" や "** 0.5" の結果と同じ値が出せます。(ただし、float 型なので計算上の微妙な誤差が出るようで、"==" で評価すると "false" が帰ってくることはあるようです)

コードの最初の部分で桁数を調整してから計算を始めているので、かなり大きな数からかなり小さな数までしっかり計算できます。

$ ruby root.rb 2 1.4142135623731 $ ruby root.rb 3 1.73205080756888 $ ruby root.rb 12345678901234567890 3513641828.82014 $ ruby root.rb 0.00000000000000000000000123 1.10905365064094e-12

今回は float 型で値を返すようにしたため有効桁数に制限がありますが、"BigDecimal" を使えば有効桁数の制限を気にせずに計算できると思います。まあ、これは今後の課題ということで……。

 

追記 (2010/05/04) : 以前の "root.rb" が "while" を多用していて、あまり Ruby っぽくないように思えたので、"Integer#upto" を使ったコードの変えてみました。

2009年8月31日 (月)

Project Euler - Problem 59

問題はこちらをご覧ください。


面倒くさそうだったので、しばらくほったらかしにしていたのですが、「暗号解読」(サイモン・シン著)を読んだら解法のヒントがあったので、解いてみました。

「ある程度の長さをもつ普通の英文」の場合、"e" が最頻出文字であることが分かっています。

今回の暗号は 3 文字のキーワードが使われているので、暗号化された文章を三文字おきにグループ分けすると、その中のグループの頻出文字に "e" が含まれていることが予想されます。

そこで、それぞれのグループの出現頻度の高い順に 5 つの文字を拾い上げて、それが "e" だったと仮定してキーワードの文字を推測してみました。

今回は元の文字のコードをキーワードのコードと "xor" することで暗号化しているので、暗号化された文字のコードと元の文字のコードを "xor" するとキーワードのコードが返ってきます。

# -*- coding: utf-8 -*- # # = 鍵となる文字を探す # class Array # == 数字の出現頻度を数え上げて、多い順に並べて返す。 def count h = Hash.new(0) self.each do |n| h[n] = h[n] + 1 end return h.to_a.sort_by{|a| a[1]}.map{|a| a[0]}.reverse end end cipher_text = open("cipher1.txt"){|file| file.read} cipher_arr = cipher_text.split(",").map{|str| str.to_i} # text_arr を鍵の同じ文字に対応する 3 つの部分に分ける。 part = Array.new 3.times{|i| part[i] = Array.new} cipher_arr.each_with_index do |n, i| part[i % 3].push(n) end # 各パートで頻出する 5 文字を "e" に見立てて鍵の文字を推測する。 part.each do |arr| p arr.count.take(5).map{|n| (n ^ "e".ord).chr} end

今回の文章はあまり長い文章ではなかったので、さすがに "e" が最頻出とはなっていませんでしたが、それらしいキーワードを想定するだけの材料にはなりました。


それでは、キーワードが分かったところで、暗号文を復号してみましょう。

# -*- coding: utf-8 -*- # # = 暗号文を解読する # cipher_text = open("cipher1.txt"){|file| file.read} cipher_arr = cipher_text.split(",").map{|str| str.to_i} key_word = "***" # "***" の代わりに鍵となる 3 文字を入れる。 key = key_word.split("").map{|i| i.ord} arr = Array.new cipher_arr.each_with_index do |n, i| arr.push(n ^ key[i % 3]) end plain_text = arr.map{|i| i.chr}.join puts arr.inject(:+) puts plain_text

正しく復号されれば、数字と聖書の一節が英文で表示されるはずです。


ところで、今回は三つのグループのいずれでも "e" が最頻出文字となっていませんでした。

そこで、最頻出文字は何だったかを調べてみました。すると……なんと " " (半角スペース)でした。

確かに、アルファベットの中では "e" が最頻出かもしれませんが、今回のように「半角スペース」まで含めて暗号化されれば、「半角スペース」が最頻出になりますよね。もう少し良く考えれば想像できたかもしれません。


実際に問題を解いた後、他の人の解き方を調べてみたら、問題文の「平文はよく用いられる英単語を含んでいる」という部分から、暗号文の文字列が "the" や "was" などの単語に復号できる部分を探してそこからキーワードを推測している方が何人かいらっしゃいました。

それでも正解が得られているようなので、間違った解法というわけではないのでしょうが、「平文はよく用いられる英単語を含んでいる」という一文は、「単語の出現頻度は極端に偏っていない」ということを強調したかったのでは?と私は思っています。

より以前の記事一覧

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ