Happy FizzBuzz!!

今年はこのあいさつを流行らせていきたいと思います。
残り少ないですがよろしくお願いします。

この記事はリブセンスアドベントカレンダー2016 18日目 A面です。
B面 Amazon PollyでHappy FizzBuzzオーディオライフ
C面 oF製ビジュアライザでHappy FizzBuzzビジュアライズライフ
もあわせてご覧ください。

無限FizzBuzzリスト

さて、みなさんはプログラムの中で

長さ不定のFizzBuzzリストが必要になり
しかし実際に評価されるかは定かでなく
メモリに乗っけておきたくない

ということが多々ありますよね。

そう、そんなときに役立つのが遅延評価の無限FizzBuzzリストです。

Rubyで実装してみる

さっそくお手持ちのRuby(>2.0)で実装してみましょう。

fb = Array.new(1).cycle.lazy.zip((Array.new(2) << "Fizz").cycle, (Array.new(4) << "Buzz").cycle).with_index(1).map { |s, i| s.join.gsub(/^$/, i.to_s) }

なんと簡潔にできました！

クラスとサイズを見てみると

irb(main):006:0> fb.class
=> Enumerator::Lazy
irb(main):007:0> fb.size
=> Infinity

きちんと遅延評価の無限リストになっています。

実行すると

irb(main):019:0> fb.take(15).map(&:to_s).to_a.join(" ")
=> "1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz"

みごとFizzBuzzがあらわれました。

コード

さきほどコード、改行を入れて見やすくするとこうなります。

fb = Array.new(1).cycle.lazy.zip(
  (Array.new(2) << "Fizz").cycle,
  (Array.new(4) << "Buzz").cycle
).with_index(1).map { |s, i| s.join.gsub(/^$/, i.to_s) }

まずは一行目。
Array.newは引数Nを渡すとサイズNのnil配列ができあがるので、
Array.new(1)は[nil] となります。
これをcycleすると無限nil配列ができあがります。

ただしこれにzipをかけると永遠に処理が終わらないので、
lazyを挟むことによってEnumerator::Lazyに変換します。

あとは同じように作った無限Fizz配列、無限Buzz配列をzipし、
インデックスを付与してmapします。
map内が少し見苦しいのですが、文字列連結した後、空のときはインデックスに変換。
つまりFizzでもBuzzでもないときは数字が表示される、というわけです。

使用メモリ

もちろん気になるのはメモリですよね。
今回はObjectSpaceを使って計測してみます。

まずはふつうにFizzBuzz配列(サイズ100万)をつくった場合。

irb(main):003:0> fb = []
=> []
irb(main):004:0> (1..1000000).each do |i|
irb(main):005:1*   s = ''
irb(main):006:1>   s << 'Fizz' if i % 3 == 0
irb(main):007:1>   s << 'Buzz' if i % 5 == 0
irb(main):008:1>   fb << (s == '' ? i.to_s : s)
irb(main):009:1> end
=> 1..1000000
irb(main):010:0> ObjectSpace.memsize_of(fb)
=> 11636272

とんでもないメモリ使用量ですね。

次に無限FizzBuzzリストの場合です。

irb(main):012:0* lazy_fb = Array.new(1).cycle.lazy.zip((Array.new(2) << "Fizz").cycle, (Array.new(4) << "Buzz").cycle).with_index(1).map { |ss, i| ss.join.gsub(/^$/, i.to_s) }.take(1000000)
=> #<Enumerator::Lazy: #<Enumerator::Lazy: #<Enumerator::Lazy: #<Enumerator::Lazy: #<Enumerator::Lazy: #<Enumerator: [nil]:cycle>>:zip(#<Enumerator: [nil, nil, "Fizz"]:cycle>, #<Enumerator: [nil, nil, nil, nil, "Buzz"]:cycle>)>:with_index(1)>:map>:take(1000000)>
irb(main):013:0> ObjectSpace.memsize_of(lazy_fb)
=> 272

もちろんO(1)です。すばらしい。

まあ評価遅いとかそもそもランダムアクセスのスピード違うから配列と比べてもアレだとか色々難癖はありますが、冒頭に書いたような状況にはピッタリの代物かと思います。

みなさまも、遅延評価の無限FizzBuzzリストを使って、
HappyなFizzBuzzライフをお送りください。