Line 1: Error: Invalid Blog('by Esehara' )

または私は如何にして心配するのを止めてバグを愛するようになったか

>> Zanmemo

あと何かあれは 「esehara あっと じーめーる」 か @esehara まで

最遅FizzBuzz研究報告: 全出力まで3秒も時間がかかるFizzBuzzを書いてみよう

近況

f:id:nisemono_san:20150402015134p:plain

はじめに

さて、おそらくエンジニアの皆さんでしたら、如何に最速・最適化されたアルゴリズムを書くことに興味があるかと思われます。しかし、過去にもバブルソートよりも非効率なソートアルゴリズムを探して ―― ストゥージソートとスローソート - Line 1: Error: Invalid Blog('by Esehara' )という記事を書きましたが、逆最適化という問題も面白くて、ここ最近FizzBuzzでも結構遅いFizzBuzzが書けたので、この場を借りて報告したいと思います。

ルール

  • いわゆるFizzBuzzの仕様は守る
  • sleepや空のwhile文、eachなど、それを取り除いても影響のないコードは使用禁止とする

ソース

def method_missing(name, *args)
  a, b, c = name.to_s.split("_")
  send(eval(b) || eval(c) ? "#{b}_#{c}" : name)
rescue SystemStackError
  a
end
def true_false; "Fizz" end
def false_true; "Buzz" end
def true_true; "FizzBuzz" end
(1..100).each { |x| puts send("#{x}_#{x % 3 == 0}_#{x % 5 == 0}") }

実測

real 0m8.967s
user 0m4.124s
sys  0m0.049s

ポイント

まず、method_missingがトップレベルで宣言できることは過去の記事でも書いた通りです。今回もこれを利用します。

ここで一つ疑問があります。もしmethod_missingの中で、定義されていないメソッドを呼び出した場合はどうなるか? 答えは明確で、これをmethod_missingで補足してしまいます!

そこで、基本的にはFizz, Buzz, FizzBuzzを出力するだけのメソッドを定義してあげることにします。そうすると、例えば#{x % 3 == 0}_#{x % 5 == 0}というコードにした場合、false_falseというメソッドを呼び出そうとするのですが、当然存在しません。したがって、このfalse_falsemethod_missingで補足し……といった、循環構造が完成します。

もしかしたら不正確ではない説明かもしれませんが、メソッドを呼び出すごとに、元のメソッドの呼び出しを一回スタックしていきます。そして、そのスタックの積み上げ限界が来ると、スタックオーバーフローとなり、エラーとなってしまいます。RubyだとSystemStackErrorですね。これを補足することで、つまりFizzにもBuzzにもFizzBuzzにも該当しないものであったということがわかります。

さて、さらにもっと疑問が生じます。

"#{x}_#{x % 3 == 0}_#{x % 5 == 0}"となっている部分なのですが、なぜわざわざ元の数字を埋め込み、method_missing先でパースしているのでしょうか。"#{x % 3 == 0}_#{x % 5 == 0}"ではダメなのでしょうか?

問題は、「どのようにして元の数字を取得するか」ということです。例えば、上のように書き直したコードを見てみましょう:

def method_missing(name, *args)
  send name
rescue SystemStackError
  @counter.to_s
end
def true_false; "Fizz" end
def false_true; "Buzz" end
def true_true; "FizzBuzz" end
(1..100).each do |x| 
  @counter = x
  puts send("#{x % 3 == 0}_#{x % 5 == 0}")
end

問題は、each内のブロックと、method_missing内の変数のスコープが違うために、何らかの外部参照が必要となってきます。この場合はトップレベルにインスタンス変数を使っていますが、これはとても気持ちが悪いですね。もっと他の方法はないのでしょうか。どうせだったらclassにしてしまえばいいのでは、ということで全部まとめてclassにしてしまいます。   

class StackFizzBuzz
  def true_false; "Fizz" end
  def false_true; "Buzz" end
  def true_true; "FizzBuzz" end

  def method_missing(name, *args)
    send name
  rescue SystemStackError
    @x
  end

  def main
    (1..100).each do |x|
      @x = x
      puts send("#{x % 3 == 0}_#{x % 5 == 0}")
    end
  end
end
StackFizzBuzz.new.main

 逆に普通な感じがしないこともないですね。ただ、このおかげでmethod_missingがトップレベルを汚染することがなくなるので、安心して実装できるというメリットがあることは確かです。  

考察

  さて、ここで気になることが一つあります。スタックを全部食いつぶせば、そりゃ必然的に遅くなるだろうという目論見で実装をしていたのですが、実際に調べたところ、最初のコードよりも幾分他のコードのほうが早いのです。どうも、スタックを食いつぶしていても、そんなに遅くないのではないかと思い、標準ライブラリであるところのprofilerで調べたところ:

最初のコード

 

   %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 73.37     4.05      4.05    36370     0.11   698.78  Object#method_missing
 17.21     5.00      0.95    72737     0.01     0.01  Kernel#eval
  5.80     5.32      0.32    36370     0.01     0.01  Symbol#to_s
  3.62     5.52      0.20    36370     0.01     0.01  String#split

次のコード

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 99.31     1.43      1.43    43640     0.03   186.23  Object#method_missing
  0.69     1.44      0.01       20     0.50     0.50  IO#write
  0.00     1.44      0.00       10     0.00     1.00  IO#puts

何が起きていたか

要するにevalとかなんやらでパースしたりしていたのが、意図せず遅くなっていた理由だったようです。つまり、気が付いたら本当に非効率的なコードになっていたということです。これは思わぬ誤算ですね。

 まとめ

というわけで、今回は遅いFizzBuzzについて書いてみました。このように、如何にして遅いFizzBuzzを書くかということは、如何にして高速なFizzBuzzを書く、というよりも手軽で頭を使うなあ、ということが実感として得られたので、興味ある方、また「こんな方法あるぞ!」という方は、ぜひ挑戦してみるといいかもしれません。