mycliの選択候補のカラーを変更する
mycliではSyntax Colorsにあるようにカラーテーマを設定できますが、選択候補はカラーテーマによって変更されないので以下のように見づらくなってしまいます。
解決するためには、~/.myclircのCompletion menusを編集すればカラーを自由に設定することができます。
以下は自分の設定例です。
# Completion menus. Token.Menu.Completions.Completion.Current = 'bg:#686868 #d8d8d8' Token.Menu.Completions.Completion = 'bg:#2d2d2d #d8d8d8'
変更後は以下のようになりました。
※テーマもsyntax_style = monokaiとしています。
Reference
GolangでBucketized Cuckoo Hashingを実装してみた
先日、Cuckoo Hashingの記事を書いたところ、以下のご指摘を頂いたのでBucketized版も実装してみました。
bucketizedして性能バク上げしよう₍₍ (ง´･_･`)ว ⁾⁾
— まっちゃら (@matsu_chara) 2017年5月6日
Erlingssonらの論文にも述べられていますが、挿入した要素がテーブルサイズの50%に達すると性能が低下するそうです。 前回も述べましたが、挿入時のハッシュの衝突によって要素の追い出しが起きてしまうためですね。そこで、挿入できる数をひとつでなく複数個にする(本記事ではこれをbucketと呼ぶことにします)ことで、衝突しても用意したbucketの大きさだけそのまま挿入できるようにしたものがBucketized Cuckoo Hashingです。
Fotakisらによるとひとつのbucketに4つの要素まで詰め込めるようにした場合では97%まで空間効率を上げることができるそうです。
この論文中ではBucketized Cuckoo Hashingはd-ary Cuckoo Hashingと呼ばれており、d=4の場合で97%と述べられています。
実装
gist0b30182c97fa91f73174ebcf3baf7645
上記では結果が見やすいようにd=2としています。
ベンチマーク
せっかくなのでbucketized CuckooHashingを通常のCuckooHashingと比較してみます。
ここでは一様乱数で発生させた要素を挿入し、挿入時間を測定します。
測定内容を実環境の問題と合わせて考えるべきですが、実環境の問題はどんなのがあるんでしょうか…
挿入する要素数をテーブルサイズ×bucketサイズで除した値を充填率とし、充填率が大きくなったときに挿入時間がどのように変化するか測定します。
今回は限られたメモリ上でbucketizedするかしないかを決定することを想定し、テーブルサイズとbucketのサイズを以下とします。
[Normal CuckooHashing] N int64 = 100000 // テーブルの大きさ [Bucketized CuckooHashing] N int64 = 25000 // テーブルの大きさ BCKSIZE int = 4 // bucketのサイズ
ベンチマークコードはGithubにあります。 ベンチマーク結果は以下です。
全体としてbucketizedしたほうが挿入時間が小さくなっていることがわかります。
References
- GolangでCuckoo Hashingを実装してみた
- Ross, Kenneth A. “Efficient hash probes on modern processors.” Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on. IEEE, 2007.
- Erlingsson, Ulfar, Mark Manasse, and Frank McSherry. “A cool and practical alternative to traditional hash tables.” Proc. 7th Workshop on Distributed Data and Structures (WDAS’06). 2006.
- Cuckoo hashing - wikipedia
- Fotakis, Dimitris, et al. “Space efficient hash tables with worst case constant access time.” Annual Symposium on Theoretical Aspects of Computer Science. Springer Berlin Heidelberg, 2003.
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"
上記編集後、保存すれば設定が反映されます。
