go testの-benchを使いつつProject Eulerの4問目を解いた・速くした🚀
趣味プログラミングです。
go test の-benchを使い、Project Eulerの問題を解くプログラムを速くしていった過程を書きます。
解く&テスト書く -> 速くする という流れです。
今日のお題
Project Eulerの第4問日本語訳から。
左右どちらから読んでも同じ値になる数を回文数という.
2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.
では, 3桁の数の積で表される回文数の最大値を求めよ.
適当なループを書くと 995*583=580085 みたいな答えが出てきて誤答します。
誤答しませんか。私は間違えました👼
解く&テスト書く
さて、間違えずに、以下のようにして解いた、とします。
このパッケージではSolveという関数が計算結果を返しています。
euler004/main.go
package euler004
const max = 999
const min = 100
func Solve() int {
i := max
candidate := 0
for {
j := i
for {
x := i * j
if reversible(x) {
if candidate < x {
candidate = x
}
}
j--
if j < min {
break
}
}
i--
if i < min {
break
}
}
return candidate
}
func reversible(arg int) bool {
x := arg
if x%10 == 0 {
return false
}
y := 0
for {
y += (x % 10)
x = x / 10
if x == 0 {
break
}
y = y * 10
}
return arg == y
}
euler004/main_test.go
Solveの出力をチェックするテストも書いておきます。
package euler004_test
import (
"fmt"
e "github.com/hoshinotsuyoshi/study-go/euler/euler004"
)
func Example_Solve() {
fmt.Println(e.Solve())
// Output:
// 906609
}
このテストは 以下のように実行できます
$ go test euler004/main_test.go
ok command-line-arguments 0.007s
計測 ⏳
さて、ここから本題です。
まず、テスト側にベンチマークをとるためのコードを入れます。
--- a/euler/euler004/main_test.go
+++ b/euler/euler004/main_test.go
@@ -3,7 +3,6 @@ package euler004_test
import (
"fmt"
e "github.com/hoshinotsuyoshi/study-go/euler/euler004"
+ "testing"
)
func Example_Solve() {
@@ -11,9 +10,3 @@ func Example_Solve() {
// Output:
// 906609
}
+
+func Benchmark_Solve(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ e.Solve()
+ }
+}
これを -bench をつけて実行します。
$ go test -bench . euler/euler004/main_test.go
goos: darwin
goarch: amd64
Benchmark_Solve-4 300 5796457 ns/op
PASS
ok command-line-arguments 1.180s
1回の処理に 5796457 ns かかっていることがわかりました。
速くする 🚀
速くできる余地を後から見つけました(と、いうことにしましょう!)。修正します。
--- a/euler/euler004/main.go
+++ b/euler/euler004/main.go
@@ -5,23 +5,27 @@ const min = 100
func Solve() int {
i := max
+ element := 0
candidate := 0
for {
j := i
for {
x := i * j
if reversible(x) {
+ if element < j {
+ element = j
+ }
if candidate < x {
candidate = x
}
}
j--
- if j < min {
+ if j < element || j < min {
break
}
}
i--
- if i < min {
+ if i < element || i < min {
break
}
}
もう一度test実行。
$ go test -bench . euler/euler004/main_test.go
goos: darwin
goarch: amd64
Benchmark_Solve-4 10000 115018 ns/op
PASS
ok command-line-arguments 1.180s
5796457 ns -> 115018 nsになりました!
50倍ぐらい速くなりました!!! 🚀🚀 わーい!(わざとらしい)
ちなみに、私はアルゴリズム詳しくないので、もっと速くなると思います👼
まとめ
今回は_test.goなファイルの中にベンチマーク測定のコードを入れる方法を説明しました。
go楽しいですね。
以上です🎅
環境とか
$ go version
go version go1.9.2 darwin/amd64
参考
Go でベンチマーク - Block Rockin’ Codes
