sukoというパズルの適当なソルバを書いたので簡単なベンチマークを取ってみた。
問題は2014/01/06のmetro紙より。
new scala.testing.Benchmark {
def run() = {
// solver here...
}
}.runBenchmark(5)
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("====================")
}
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("====================")
}
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("====================")
}
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("====================")
}
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("====================")
}
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("====================")
}
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("====================")
}
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式)を複数書いた方が綺麗に書けてるような気がするけど、パフォーマンス的にはよくない。 当たり前のことだけど、並列コレクション化を頑張る前にメソッドコールを減らすとか基本的なことをやった方がよさそう。