遅刻してメイドめーるの最後の方に到着した・・・
- 「メイドめーる」メイドさんはこうやって働いている! by 大怪獣もぎゃさん
- 萌えコンテンツは大変らしい
- 遅れたから技術的な話聞き逃して残念・・・
- 整数論の問題に Ruby を活用してみる by こなみさん
- 自然数2,3,4,...,Nのいずれでも割り切れる最小の数を探す
- なんかProject Eulerの問題で見たなと思ったらproblem5と一緒だった。
- 数学ガールは萌え系本、でも先生の趣味とはちょっと違うらしい。
当時書いたソース
#1〜20の最小公倍数を求める def gcd(m, n) # m > n while true return m if n < 1 return n if m % n < 1 m = m % n n, m = m, n end end def lcm(a, b) (a * b) / gcd(a, b) end p (3..20).inject(lcm(1, 2)){|s,i|lcm(s, i)}
バイト中にGolfせずわかりやすく書いたつもりらしい。
Hash使ってないしだいぶ無駄な処理してる。
というわけで、Hash版
g=Hash.new{|h,k| m,n=k while true a=m;break if n<1 a=n;break if m%n<1 m%=n n,m=m,n end h[k]=a } l=Hash.new{|h,k| a,b=k h[k]=a*b/g[k] } p (3..20).inject(l[[1, 2]]){|s,i|l[[s, i]]}
ベンチマークとってみたらびっくり。
Mahito% ruby euler005.rb user system total real 0.010000 0.000000 0.010000 ( 0.009153) Mahito% ruby euler005.rb user system total real 0.010000 0.000000 0.010000 ( 0.009253) Mahito% ruby euler005.rb user system total real 0.010000 0.000000 0.010000 ( 0.009035) Mahito% ruby euler005_hash.rb user system total real 0.020000 0.000000 0.020000 ( 0.016634) Mahito% ruby euler005_hash.rb user system total real 0.020000 0.000000 0.020000 ( 0.016664) Mahito% ruby euler005_hash.rb user system total real 0.020000 0.000000 0.020000 ( 0.016520)
Hash使った方が遅かったりする。
ということは、Hashのヒット率が悪いのかなと思う。
試してみたらヒット率0だったのでHashは効率悪いんだな。
なんとなくlambda版も書いておく
gcd=lambda{|m,n| while true n<1?(return m):m%n<1?(return n):(m%=n;n,m=m,n) end } lcm=lambda{|a,b|(a*b)/gcd[a,b]} p (3..20).inject(lcm[1,2]){|s,i|lcm[s,i]}
ベンチマークは関数の方が若干優秀
Mahito% ruby euler005.rb user system total real 0.010000 0.000000 0.010000 ( 0.008988) Mahito% ruby euler005.rb user system total real 0.010000 0.000000 0.010000 ( 0.009042) Mahito% ruby euler005.rb user system total real 0.010000 0.000000 0.010000 ( 0.009900) Mahito% ruby euler005_lambda.rb user system total real 0.010000 0.000000 0.010000 ( 0.011326) Mahito% ruby euler005_lambda.rb user system total real 0.010000 0.000000 0.010000 ( 0.012133) Mahito% ruby euler005_lambda.rb user system total real 0.010000 0.000000 0.010000 ( 0.011654)
こうして比べる
関数>lambda>Hash
まぁ、Hashのヒット率次第ではHashが早いんだろうけどヒットしなきゃ意味がない・・・