ScalaでFizzBuzzやってみた

Scala

(４年半ほど仕事にやられてましたが何とか元気です。)

先日ひさしぶりにFizzBuzzを書く機会があったので再学習中のScalaでもやってみました。

■ 無限リストによる実装

まず、1から始まるFizzBuzzの無限リストを100まで評価する方法で実装してみました。

// 1から100までのFizzBuzz
// scalac FizzBuzz.scala
// scala FizzBuzz

object FizzBuzz extends App {
  // 数値をFizzBuzzに変換する関数
  def toFizzBuzz(n: Int): String = n match {
    case _ if n % (3*5) == 0 => "FizzBuzz"
    case _ if n %     3 == 0 => "Fizz"
    case _ if n %     5 == 0 => "Buzz"
    case _                   => n.toString
  }

  // 整数の無限リスト(n, n+1, n+2, …)の各要素に対してfを適用する関数
  // 　-> Stream((n,f(n)), (n+1,f(n+1)), (n+2,f(n+2)), ?)となる
  def mapSeqNums[T](f: Int => T, n: Int): Stream[(Int, T)] = { 
    (n, f(n)) #:: mapSeqNums(f, n+1)
  }

  // (1) 1から100までのFizzBuzzを作成
  val fizzbuzz = mapSeqNums(toFizzBuzz, 1) take 100 

  // 表示
  fizzbuzz.print
}

無限リストの実現にはストリームを利用してみました。

ストリーム (Stream) はリストに似ているが、要素は遅延評価される。そのため、ストリームは無限の長さをもつことができる。呼び出された要素のみが計算される。他の点においては、ストリームはリストと同じ性能特性をもつ。 http://docs.scala-lang.org/ja/overviews/collections/concrete-immutable-collection-classes.html

● 実行結果

実行するとこうなります。

$ scala FizzBuzz
(1,1), (2,2), (3,Fizz), (4,4), (5,Buzz), (6,Fizz), (7,7), (8,8), (9,Fizz), (10,Buzz), (11,11), (12,Fizz), (13,13), (14,14), (15,FizzBuzz), (16,16), (17,17), (18,Fizz), (19,19), (20,Buzz), (21,Fizz), (22,22), (23,23), (24,Fizz), (25,Buzz), (26,26), (27,Fizz), (28,28), (29,29), (30,FizzBuzz), (31,31), (32,32), (33,Fizz), (34,34), (35,Buzz), (36,Fizz), (37,37), (38,38), (39,Fizz), (40,Buzz), (41,41), (42,Fizz), (43,43), (44,44), (45,FizzBuzz), (46,46), (47,47), (48,Fizz), (49,49), (50,Buzz), (51,Fizz), (52,52), (53,53), (54,Fizz), (55,Buzz), (56,56), (57,Fizz), (58,58), (59,59), (60,FizzBuzz), (61,61), (62,62), (63,Fizz), (64,64), (65,Buzz), (66,Fizz), (67,67), (68,68), (69,Fizz), (70,Buzz), (71,71), (72,Fizz), (73,73), (74,74), (75,FizzBuzz), (76,76), (77,77), (78,Fizz), (79,79), (80,Buzz), (81,Fizz), (82,82), (83,83), (84,Fizz), (85,Buzz), (86,86), (87,Fizz), (88,88), (89,89), (90,FizzBuzz), (91,91), (92,92), (93,Fizz), (94,94), (95,Buzz), (96,Fizz), (97,97), (98,98), (99,Fizz), (100,Buzz), empty

● 無限ループにならない理由

コメント(1)の処理で無限ループに陥らないのはtake関数が必要とする所までしかmapSeqNums関数が評価されない為です。 式の評価順序は以下のイメージです。

f:id:nihma:20141129215526j:plain

■ 素直な実装

遅延評価による無限リストでの実装との比較のために正格評価による素直な実装もしてみました。

● Rangeによる実装

Rangeによる素直な実装はこうなりました。 最もポピュラーなやり方です。

val fizzbuzz = (1 to 100).map(n => (n, toFizzBuzz(n)))

● Listによる実装

Listによる実装にするとこうなりました。

val fizzbuzz = List.range(1, 100).map(n => (n, toFizzBuzz(n)))

● ListBufferによる実装

ListBufferでするとこうなりました。手続き的な書き方で手動による最適化です。

def range2(s: Int, e: Int): scala.collection.mutable.ListBuffer[Int] = { 
  val list = scala.collection.mutable.ListBuffer[Int]();
  var i = s 
  while (i <= e) {
    list += i
    i += 1
  }   
  list
}
val fizzbuzz = range2(1, 100).map(n => (n, toFizzBuzz(n)))

● ListBufferによる実装(fizzbuzzしながら)

ここまでの素直な実装では次の２回ループが走ってしまう問題があります。

  1. 1〜100のリストを作成する
  2. 各数値をFizzBuzzに変換する(map)

1のついでに2をすればループを１回に減らす事ができるのでやってみました。

def rangeWith[T](s: Int, e: Int, f: Int => T): scala.collection.mutable.ListBuffer[T] = {
  val list = scala.collection.mutable.ListBuffer[T]();
  var i = s
  while (i <= e) {
    list += f(i)
    i += 1
  }
  list
}
val fizzbuzz = rangeWith[(Int, String)](1, 100, n => (n, toFizzBuzz(n)))

■ 性能評価

結局どれが速いのか手元の環境で実測してみました。

機器 プロセッサ メモリ OS scala
MacBook Air 1.7 GHz Intel Core i7 8 GB 1600 MHz DDR3 OS X 10.9.4（13E28） 2.10.4

● 測定方法

1から1000000までのfizzbuzzを求めるようにして、処理を必ず評価させるため最後にListへ変換するコードを入れました。

val fizzbuzz = ...
val result = fizzbuzz.toList // force
// fizzbuzz.print

そしてtimeコマンドて実測し５回の平均を出しました。

$ time scala FizzBuzz

● 結果

無限リストによる実装

項目 1回目 2回目 3回目 4回目 5回目 平均
real(s) 3.689 3.290 3.298 3.598 3.641 3.5032
user(s) 12.088 10.745 11.136 12.122 12.504 11.719
sys(s) 0.288 0.290 0.259 0.274 0.243 0.2708

Rangeによる実装

項目 1回目 2回目 3回目 4回目 5回目 平均
real(s) 1.459 1.543 1.440 1.488 1.399 1.4658
user(s) 4.399 4.645 4.282 4.446 4.163 4.387
sys(s) 0.164 0.175 0.168 0.172 0.162 0.1682

Listによる実装

項目 1回目 2回目 3回目 4回目 5回目 平均
real(s) 2.854 2.844 2.929 3.029 2.915 2.9142
user(s) 9.459 9.455 9.780 10.188 9.638 9.704
sys(s) 0.228 0.227 0.226 0.235 0.232 0.2296

ListBufferによる実装

項目 1回目 2回目 3回目 4回目 5回目 平均
real(s) 2.358 2.360 2.313 2.962 2.362 2.471
user(s) 7.387 7.780 7.447 9.938 7.765 8.0634
sys(s) 0.221 0.199 0.206 0.216 0.201 0.2086

ListBufferによる実装(fizzbuzzしながら)

項目 1回目 2回目 3回目 4回目 5回目 平均
real(s) 1.956 1.958 2.027 1.973 1.980 1.9788
user(s) 6.261 6.164 6.493 6.312 6.291 6.3042
sys(s) 0.171 0.170 0.173 0.167 0.166 0.1694

■ 所感

  • 色々な要因(サンクコスト、CPUアーキテクチャ、コンパイラ最適化状況、toListの処理コスト、データ量etc)を考慮する必要はあると思いますが、今回の測定では無限リストによる実装は想定したほど性能が出ず、Rangeによる実装の速度が一番という結果になりました。とりあえずRangeでやっとけば問題ないような気がします。(関数を適用しながらRangeできたらさらに速くなるのかな。)
  • より低レイヤーに踏み込んだ調査も、とも考えましたがFizzBuzzですし疲れたのでしませんでした。
  • mapSeqNumsという名前はなんか違う気がします。命名センスを磨きたいです。