« 2009年8月 | トップページ | 2009年10月 »

2009年9月

2009年9月29日 (火)

source-highlight

昨日、"source-highlight" というコマンドプログラムがあるのを知りました。

早速、私のパソコン (Ubuntu) にもインストールしてみました。

"Ruby" のコードは問題なく読み込まれて、"htlm" の形で出力されました。結果は以下のとおりです。

# -*- coding: utf-8 -*-
require 'math_tool'
 
class Array
  # 配列の中から同じ要素を n 個持つグループを見つける。
  def check(n)
    return false if self.size < n
    arr = self.map{|a| [a, a.to_a.sort.to_i]}.sort_by{|a| a[1]}
    while arr.size > n
      part = arr.take_while{|a| arr[0][1] == a[1]}
      return part.map{|a| a[0]}.sort if part.size == n
      len = part.size
      arr = arr.drop(len)
    end
    return false
  end
end
 
d = 10
arr = Array.new
1.upto(1/0.0) do |i|
  num = i ** 3
  # 同じ桁の数を arr に集めていく
  if num < d
    arr.push(num)
    next
  end
  ans = arr.check(5)
  if ans
    puts ans[0]
    break
  end
  d = d * 10
  arr = [num]
end

"htlm" のソースコードはやたら長くなりますが、色がついて、ちょっとは見やすくなったかな?

2009年9月17日 (木)

Project Euler - Problem 62

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


# -*- coding: utf-8 -*- require 'math_tool' class Array # 配列の中から同じ要素を n 個持つグループを見つける。 def check(n) return false if self.size < n arr = self.map{|a| [a, a.to_a.sort.to_i]}.sort_by{|a| a[1]} while arr.size > n part = arr.take_while{|a| arr[0][1] == a[1]} return part.map{|a| a[0]}.sort if part.size == n len = part.size arr = arr.drop(len) end return false end end d = 10 arr = Array.new 1.upto(1/0.0) do |i| num = i ** 3 # 同じ桁の数を arr に集めていく if num < d arr.push(num) next end ans = arr.check(5) if ans puts ans[0] break end d = d * 10 arr = [num] end

今回は次のような戦略で問題を解いていきました。

  1. 立方数を順に求めていって、同じ桁の数だけを一つの配列にまとめる。
  2. 配列の要素を構成要素の順に並べていく。
  3. 同じ構成要素を持つ数字が 5 個あるかどうかを調べていく。

答えが出るまでの時間もそこそこ速かったので (Ruby 1.9 で約 0.4 秒)、自分では満足でした。


ところが、ネットで他の人の解法を調べていたら、次のような素晴らしい解答に出会いました。

cube = Hash.new 1.upto(1/0.0) do |i| j = i ** 3 k = j.to_s.split("").sort.join cube[k] = Array.new unless cube[k] cube[k].push(j) if cube[k].size == 5 puts cube[k][0] exit end end

ハッシュテーブルを上手に使っているので、コードがシンプルでしかも速い!!

自分ではハッシュテーブルを使うことがあまり無かったので、「いろいろなデータ構造の上手な使い方を、もっと学ばないといけない」と痛感しました。

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月 | トップページ | 2009年10月 »

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            
フォト

最近のトラックバック

無料ブログはココログ