Ruby
FizzBuzz
遅延評価
LivesenseDay 18

無限FizzBuzzリストでHappy FizzBuzzライフ

More than 1 year has passed since last update.


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ライフをお送りください。