Golangで数を増やしながらベンチマーク
ベンチマークを測定していると要素数を増やしたり、負荷を上げたりしながら性能がどのように変わるか調べたいときがあります。 変数をべた書きしたベンチマークをコピペして書くことも可能ですが、以下のような方法できれいに書くことができます。
ここでは関数doSomething()のベンチマークを取りたいとします。
package multibench
func doSomething(n int) {}
以下のようにテストファイルの中に、要素数nを引数とする関数を、補助的に用意することで目的が達成できます。ここでbenchmarkDoSomething()はpackage内でのみ参照できればいいので、小文字から始まることに注意してください。逆に測定したいBenchmarkDoSomething10()などは、大文字から始まります。
package multibench
import "testing"
func benchmarkDoSomething(n int, b *testing.B) {
for i := 0; i < b.N; i++ {
doSomething(n)
}
}
func BenchmarkDoSomething10(b *testing.B) { benchmarkDoSomething(10, b) }
func BenchmarkDoSomething30(b *testing.B) { benchmarkDoSomething(30, b) }
func BenchmarkDoSomething70(b *testing.B) { benchmarkDoSomething(70, b) }
func BenchmarkDoSomething100(b *testing.B) { benchmarkDoSomething(100, b) }
func BenchmarkDoSomething300(b *testing.B) { benchmarkDoSomething(300, b) }
func BenchmarkDoSomething700(b *testing.B) { benchmarkDoSomething(700, b) }
func BenchmarkDoSomething1000(b *testing.B) { benchmarkDoSomething(1000, b) }
func BenchmarkDoSomething3000(b *testing.B) { benchmarkDoSomething(3000, b) }
実行結果
$ go test -bench DoSomething BenchmarkDoSomething10-4 2000000000 0.33 ns/op BenchmarkDoSomething30-4 2000000000 0.34 ns/op BenchmarkDoSomething70-4 2000000000 0.33 ns/op BenchmarkDoSomething100-4 2000000000 0.35 ns/op BenchmarkDoSomething300-4 2000000000 0.33 ns/op BenchmarkDoSomething700-4 2000000000 0.33 ns/op BenchmarkDoSomething1000-4 2000000000 0.34 ns/op BenchmarkDoSomething3000-4 2000000000 0.34 ns/op PASS ok /YOURPATH/TO/multibench 5.680s
doSomeshingというよりdoNothingなので変化がわかりづらいですが、
関数の中身がnによって変化するようなものであればちゃんと変わります。
References
GolangでHMAC-SHA256署名する
APIの認証でHMAC(Hash-based Message Authentication Code)を使用したいことがあります。 HMACはその名の通り、あるhash-basedなメッセージ認証符号で、メッセージと秘密鍵をもとに生成されます。 今回はハッシュ関数にSHA256を用いて、HMACしてみます。
実装
func MakeHMAC(msg, key string) string {
mac := hmac.New(sha256.New, []byte(key))
mac.Write([]byte(msg))
return hex.EncodeToString(mac.Sum(nil))
}
References
GolangでMiller-Rabin素数判定法を実装してみる
背景
Wikipedia
にも記載されていますが、
Miller-Rabin素数判定法は
与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種で、乱択アルゴリズムです。
フェルマーテストでは、以下のフェルマーの小定理を用いて
素数判定を行いますが、カーマイケル数と呼ばれる合成数を、誤って(素数と)判定してしまいます。
例えば、最小のカーマイケル数は561ですが、のため、素数ではありません。
フェルマーの小定理
素数
と互いに素となる整数
に対して
が成り立つ。
フェルマーテストを改良したのがMiller-Rabin素数判定法です。
詳細はWikipediaを参照頂ければと思いますが、与えられた素数を奇素数(素数判定をしたいのは、大きい整数なので、奇素数を考えれば目的は十分に果たせます)と考え、
と表現します。ここで
は正整数で、
は奇数です。すると式(1)は以下のように書けます。
が素数であれば、式(2)を満たします。左辺を
とみて、式(2)について単位元の平方根を考えます。
非自明な平方根は存在しない(証明もWikipediaにあります)ので以下の2式のみを考えればよいことになります。
ここで、です。
上記は、自明な平方根
または
となった場合を考えて、
となった場合は、さらに繰り返し(平方根が
となるまで)平方根を考えていった結果を表しています。式(3)は
にならず、平方根が取れなくなるまで取ったあとの結果になります。
あとはフェルマーテストと同様に考えて、与えられた数が素数でない(合成数である)のであれば、式(3)および式(4)を満たさないとして、素数判定を行います。
フェルマーテストと同様に偽陽性(素数と判定したのに実は合成数だった)の可能性は残りますが、フェルマーテストより確率は低いようです。
実装
gist1cd38a67c96df7966b9c468927dc2757
結果
今回は以下の4パターンを判定してみました。
- 1から100までに含まれる素数
- 1から合成数(奇整数のみ)
- 以前作った合成数(16329805957987392833 = 7508269669 * 2174909357)
- 素数生成機により生成した500桁の素数
結果は以下の通り、いずれも正しく判定できています。
$ go run MillerRabinPrimalityTest.go ------------Prime------------- 2 : true 3 : true 5 : true 7 : true 11 : true 13 : true 17 : true 19 : true 23 : true 29 : true 31 : true 37 : true 41 : true 43 : true 47 : true 53 : true 59 : true 61 : true 67 : true 71 : true 73 : true 79 : true 83 : true 89 : true 97 : true ------------Composite------------- 9 : false 15 : false 21 : false 25 : false 27 : false 33 : false 35 : false 39 : false 45 : false 49 : false 51 : false 55 : false 57 : false 63 : false 65 : false 69 : false 75 : false 77 : false 81 : false 85 : false 87 : false 91 : false 93 : false 95 : false 99 : false 16329805957987392833 : false 75367631466941141791247084978233913478587466161271622771710895906453753967164967411257954571043148038883968051384064219878882200013408641715083492640764339527637873502061727098279950196988248939994544197535642414553039637030217247486372549770605212095298947963579455290328750806815560590656493190626063424483777638146122548073605596393468295558919015322872295712049815793564477203891171966598995001945926910413702372501638140065699147590309176011776418089018393636130620122226631715476290375904684033 : true
今回はをランダムに選ぶ回数
kをk=20としましたが、精度を上げるにはこの値を増やすことが有効です。逆にk=1などとしてみると以下のように結構間違えます。もちろん乱択アルゴリズムなので何度もやるとミスがあったりなかったりですが。
$ go run MillerRabinPrimalityTest.go ------------Prime------------- 2 : true 3 : true 5 : true 7 : true 11 : true 13 : true 17 : true 19 : true 23 : true 29 : true 31 : true 37 : true 41 : true 43 : true 47 : true 53 : true 59 : true 61 : true 67 : true 71 : true 73 : true 79 : true 83 : true 89 : true 97 : true ------------Composite------------- 9 : false 15 : false 21 : false 25 : false 27 : true 33 : false 35 : false 39 : true 45 : false 49 : false 51 : false 55 : false 57 : false 63 : false 65 : false 69 : false 75 : false 77 : false 81 : false 85 : false 87 : false 91 : true 93 : false 95 : false 99 : false 16329805957987392833 : false 75367631466941141791247084978233913478587466161271622771710895906453753967164967411257954571043148038883968051384064219878882200013408641715083492640764339527637873502061727098279950196988248939994544197535642414553039637030217247486372549770605212095298947963579455290328750806815560590656493190626063424483777638146122548073605596393468295558919015322872295712049815793564477203891171966598995001945926910413702372501638140065699147590309176011776418089018393636130620122226631715476290375904684033 : true
Reference
Atomでconfig.fishをハイライトさせる
zshからfishに移行している最中にconfig.fishがAtomでハイライトされていなかったのでさせました。
単純に拡張子とscope nameを対応させるだけですが、fishを検索ワードにしてると意外と引っかからなかったのでメモ書きとしてまとめておきます。
事前準備(file-typesのインストール)
Atomを開き、cmd + ,でPreferenceを開きます。
Installからfile-typesパッケージを検索し、インストールします。
config.csonの編集
以下のように設定します。
恐らく$HOME/.atom/config.csonにあるかと思います。
"*":
"file-types":
fish: "source.shell"
上記編集後、保存すれば設定が反映されます。
Reference
GolangでCuckoo Hashingを実装してみた
2017/5/27 修正
int64型であるkeyを[]byte型へconvertする際にhasher.Write([]byte(string(key)))ではうまくいかないため以下のように修正しました。
b := make([]byte, 8) binary.LittleEndian.PutUint64(b, uint64(key)) hasher.Write(b)
背景
BloomFilterを実装した後に、やろうやろうと思っていたCuckoo Hashingを実装してみました。
Cuckoo Hashing自体の説明は
@_krzさんの記事がわかりやすいです。絵を交えられているのでイメージもつきやすいです。
メリットとしてはlookupが定数時間(2回比較するだけ)で完了することが挙げられます。
またアルゴリズム自体がわかりやすいです。2つのテーブルを用意しておき、挿入したいkeyのハッシュ値を計算し、ハッシュ値をindexとみて、テーブルが空いていれば挿入。すでに埋まっていれば、keyと既に入っていた値を交換して、もう一つのテーブルで同様の操作を繰り返すという流れになっています。カッコーの托卵のようですね。
デメリットは、ハッシュの衝突が起こった場合やループが無限ループに入る恐れがあります。今回の実装でもMAXLOOPを設定することで無限ループを防いでいます。
また、こちらによるとテーブルの半分が埋まった段階で性能が落ちてしまうそうです。
実装
gistaaf77c63f3668efdd44e2f4ae9642f76
今回は0を空とする実装にしましたが、実際には0を挿入したい場合も多いと思うので、その場合はうまくゼロ値を使うなどするのがよいと思います。
References
Golangで有向グラフをかく
背景
言語処理100本ノック 2015をやっている最中に、有向グラフで表示する問題(Q44)に遭遇しました。 gographvizでDOT言語のdotファイルを作成し、graphvizで可視化したのでまとめます。
動作環境
# sw_vers ProductName: Mac OS X ProductVersion: 10.11.6 BuildVersion: 15G31 # go version go version go1.8 darwin/amd64 # dot -V dot - graphviz version 2.40.1 (20161225.0304)
インストール
graphvizのインストール
# brew install graphviz
gographviz packageのインストール
# go get github.com/awalterschulze/gographviz
有向グラフの作成
設定値などはGraphvizとdot言語でグラフを描く方法のまとめを参考にさせて頂きました。
gist4c915c1e14aae064a92cc30fbcb5eac7
dotファイル上で、Attributionにダブルクオーテーションが必要な場合は、エスケープしないとsyntaxエラーになるので注意してください。
また、今回のように事前のテストができる場合は問題ないですが、Attrを動的に設定するような場合は、以下のようにエラーチェックをしたほうがよいでしょう。
// 例) colorschemeを設定する場合
if _, err := gographviz.NewAttr("colorscheme"); err != nil {
panic(err)
}
nodeAttrs["colorscheme"] = "rdylgn11" // 問題ないことを確認してからmapに格納する
出力のdotファイルは以下のようになります。
gistc0bdfb47ec6948b6bed5cd51ad92f05c
有向グラフの出力
噂のGraphvizを使ってみるにもありますが、上記で出力したdotファイルをもとに、pngファイルとして結果を出力させるには以下のようにします。
# dot -T png diGraph.dot -o diGraph.png
結果です。いい感じですね。
