akiomik/suko-bench.md

## suko-bench.md

      
    Raw
  

              suko-bench.md
            
          
    概要

sukoというパズルの適当なソルバを書いたので簡単なベンチマークを取ってみた。
問題は2014/01/06のmetro紙より。
ベンチマーク方法

new scala.testing.Benchmark {
  def run() = {
    // solver here...
  }
}.runBenchmark(5)
コード

(1)基本形

for {
  s11 <- 1 to 9; s12 <- 1 to 9; s13 <- 1 to 9
  s21 <- 1 to 9; s22 <- 1 to 9; s23 <- 1 to 9
  s31 <- 1 to 9; s32 <- 1 to 9; s33 <- 1 to 9
  if s11 + s12 + s21 + s22 == 14
  if s12 + s13 + s22 + s23 == 17
  if s21 + s22 + s31 + s32 == 17
  if s22 + s23 + s32 + s33 == 21
  if s11 + s23 + s33 == 21
  if s12 + s13 + s22 == 9
  if s21 + s31 + s32 == 15
  if Seq(s11, s12, s13, s21, s22, s23, s31, s32, s33).sortWith(_ < _) == Seq(1, 2, 3, 4, 5, 6, 7, 8, 9)
} {
  println(s"${s11} ${s12} ${s13}")
  println(s"${s21} ${s22} ${s23}")
  println(s"${s31} ${s32} ${s33}")
  println("====================")
}
(2) ifを1つにまとめる

for {
  s11 <- 1 to 9; s12 <- 1 to 9; s13 <- 1 to 9
  s21 <- 1 to 9; s22 <- 1 to 9; s23 <- 1 to 9
  s31 <- 1 to 9; s32 <- 1 to 9; s33 <- 1 to 9
  if s11 + s12 + s21 + s22 == 14 &&
    s12 + s13 + s22 + s23 == 17 &&
    s21 + s22 + s31 + s32 == 17 &&
    s22 + s23 + s32 + s33 == 21 &&
    s11 + s23 + s33 == 21 &&
    s12 + s13 + s22 == 9 &&
    s21 + s31 + s32 == 15 &&
    Seq(s11, s12, s13, s21, s22, s23, s31, s32, s33).sortWith(_ < _) == Seq(1, 2, 3, 4, 5, 6, 7, 8, 9)
} {
  println(s"${s11} ${s12} ${s13}")
  println(s"${s21} ${s22} ${s23}")
  println(s"${s31} ${s32} ${s33}")
  println("====================")
}
(3) 並列コレクション化(1つ)

for {
  s11 <- (1 to 9).par; s12 <- 1 to 9; s13 <- 1 to 9
  s21 <- 1 to 9; s22 <- 1 to 9; s23 <- 1 to 9
  s31 <- 1 to 9; s32 <- 1 to 9; s33 <- 1 to 9
  if s11 + s12 + s21 + s22 == 14
  if s12 + s13 + s22 + s23 == 17
  if s21 + s22 + s31 + s32 == 17
  if s22 + s23 + s32 + s33 == 21
  if s11 + s23 + s33 == 21
  if s12 + s13 + s22 == 9
  if s21 + s31 + s32 == 15
  if Seq(s11, s12, s13, s21, s22, s23, s31, s32, s33).sortWith(_ < _) == Seq(1, 2, 3, 4, 5, 6, 7, 8, 9)
} {
  println(s"${s11} ${s12} ${s13}")
  println(s"${s21} ${s22} ${s23}")
  println(s"${s31} ${s32} ${s33}")
  println("====================")
}
(4) 並列コレクション化(2つ)

for {
  s11 <- (1 to 9).par; s12 <- (1 to 9).par; s13 <- 1 to 9
  s21 <- 1 to 9; s22 <- 1 to 9; s23 <- 1 to 9
  s31 <- 1 to 9; s32 <- 1 to 9; s33 <- 1 to 9
  if s11 + s12 + s21 + s22 == 14
  if s12 + s13 + s22 + s23 == 17
  if s21 + s22 + s31 + s32 == 17
  if s22 + s23 + s32 + s33 == 21
  if s11 + s23 + s33 == 21
  if s12 + s13 + s22 == 9
  if s21 + s31 + s32 == 15
  if Seq(s11, s12, s13, s21, s22, s23, s31, s32, s33).sortWith(_ < _) == Seq(1, 2, 3, 4, 5, 6, 7, 8, 9)
} {
  println(s"${s11} ${s12} ${s13}")
  println(s"${s21} ${s22} ${s23}")
  println(s"${s31} ${s32} ${s33}")
  println("====================")
}
(5) 並列コレクション化(全部)

for {
  s11 <- (1 to 9).par; s12 <- (1 to 9).par; s13 <- (1 to 9).par
  s21 <- (1 to 9).par; s22 <- (1 to 9).par; s23 <- (1 to 9).par
  s31 <- (1 to 9).par; s32 <- (1 to 9).par; s33 <- (1 to 9).par
  if s11 + s12 + s21 + s22 == 14
  if s12 + s13 + s22 + s23 == 17
  if s21 + s22 + s31 + s32 == 17
  if s22 + s23 + s32 + s33 == 21
  if s11 + s23 + s33 == 21
  if s12 + s13 + s22 == 9
  if s21 + s31 + s32 == 15
  if Seq(s11, s12, s13, s21, s22, s23, s31, s32, s33).sortWith(_ < _) == Seq(1, 2, 3, 4, 5, 6, 7, 8, 9)
} {
  println(s"${s11} ${s12} ${s13}")
  println(s"${s21} ${s22} ${s23}")
  println(s"${s31} ${s32} ${s33}")
  println("====================")
}
(6) (2) + (3)

for {
  s11 <- (1 to 9).par; s12 <- 1 to 9; s13 <- 1 to 9
  s21 <- 1 to 9; s22 <- 1 to 9; s23 <- 1 to 9
  s31 <- 1 to 9; s32 <- 1 to 9; s33 <- 1 to 9
  if s11 + s12 + s21 + s22 == 14 &&
    s12 + s13 + s22 + s23 == 17 &&
    s21 + s22 + s31 + s32 == 17 &&
    s22 + s23 + s32 + s33 == 21 &&
    s11 + s23 + s33 == 21 &&
    s12 + s13 + s22 == 9 &&
    s21 + s31 + s32 == 15 &&
    Seq(s11, s12, s13, s21, s22, s23, s31, s32, s33).sortWith(_ < _) == Seq(1, 2, 3, 4, 5, 6, 7, 8, 9)
} {
  println(s"${s11} ${s12} ${s13}")
  println(s"${s21} ${s22} ${s23}")
  println(s"${s31} ${s32} ${s33}")
  println("====================")
}
(7) (2) + (4)

for {
  s11 <- (1 to 9).par; s12 <- (1 to 9).par; s13 <- 1 to 9
  s21 <- 1 to 9; s22 <- 1 to 9; s23 <- 1 to 9
  s31 <- 1 to 9; s32 <- 1 to 9; s33 <- 1 to 9
  if s11 + s12 + s21 + s22 == 14 &&
    s12 + s13 + s22 + s23 == 17 &&
    s21 + s22 + s31 + s32 == 17 &&
    s22 + s23 + s32 + s33 == 21 &&
    s11 + s23 + s33 == 21 &&
    s12 + s13 + s22 == 9 &&
    s21 + s31 + s32 == 15 &&
    Seq(s11, s12, s13, s21, s22, s23, s31, s32, s33).sortWith(_ < _) == Seq(1, 2, 3, 4, 5, 6, 7, 8, 9)
} {
  println(s"${s11} ${s12} ${s13}")
  println(s"${s21} ${s22} ${s23}")
  println(s"${s31} ${s32} ${s33}")
  println("====================")
}
(8) (2) + (5)

for {
  s11 <- (1 to 9).par; s12 <- (1 to 9).par; s13 <- (1 to 9).par
  s21 <- (1 to 9).par; s22 <- (1 to 9).par; s23 <- (1 to 9).par
  s31 <- (1 to 9).par; s32 <- (1 to 9).par; s33 <- (1 to 9).par
  if s11 + s12 + s21 + s22 == 14 &&
    s12 + s13 + s22 + s23 == 17 &&
    s21 + s22 + s31 + s32 == 17 &&
    s22 + s23 + s32 + s33 == 21 &&
    s11 + s23 + s33 == 21 &&
    s12 + s13 + s22 == 9 &&
    s21 + s31 + s32 == 15 &&
    Seq(s11, s12, s13, s21, s22, s23, s31, s32, s33).sortWith(_ < _) == Seq(1, 2, 3, 4, 5, 6, 7, 8, 9)
} {
  println(s"${s11} ${s12} ${s13}")
  println(s"${s21} ${s22} ${s23}")
  println(s"${s31} ${s32} ${s33}")
  println("====================")
}
結果


#
内容
平均実行時間(ms)


1
基本形
34654.2


2
ifを一つにまとめる
6318.2


3
並列コレクション化(1つ)
16394


4
並列コレクション化(2つ)
15213.4


5
並列コレクション化(全部)
143388.2


6
(2) + (3)
3436.6


7
(2) + (4)
3210.8


8
(2) + (5)
79968.8


まとめ

一番速くなったのは(6)。
リスト内包表記的には述語(if式)を複数書いた方が綺麗に書けてるような気がするけど、パフォーマンス的にはよくない。
当たり前のことだけど、並列コレクション化を頑張る前にメソッドコールを減らすとか基本的なことをやった方がよさそう。
#	内容	平均実行時間(ms)
1	基本形	34654.2
2	ifを一つにまとめる	6318.2
3	並列コレクション化(1つ)	16394
4	並列コレクション化(2つ)	15213.4
5	並列コレクション化(全部)	143388.2
6	(2) + (3)	3436.6
7	(2) + (4)	3210.8
8	(2) + (5)	79968.8