読者です 読者をやめる 読者になる 読者になる

BloomFilterについて調べてみた

BloomFilterとは

Wikipedia にも記載されていますが、ある要素が集合に属しているかを検査できるフィルタです。

一番最初に思いつく実装としては、こんな感じでしょうか。

  • 集合の先頭から順に要素を比較していく
  • 途中で見つかれば「属している」
  • 最後まで見つからなければ「属していない」

この場合、要素数をNとして、O(N)の計算量が必要ですが、BloomFilterでは、BloomFilterで使用するハッシュ関数の個数をkとして、O(k)で計算ができます。
もちろん、これにはトレードオフがあり、「属している」と判断したものの、 実は「属していなかった」 という偽陽性を許容することで上記のような利点を実現しています。
※ただしBloomFilterでは、原理的に偽陰性はありません。

詳細はこのあとみていきますが、実際に動かしてみるとわかりやすいので、体験したい方はGUIでポチポチできるこちらがおすすめです。

空間効率性

以前、記事 にも書きましたが、A. PaghらによるとBloomFilterにデータを格納するために必要なbit数は  N log_2 \frac{1}{p} \times log_2 e [bit]です。
ここで、pを偽陽性確率、Nを集合の要素数とします。

単純に生データを格納することを考えると、 N \times要素の大きさ[bit]の領域を確保する必要があります。
例えばユーザIDを8文字英数と絞ったとして N \times 8文字 \times 8(1Byte) [bit]が必要です。このことからもBloomFilterの空間効率性が高いことがわかります。

計算時間

前述の通り、kをBloomFilterで使用するハッシュ関数の個数として、O(k)で計算ができます。 要素の追加もO(k)です。

セキュリティ

副次的なメリットですが、セキュリティ面でも有利な可能性があります。
redis4.0で使えるようになるかもしれないモジュールredabloomsでも使われているDebloom
こちらのREADMEを読むまで発想すらなかったですが、アプリケーションでの応用を考えたときに実データを保持しなくてよいというセキュリティ上のメリットも考えられます。 READMEにあるのは以下の記載なので、そこまで踏み込んだ記載ではないですが……。

A Bloom filter gives the application cheap, memory efficient set operations, with no actual data stored about the given element.

どういうことかと言うと、BloomFilterでは実データのハッシュを計算し、その結果をもとに配列へのマッピングを行うため、実データそのものをストアしておく必要がありません。
当然、この場合は暗号学的な現像計算困難性や衝突困難性を満たすようなハッシュ関数を選択する必要があります。 MD5のようなハッシュ関数を使用している場合は、この限りではありません。

応用先

Broderらのsurveyによると1970年にBloomによって提案されて以来、初期のUNIXのスペルチェックで使われていたそうで、今でもデータベースの分野でよく使われているそうです。

セキュリティ の箇所でも述べましたが、 redis にも以下の記載があり、使われているようです。

Encode a lot of data in little space, or create a Redis backed Bloom Filter using GETBIT and SETBIT.

Broderらのsurveyでも述べられていますが、リストで持つようなデータではBloomFilterに応用できる可能性があるということの実例ですね(リストで保持している=検索したいという考えのもとで)。

ほかにもsquid-cache でも使われていたり、http2のcache-aware server pushの文脈でもBloomFilterが登場します。cache-aware server pushでは、Golomb coded setが使われているみたいです。
Golomb coded setについては以前まとめたのでこちらをどうぞ。

最後に

応用先について、調べれば調べるほど出てきてまだまだ出てきそうです。読んでいる途中の論文でも登場しているので、まとまったら追記したいです。
実装もそのうち記事にします。。。

2017/2/4 追記
実装も記事にしました。

参考

Golangでソートアルゴリズムのベンチマークを書いてみる

前回はテストを書いたので、今回はベンチマークです。対象アルゴリズムは前回同様、以下7つのソートアルゴリズムです。

ベンチマークの書き方

Go言語標準のtestパッケージにあるようにBenchMark<関数名>の形で関数を書き、引数をb *testing.Bにします。
するとb.Nが自動的に設定され、[0, b.N)でループし、ベンチマークが計測されます。
前回と同様にBubbleSortを例に取ると以下のようになります。

gistb8368c3fa411a7150eaa662d441979a1

ここで注意が必要なのは、ソート対象を毎回初期化してあげることです。
今回のコードではsliceを渡しているので値渡しではなく、参照渡しとなります。そのため、2回目以降のループではソート済みのsliceをソートすることになり、正しくベンチマークできません。
詳細は「ソート対象の初期化漏れ」にて後述します。

今回やりたいのは他のソートアルゴリズムも含めた比較なので、ソート対象の変数は以下のように別ファイルで定義することにします。
(以下の例の対象は適当です)

gistf3b900057c02e0905169e3e7ebf0aac7

-benchオプションを付けて実行してみると以下のようになります。

# go test -bench BubbleSort
PASS
BenchmarkBubbleSort-2         20000000         111 ns/op

2000万回実行し、一回あたり平均で111nsでした。 簡単にベンチマークが書けていいですね。
ディレクトリ内をまとめて実行したい場合はgo test -bench .とすればOKです。

ハマったところ

ベンチマーク結果の前にハマったところです。

ソート対象の初期化漏れ

ソート対象をsliceとしてソートアルゴリズムに渡していることに注意を払っておらず、ソート済みの配列でベンチマークを取っていました。
毎回、sliceを初期化してあげないと二回目以降のループでソート済みの配列をソートすることになってしまいます。 (前述の通り、値渡しではなく、参照渡しのため)

実際、初期化をせずに行ったベンチマークの結果は以下です。

// ソート対象: {0, 3, 1, 2, 3, 4, 5, 1, 9, 0}

# go test -bench .
PASS
BenchmarkBubbleSort-2        20000000           83.7 ns/op
BenchmarkHeapSort-2           3000000          572   ns/op
BenchmarkInsertionSort-2    100000000           17.7 ns/op
BenchmarkMergeSort-2          2000000          804   ns/op
BenchmarkMQuickSort-2        20000000           86.8 ns/op
BenchmarkSelectionSort-2     20000000           99.6 ns/op
BenchmarkShellSort-2          3000000          528   ns/op

やたらと挿入ソート(InsertionSort)が早くなっていることがわかります。
ちなみにBubbleSortを例としたコードは以下です。 2回目以降はソート対象aが初期化されず、ソート済み配列となります。

gistc5799874dd907597a619a0f2d60f8c84

ベンチマークのループ内でStartTimer()StopTimer()を呼ぶと遅い

今回の場合、ソース対象を初期化したり、乱数でソート対象を生成してベンチマークを測定します。 その処理はソートアルゴリズムの実行時間とは関係ないので、初期化処理中はベンチマークのタイマーを止めたくなります。
実際、testパッケージにはStartTimer()StopTimer()が用意されています。

ところがこれはベンチマークループの外で呼ぶべきです。
ベンチマークタイマーの計測開始は、[0, b.N)のループからではなく、BenchMark<関数名>(b *testing.B)が実行されたときから、だからです。

stackoverflowですが、Golang benchmarking b.StopTimer() hangs — is it me? にも書いてあるように、b.Nが10億などとなった場合、ループ中でStartTimer()StopTimer()を呼ぶとベンチマークに膨大な時間を要します。
例えば1回のタイマー停止/開始に要するが100nsだとしても、現実世界では10億回のループ中に100秒が経過してしまいます。
これとは別にStartTimer()StopTimer()を呼ぶコストやベンチマーク対象の時間が乗ってきます。

今回はその回避策として、初期化処理だけのベンチマークを測定し、それに要する時間をソートアルゴリズムベンチマークから引く方法を取ります。
計測用のコードは以下です。

gist68c61fa11c1371912da88d55ef316e5d

Base(baseline)じゃなくてoffsetで名前統一すべきだった

結果

以下の3パターンをベンチマークしてみます。

  • 無印: {0, 3, 1, 2, 3, 4, 5, 1, 9, 0}
  • Sorted: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
  • RandomizedData: [0, 9]をランダムに並べた順列(重複なし)
# go test -bench .
PASS
BenchmarkBaseCopy-2                    200000000          8.14 ns/op
BenchmarkBaseRandom-2                     100000         14619 ns/op
BenchmarkBubbleSort-2                   10000000           111 ns/op
BenchmarkBubbleSorted-2                 20000000          90.1 ns/op
BenchmarkBubbleSortRandomizedData-2       100000         14923 ns/op
BenchmarkHeapSort-2                      2000000           696 ns/op
BenchmarkHeapSorted-2                    2000000           615 ns/op
BenchmarkHeapSortRandomizedData-2         100000         15420 ns/op
BenchmarkInsertionSort-2                10000000           149 ns/op
BenchmarkInsertionSorted-2              50000000          23.2 ns/op
BenchmarkInsertionSortRandomizedData-2    100000         14848 ns/op
BenchmarkMergeSort-2                     2000000           884 ns/op
BenchmarkMergeSorted-2                   2000000           771 ns/op
BenchmarkMergeSortRandomizedData-2        100000         15719 ns/op
BenchmarkQuickSort-2                    10000000           206 ns/op
BenchmarkQuickSorted-2                  20000000          90.5 ns/op
BenchmarkQuickSortRandomizedData-2        100000         14814 ns/op
BenchmarkSelectionSort-2                10000000           184 ns/op
BenchmarkSelectionSorted-2              20000000           108 ns/op
BenchmarkSelectionSortRandomizedData-2    100000         15197 ns/op
BenchmarkShellSort-2                     2000000           668 ns/op
BenchmarkShellSorted-2                   3000000           529 ns/op
BenchmarkShellSortRandomizedData-2        100000         15568 ns/op

流石に生そのままだと見づらいので、グラフにします。 offsetも引いてあります。

f:id:cipepser:20170122171809p:plain

ソート済みの挿入ソート圧倒的ですね。 また要素数が10個程度なのでバブルソートでも有用な感じですね。 せっかくなので要素数を多くしてみましょう。 手でソート対象を10万個も書くのは大変なのでソート済みと乱数のみにします。
結果は以下です。軸は縦横ともにlogスケールにしています。

f:id:cipepser:20170122171811p:plain

f:id:cipepser:20170122171815p:plain

こちらでもソート済みであれば、挿入ソートの速さが伺えます。
また乱数の結果から、一般にはクイックソートが速いというのもわかりますね。

各ソートアルゴリズムの平均計算量は、以下です。

ソートアルゴリズム 平均計算量
バブルソート O(n2)
ヒープソート O(n log n)
挿入ソート O(n2)
マージソート O(n log n)
クイックソート O(n log n)
選択ソート O(n2)
シェルソート O(n log n)

乱数のほうを見ると要素数が大きくなるにつれて、O(n2)と O(n log n)ではっきりとわかれてくることがわかります。
素数が小さい範囲では、クイックソートが最速ではないので、実用上は入力の要素数によってソートアルゴリズムを使い分けるのがよさそうです。

最後に

コードはGitHubにもあげてあります。

2017/1/14 修正 Gitではなく、GitHubとの指摘を頂いたので修正しました。

Reference

Golangでソートアルゴリズムのテストを書いてみる

背景

先日書いた記事 にてクイックソートのバグをご指摘頂きました。
実装中は適当に入力値を変えてソートがうまくできていることを確認していたものの、実装して満足してしまったためにバグが混入していました。
やはり テストはしっかり書かなくてはいけない と思い、go testしようじゃないかと思い立ちました。

どうやってテストするか

未整列な配列は用意するにしても、いちいちそれを手作業で正しい順番にするのもめんどくさいしですし、それこそバグが混入するかもしれません。
テスト対象と比較すべきは、正しい結果 です。 Go言語標準のsortパッケージを使いましょう。
Godocにもあるように以下のように使用します(l.11)。

gist432ad7127932ecf06acd2978e0dcc2a1

配列同士の比較はreflectパッケージのDeepEqual を使用します。

gistf0ec9f7b3753cda59d84d05d2b631557

今回ソートアルゴリズムについて、テストの入力パターンは[]intに限るとすると go test で出来ること のTipsが有効なのでループでテストさせます。

テストパターンはソートアルゴリズムにまたがり共通なので以下のように別出ししておきます。
パッケージ名はMySortとしました。

gist4a671073d198359db81104618e763db2

BubbleSortでの例は以下です。

gista7dace84aae086af18858a69693ad9c4

gist59f87abcfd8397c552fcaddf79e143ca

テスト結果

では前回実装した以下7つのソートをテストしてみましょう。

実装はgitにあげてあります。

いよいよテストです。
git testを実行する際はMySortディレクトリ内で行います。

# go test
PASS
ok      MySort  0.004s

通ってますね。
ちなみにわざと失敗するケースとしてactualとexpectedの比較の前にactual[0] = 100とすると以下のようになります。
どのように表示するかはif文の中に書けばよいので見やすいよう成形しましょう。

# go test
--- FAIL: TestSort (0.00s)
    BubbleSort_test.go:27:
        expected: [1 2 3 4 5]
        actual: [100 2 3 4 5]
    BubbleSort_test.go:27:
        expected: [1 2 3 4 5]
        actual: [100 2 3 4 5]
    BubbleSort_test.go:27:
        expected: [1 1 2 3 4 5]
        actual: [100 1 2 3 4 5]
    BubbleSort_test.go:27:
        expected: [0 1 2]
        actual: [100 1 2]
    BubbleSort_test.go:27:
        expected: [1 1 1 1 1 1 1 1]
        actual: [100 1 1 1 1 1 1 1]
FAIL
exit status 1
FAIL    MySort  0.007s

最後に

テスト書きましょうというのは、よく聞くものの実はこれまでテストというものを書いたことがありませんでした。
今回、実際に書いてみてどんなものなのかイメージが掴めました。
が、テストパターンが足りてない気配しかないので網羅性難しいですね......。

またせっかくソートを実装しているので次はベンチマークやりたいですね。
テストだとうまく実装できていれば同じ結果になるので比較して楽しみたいところです。

Reference

基本的なソートアルゴリズムをGolangで実装してみた

2017/1/14 修正
intelf000さんのご指摘を受け、クイックソートについて、以下のバグを修正しました。
(合わせてsliceが参照渡しであることにも注意し、実装を改めています)

[内容]
a[left], a[right], pivotが同一の値となった場合に panic: runtime error: index out of range が発生。

背景

ソートアルゴリズムの話をするときに、自分の中で整理できていなかったので以下のアルゴリズムを実装してみました。

Goで書いたのは筋トレも兼ねているだけです。

そもそもGoにはsortパッケージ があります。
ちなみにリンク先を見て頂ければわかりますが、sortパッケージはクイックソートで実装されています。
(実体としては、データ長に応じて、ヒープソートと挿入ソートを併用する実装になっています)

ある程度ソート済みのアルゴリズムでは挿入ソートのほうが高速なのでソートしたいデータの特性によってはsortパッケージ以外を使用する選択肢もありそうです。

バブルソート

隣同士比較して交換するだけです.

gist95666e2ef1f45fece4b45fbafdff0f27

選択ソート

最小値(あるいは最大値)を「選択」し、小さい順に並べていくソートです。

gista224fb335644d3ca8567ec6aff87acb7

挿入ソート

整列済みのデータに対して、要素を正しい位置に挿入します。 整列済みであることを意識して、比較は後ろから行うようにしてみました。

連結リストで実装するのがよかったですね......。

gistfb4e64acc94d5b92a0227e898df99aa1

シェルソート

適当な間隔 h_iずつ空けて、グループを作り、グループ内でソートします。さらに間隔を狭めていき、間隔が1になったところで全体をソートします。

上記の過程である程度ソートされていき、最後は挿入ソートで締めます。

Knuth先生のThe Art of Computer Programmingによると以下を満たすよう間隔を選んでいくと O(n^{1.25})になるそうです。
(未読ですが......)

 h_{i+1} = 3h_i + 1
 h_0 = 1, h_i \in {\cal N}

giste344fbfc474b18e3e0f548dfaeb65ec8

マージソート

データを適当に分けていき、それをマージする際にソートします。

gist695d1274cca4314d1c755368ccd6abc0

クイックソート

一般なデータに対しては最も高速といわれているそうです。 ピボットより小さい値を持つグループと大きい値を持つグループにわけ、再帰的にソートしていきます。

ピボットの選び方によっては無限ループに入ってしまったり、計算量が増えてしまうので注意が必要です。

2017/1/14 訂正(詳細は記事冒頭に記載)

giste9999b007076c5c77f23b9188dc79598

ヒープソート

ヒープ木では根が最大(または最小)になるので、根を取り除き、残った部分をさらにヒープ木にすることを繰り返します。
こちらが大変参考になります。

UpHeapとDownHeapをまとめてヒープ木を作る関数にするのもありかと思ったのですが、それだと必要以上に計算が多くなるので微妙なんでしょうか。

gist71006d4ed430ae94e04dd6fe3c182ada

感想

全体的にGoの配列(slice)の操作に苦戦しました。 複数の値をまとめて代入できなかったり、配列を添え字で抜き出すところとか自分の想像する挙動と微妙に異なるので境界は特に気を遣いながら書きました。

上記以外にも様々なソートアルゴリズムがあるので実装していきたいです。 特にデータの特性に応じて、一定の条件下ではより高速になるようなソートはおもしろそうですね。

Reference

Golangで言語処理100本ノック2015 第1章: 準備運動

Golangで言語処理100本ノック2015 第1章: 準備運動

言語処理100本ノック 2015の第1章: 準備運動の10問です。

00. 文字列の逆順

文字列"stressed"の文字を逆に(末尾から先頭に向かって)並べた文字列を得よ.

gist09251fc66515bb60f15d58721c08466a

rune(int32のalias)使ってみました。

01. 「パタトクカシーー」

「パタトクカシーー」という文字列の1,3,5,7文字目を取り出して連結した文字列を得よ.

gistedcd4efc4d726baa40b331b7e5266e9b

拡張性に乏しいコードになってしまいました......。

02. 「パトカー」+「タクシー」=「パタトクカシーー」

「パトカー」+「タクシー」の文字を先頭から交互に連結して文字列「パタトクカシーー」を得よ.

gist2bb8c732a7892380679b0d89c75104a0

range使いたかったものの2つの配列だと難しいですね。

03. 円周率

"Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics."という文を単語に分解し,各単語の(アルファベットの)文字数を先頭から出現順に並べたリストを作成せよ.

gist7aad5498729843d80b17ee165820e1c7

04. 元素記号

"Hi He Lied Because Boron Could Not Oxidize Fluorine. New Nations Might Also Sign Peace Security Clause. Arthur King Can."という文を単語に分解し,1, 5, 6, 7, 8, 9, 15, 16, 19番目の単語は先頭の1文字,それ以外の単語は先頭に2文字を取り出し,取り出した文字列から単語の位置(先頭から何番目の単語か)への連想配列(辞書型もしくはマップ型)を作成せよ.

gist9992125ab064053287a0dd4dd4ae4c0a

マグネシウム......

05. n-gram

与えられたシーケンス(文字列やリストなど)からn-gramを作る関数を作成せよ.この関数を用い,"I am an NLPer"という文から単語bi-gram,文字bi-gramを得よ.

gistcbc1ee78191bf3f77d7a49df56d45a19

結構めんどくさかったものの、文字列はruneとして扱って、最後表示するときだけstringにするほうがバグの混入も減りそうな気がしました。

06. 集合

"paraparaparadise"と"paragraph"に含まれる文字bi-gramの集合を,それぞれ, XとYとして求め,XとYの和集合,積集合,差集合を求めよ.さらに,'se'というbi-gramがXおよびYに含まれるかどうかを調べよ.

giste1d1767b1727a65b3d4b1702cfab0dbc

sliceに対してappendだけじゃなくてremoveも欲しくなりました。

07. テンプレートによる文生成

引数x, y, zを受け取り「x時のyはz」という文字列を返す関数を実装せよ.さらに,x=12, y="気温", z=22.4として,実行結果を確認せよ.

gist916d6c7abb3721d8c4df8e285afc51b2

08. 暗号文

与えられた文字列の各文字を,以下の仕様で変換する関数cipherを実装せよ.

英小文字ならば(219 - 文字コード)の文字に置換 その他の文字はそのまま出力 この関数を用い,英語のメッセージを暗号化・復号化せよ.

gist89bee82fa497b427b37eef97744b58ce

09. Typoglycemia

スペースで区切られた単語列に対して,各単語の先頭と末尾の文字は残し,それ以外の文字の順序をランダムに並び替えるプログラムを作成せよ.ただし,長さが4以下の単語は並び替えないこととする.適当な英語の文(例えば"I couldn't believe that I could actually understand what I was reading : the phenomenal power of the human mind .")を与え,その実行結果を確認せよ.

gist72bf7cadaab3f3219dab0349223925ad

部分配列取り出すとき、a[0:3]のようにしたときa[0], a[1], a[2]が取り出されてa[3]は含まれないのをいつも勘違いするので気をつけていきたいです。

Reference

Golomb-coded setについて調べてみた

Oku KazuhoさんのHTTP/2の課題と将来を拝見していたらGolomb-coded setなるものが登場したのでいろいろ調べたメモです。

BloomFilterについてもそのうち記事にするかもしれないです。
むしろBloomFilterを先に書くべきでは。

前提、やりたいこと

やりたいことの例としてhttp2のcache-aware server pushを考える。
clientからserverへリクエストするとき、htmlよりcssを先にpushするといったような優先度付けをしたい。
一方で、既にclientでcacheしていたら、改めてserverからpushするのは無駄。
そこでclientからのリクエスト中のcookieにcache済みのjsやcssといったasset情報埋め込んでserverに教えてあげる。

とはいえ、そのままassetごとにpath/file名とか書くと無駄が大きいし、file名は変わらないけど中身が変わっていたりすると区別ができなくてつらい。
→ハッシュして送る。

ここで偽陽性はある程度許容する。
やりたいことは、すでにcache済みだったら送らない(≒送る数を減らしたい)なので、確実にcacheされてないと言えるなら送る。
(偽陽性で、cache済みと判断したけど実はcacheされてないやつはclientが改めてGETする)
→BloomFilterのような確率的データ構造が適している。

BloomFilterの空間効率性

A. PaghらによるとBloomFilterにデータを格納するために必要なbit数は以下。

BloomFilterで使うbit数:  N log_2 \frac{1}{p} \times log_2 e

確率的データ構造に使うbit数(理論値):  N log_2 \frac{1}{p}

 N: 貯めておく要素数
 p: 偽陽性確率

 log_2 e ≒ 1.44 なので44%程度、BloomFilterは理論値より空間効率が悪い。

挿入するデータの分布に適した方法でデータを格納すれば理論値に近づく。
→Golomb-coded setは、ハッシュ値の均一性を利用し、幾何分布のときにHuffman符号と同じ効率になるGolomb符号により理論値に近づける。

Golomb-coded set

※例は以下の参考文献のなぞり。

変数はさっきと一緒。

 N: 貯めておく要素数
 P: 偽陽性確率

例題として以下のフォネティックコード( N = 26)を考える。

['alpha', 'bravo', 'charlie', 'delta', 'echo', 'foxtrot', 'golf', 'hotel', 'india', 'juliet', 'kilo', 'lima', 'mike', 'november', 'oscar', 'papa', 'quebec', 'romeo', 'sierra', 'tango', 'uniform', 'victor', 'whiskey', 'xray', 'yankee', 'zulu']

許容する偽陽性確率を P = \frac{1}{64}とする。

要素は適当なハッシュ取ってから mod (N \times \frac{1}{P} (= 1664)する。

※cache-aware server pushで使う場面では、sha-2にするというようなセキュリティ性は担保しなくてよく、均一性と速度のほうが重要なのでMD5sha-1で十分。

 [0, (N \times \frac{1}{P} ) ] = [0, 1664]でハッシュ値が分布する。
ここで N(= 26)要素をハッシュ計算してからソートする。
十分に均一なハッシュならソート後の要素列のi番目とi+1番目の差は \frac{1}{P} (=64)くらいになる(ことが多いと期待される)。
 \frac{1}{P} (=64)で割ると、商は0 or 1になることが多い。
→これ幾何分布となるのでGolomb符号使うと効率がよい。

符号化は以下の表のように行う。

符号化
0 0
1 10
2 110
3 1110
4 11110

余りはそのまま2進数でくっつける。
例) 68 / 64 = 1 ... 4 → 68 = 0b(10 100)
※10と100の間のblankは便宜的に入れてるだけ。

これでフォネティックコードを符号化すると以下になる(197 bits)。

11001011 10101001 00100000 11110111 10000000 01100110 00111010 00000110 00011111 00100000 01100101 00011001 10001010 10110001 00000011 00101101 01100010 01001100 01010000 00110011 00011110 01100110 10101110 10011000 00011

それぞれデータの格納に必要なbit数は以下のようになるので、BloomFilterより理論値に近くなっていることがわかる。

理論値: 156 bits  
BloomFilter: 225 bits (最適なハッシュ関数の数で同じ偽陽性確率を許容する場合)  
Golomb-coded set: 197 bits  

参考

「トランプを3枚出してその積を103で割った余りの値の元素をいかに早く言うか」をGolangとMySQLで実装する

背景

こちらのツイートが流れてきたのでgolangで実装してみました。

「トランプを3枚出してその積を103で割った余りの値の元素をいかに早く言うか」

環境

CentOS Linux release 7.2.1511 (Core)

mysql Ver 14.14 Distrib 5.7.17, for Linux (x86_64) using EditLine wrapper

go version go1.6.3 linux/amd64

事前準備

環境変数

mysql用のdriverをgo getするためにも必要なのでGOPATHを設定します。

$ export GOPATH=<path>

またMySQLに接続するためのパスワードを環境変数から取得するため、設定します。

$ export MYSQL_PASSWD=<password>

MySQLのインストール

GoでMySQLに接続するにある go-sql-driver/mysql のインストール を行います。

$ go get github.com/go-sql-driver/mysql

データベースの構築

今回はgolangMySQLを叩いてみたかったので、データベースを構築しておきます。

データベース名: div3element

テーブル名: element

テーブルの構成は以下です。

mysql> show columns from element;
+--------+-------------+------+-----+---------+-------+
| Field  | Type        | Null | Key | Default | Extra |
+--------+-------------+------+-----+---------+-------+
| n      | int(11)     | NO   | PRI | NULL    |       |
| symbol | varchar(2)  | YES  |     | NULL    |       |
| name   | varchar(10) | YES  |     | NULL    |       |
+--------+-------------+------+-----+---------+-------+

nを原子番号として元素記号(symbol)、元素名(name)を引けるようにしています。

構築用のsqlこちら

実装

gist30613d82a059a6a51c518d0d4026c452

コードはgithubにもあげています。

使い方

コンパイルしてから、以下のように標準入力から3つの数字を入力すると、原子番号と元素名を返します。

$ ./main 12 13 11
Answer: 68, エルビウム

感想

MySQLとの連携もできたので個人的には満足しています。

トランプ想定なので1-13以外の数字が来た場合の処理とか追加したほうがよかったかもなぁと思っています。

余談ですが、このゲーム、名前付いてるんでしょうか。 名前があれば本記事のタイトルも悩まなくよかったんですが......。

Reference