2017-02-24

Golangでcounting BloomFilterを実装してみた

先日実装したBloomFilter に要素の削除ができるようにcounting BloomFilterを実装しました。

概要

単純なBloomFilter では要素を削除することはできません。
BloomFilterへのマッピングが、削除したい特定の要素によるものか、はたまた別の要素によるものか区別することができないためです。

counting BloomFilterでは、BloomFilterにDelete()ができるようにマッピングをbooleanからcountingができるようmulti-bit化しています。
当然、その分空間効率性が犠牲になります。Fanらのpaper のイントロによると、一般的には3-4[bit]で実装するそうなので、3-4倍空間効率が悪くなります。
今回はGolangのprimitive型であるuint8を使用したため、アイデア自体は変わらないですが、一般的なcounting BloomFilterよりも空間効率が劣ります。

実装と結果

gistb38c96069b177b4f64ede336c658b976

要素"2"の削除前後で結果がtrue→falseと変わっていることがわかります。

参考

2017-02-18

Golangの関数リテラルについてメモ書き

A Tour of GoのFunction valuesを読んでいて、色々勘違いしていてわからなくなってしまったので、手を動かしてわかるようになるまでのメモ書きです。

要旨

勘違いしていたのはA Tour of Goの以下の記載についてです。

関数も変数です。他の変数のように関数を渡すことができます。

どうしても関数を変数に渡した際に「戻り値を渡している」と考えていまい、例題が理解できませんでした。

理解に至った考え方は 「関数そのものを変数に渡している」 です。

例: A Tour of GoのFunction values

ここでは関数computeが定義されています。

func compute(fn func(float64, float64) float64) float64 {
    return fn(3, 4)
}

これは

引数: (float64, float64)を引数に、float64を返す関数
戻り値: float64

となる関数です。つまり関数そのものを引数として、変数のように渡すことができます。
A Tour of Goでは「(float64, float64)を引数に、float64を返す関数」であるhypotを定義するとともに、同じ関数型の関数math.Powを引数としてcomputeに渡してあげる例となっています。

fmt.Println(compute(hypot))
fmt.Println(compute(math.Pow))

Reference

2017-02-11

Golangで言語処理100本ノック2015 第2章: UNIXコマンドの基礎

言語処理100本ノック 2015の第2章: UNIXコマンドの基礎の10問です。

10. 行数のカウント

行数をカウントせよ．確認にはwcコマンドを用いよ．

gista7b27f35e5b111f979022b367ef696c4

# wc hightemp.txt
 24  48 813 hightemp.txt

ReadLine()で一行ずつ読み込み、読み終わった時点の行数を出力させました。

11. タブをスペースに置換

タブ1文字につきスペース1文字に置換せよ．確認にはsedコマンド，trコマンド，もしくはexpandコマンドを用いよ．

gist848871be78390be2901e02908051ccc7

# sed 's/\t/ /g' ../data/hightemp.txt
高知県 江川崎 41 2013-08-12
埼玉県 熊谷 40.9 2007-08-16
岐阜県 多治見 40.9 2007-08-16
山形県 山形 40.8 1933-07-25
山梨県 甲府 40.7 2013-08-10
和歌山県 かつらぎ 40.6 1994-08-08
静岡県 天竜 40.6 1994-08-04
山梨県 勝沼 40.5 2013-08-10
埼玉県 越谷 40.4 2007-08-16
群馬県 館林 40.3 2007-08-16
群馬県 上里見 40.3 1998-07-04
愛知県 愛西 40.3 1994-08-05
千葉県 牛久 40.2 2004-07-20
静岡県 佐久間 40.2 2001-07-24
愛媛県 宇和島 40.2 1927-07-22
山形県 酒田 40.1 1978-08-03
岐阜県 美濃 40 2007-08-16
群馬県 前橋 40 2001-07-24
千葉県 茂原 39.9 2013-08-11
埼玉県 鳩山 39.9 1997-07-05
大阪府 豊中 39.9 1994-08-08
山梨県 大月 39.9 1990-07-19
山形県 鶴岡 39.9 1978-08-03
愛知県 名古屋 39.9 1942-08-02

strings.Replace()を使ってもいいかと思いましたが、rune単位で一文字ずつ読み込み、tabだったら変換する方式としました。
ファイル終端の判別は、io.EOFはerror型でruneと比較できないので、NULL文字で判断しています。

12. 1列目をcol1.txtに，2列目をcol2.txtに保存

各行の1列目だけを抜き出したものをcol1.txtに，2列目だけを抜き出したものをcol2.txtとしてファイルに保存せよ．確認にはcutコマンドを用いよ．

gist930b77e110065c0d74170d39dd9e1e85

// 題意に合わせるにはさらにリダイレクトして出力する必要がありますが、さらにcatするのも冗長なので標準出力にしました。

# cut -f 1 ../data/hightemp.txt
高知県
埼玉県
岐阜県
山形県
山梨県
和歌山県
静岡県
山梨県
埼玉県
群馬県
群馬県
愛知県
千葉県
静岡県
愛媛県
山形県
岐阜県
群馬県
千葉県
埼玉県
大阪府
山梨県
山形県
愛知県

# cut -f 2 ../data/hightemp.txt
江川崎
熊谷
多治見
山形
甲府
かつらぎ
天竜
勝沼
越谷
館林
上里見
愛西
牛久
佐久間
宇和島
酒田
美濃
前橋
茂原
鳩山
豊中
大月
鶴岡
名古屋

filepathパッケージで入力と同じディレクトリに出力するようにしました。

13. col1.txtとcol2.txtをマージ

12で作ったcol1.txtとcol2.txtを結合し，元のファイルの1列目と2列目をタブ区切りで並べたテキストファイルを作成せよ．確認にはpasteコマンドを用いよ．

gista6f97b6d6ad9b9e4808fae91095e1d20

# paste ../data/col1.txt ../data/col2.txt
高知県   江川崎
埼玉県   熊谷
岐阜県   多治見
山形県   山形
山梨県   甲府
和歌山県    かつらぎ
静岡県   天竜
山梨県   勝沼
埼玉県   越谷
群馬県   館林
群馬県   上里見
愛知県   愛西
千葉県   牛久
静岡県   佐久間
愛媛県   宇和島
山形県   酒田
岐阜県   美濃
群馬県   前橋
千葉県   茂原
埼玉県   鳩山
大阪府   豊中
山梨県   大月
山形県   鶴岡
愛知県   名古屋

入出力を標準入力から取ってくるところ、filepathを取ってくるところは本質ではないので、やめました。
練習としてはQ12でできたので。
またruneで処理するところもReadLine()などにしてわかりやすくしました。

14. 先頭からN行を出力

自然数Nをコマンドライン引数などの手段で受け取り，入力のうち先頭のN行だけを表示せよ．確認にはheadコマンドを用いよ．

gist25538f623bc1425da5da9507b34823a2

# head -n 10 ../data/hightemp.txt
高知県   江川崎   41  2013-08-12
埼玉県   熊谷  40.9    2007-08-16
岐阜県   多治見   40.9    2007-08-16
山形県   山形  40.8    1933-07-25
山梨県   甲府  40.7    2013-08-10
和歌山県    かつらぎ    40.6    1994-08-08
静岡県   天竜  40.6    1994-08-04
山梨県   勝沼  40.5    2013-08-10
埼玉県   越谷  40.4    2007-08-16
群馬県   館林  40.3    2007-08-16

読み込んだ行数をカウントして、標準入力で受け取った整数になるまでループ回すだけです。

15. 末尾のN行を出力

自然数Nをコマンドライン引数などの手段で受け取り，入力のうち末尾のN行だけを表示せよ．確認にはtailコマンドを用いよ．

gistc953b981cec15f23ef604cf03f473e38

# tail -n 10 ../data/hightemp.txt
愛媛県   宇和島   40.2    1927-07-22
山形県   酒田  40.1    1978-08-03
岐阜県   美濃  40  2007-08-16
群馬県   前橋  40  2001-07-24
千葉県   茂原  39.9    2013-08-11
埼玉県   鳩山  39.9    1997-07-05
大阪府   豊中  39.9    1994-08-08
山梨県   大月  39.9    1990-07-19
山形県   鶴岡  39.9    1978-08-03
愛知県   名古屋   39.9    1942-08-02

ファイルサイズだけを取得できるのであれば、逆から一文字ずつ読む実装のほうが巨大なファイルを読み込む場合にすぐ表示できてよさそうです。
今回は全部の行を読み込み、出力用outputに溜め込み、最後に標準出力させました。
mod演算させておき、output = append(output[i:], output[:i]...)することで順番通りに出力できるのがポイントです。

16. ファイルをN分割する

自然数Nをコマンドライン引数などの手段で受け取り，入力のファイルを行単位でN分割せよ．同様の処理をsplitコマンドで実現せよ．

gist82a113dbf0bcf2436fe80a44532c589d

# split -l 13 ../data/hightemp.txt
# cat xaa
高知県   江川崎   41  2013-08-12
埼玉県   熊谷  40.9    2007-08-16
岐阜県   多治見   40.9    2007-08-16
山形県   山形  40.8    1933-07-25
山梨県   甲府  40.7    2013-08-10
和歌山県    かつらぎ    40.6    1994-08-08
静岡県   天竜  40.6    1994-08-04
山梨県   勝沼  40.5    2013-08-10
埼玉県   越谷  40.4    2007-08-16
群馬県   館林  40.3    2007-08-16
群馬県   上里見   40.3    1998-07-04
愛知県   愛西  40.3    1994-08-05
千葉県   牛久  40.2    2004-07-20
# cat xab
静岡県   佐久間   40.2    2001-07-24
愛媛県   宇和島   40.2    1927-07-22
山形県   酒田  40.1    1978-08-03
岐阜県   美濃  40  2007-08-16
群馬県   前橋  40  2001-07-24
千葉県   茂原  39.9    2013-08-11
埼玉県   鳩山  39.9    1997-07-05
大阪府   豊中  39.9    1994-08-08
山梨県   大月  39.9    1990-07-19
山形県   鶴岡  39.9    1978-08-03
愛知県   名古屋   39.9    1942-08-02

Q10を再利用しました。
書き込み用ファイルのポインタwfpを使いまわしたかったですが、if文の中で再定義しようとするとスコープから外れてしまってつらい感じでした。

N個のファイルを作成するものと勘違いしてやり直しがあったので時間が掛かりました。そのボツの供養

17. １列目の文字列の異なり

1列目の文字列の種類（異なる文字列の集合）を求めよ．確認にはsort, uniqコマンドを用いよ．

gistd7efd041ef928797af814d56bcef28ce

# cut -f 1 ../data/hightemp.txt | sort | uniq
千葉県
和歌山県
埼玉県
大阪府
山形県
山梨県
岐阜県
愛媛県
愛知県
群馬県
静岡県
高知県

必ずしもソートする必要はありませんが、sortパッケージのinterfaceを実装するのをやってみたかったので自作型runeSliceのsortを実装してみました。

18. 各行を3コラム目の数値の降順にソート

各行を3コラム目の数値の逆順で整列せよ（注意: 各行の内容は変更せずに並び替えよ）．確認にはsortコマンドを用いよ（この問題はコマンドで実行した時の結果と合わなくてもよい）．

gist89c20ddb3587c1407c5b1099ff7b1bad

# sort -nk3 ../data/hightemp.txt
千葉県   茂原  39.9    2013-08-11
埼玉県   鳩山  39.9    1997-07-05
大阪府   豊中  39.9    1994-08-08
山形県   鶴岡  39.9    1978-08-03
山梨県   大月  39.9    1990-07-19
愛知県   名古屋   39.9    1942-08-02
岐阜県   美濃  40  2007-08-16
群馬県   前橋  40  2001-07-24
山形県   酒田  40.1    1978-08-03
千葉県   牛久  40.2    2004-07-20
愛媛県   宇和島   40.2    1927-07-22
静岡県   佐久間   40.2    2001-07-24
愛知県   愛西  40.3    1994-08-05
群馬県   上里見   40.3    1998-07-04
群馬県   館林  40.3    2007-08-16
埼玉県   越谷  40.4    2007-08-16
山梨県   勝沼  40.5    2013-08-10
和歌山県    かつらぎ    40.6    1994-08-08
静岡県   天竜  40.6    1994-08-04
山梨県   甲府  40.7    2013-08-10
山形県   山形  40.8    1933-07-25
埼玉県   熊谷  40.9    2007-08-16
岐阜県   多治見   40.9    2007-08-16
高知県   江川崎   41  2013-08-12

3コラム目と指定されているので直書きでも良い気がしましたが、各コラムでソートできるようにしたかったので、Jxckさんの記事を参考にソート条件を可変にしました。
Go1.8ではsort.Sliceが実装されるのでByXXXを書かなくて良くなりそうです。
(ベンチマークを見る限り、速度は犠牲になっているようなので要件に合わせてチューニングが必要そうですが)

19. 各行の1コラム目の文字列の出現頻度を求め，出現頻度の高い順に並べる

各行の1列目の文字列の出現頻度を求め，その高い順に並べて表示せよ．確認にはcut, uniq, sortコマンドを用いよ．

gist4ea5282a6a739f8f3c7e8e0fc954fc91

# cut -f 1 ../data/hightemp.txt | sort | uniq -c | sort -r
      3 群馬県
      3 山梨県
      3 山形県
      3 埼玉県
      2 静岡県
      2 愛知県
      2 岐阜県
      2 千葉県
      1 高知県
      1 愛媛県
      1 大阪府
      1 和歌山県

ファイル内容を読み込んでから構造体に格納したものの、各フィールドを独自型にした結果、コードがひたすら長くなってしまったので微妙な気がします。メンテナンス性も低いのでベストプラクティス的なもの知る必要ありです。。。。
~~A Tour of GoのInterface valuesあたりを早く読めばよかった~~

感想

準備運動から久しく時間が空きましたが、第2章でした。
Go言語の筋トレのつもりでしたが、Linuxコマンドも知らないものが多く、勉強になりました。今回のコードはGithubにも置いてあります。

Reference

2017-02-04

GolangでBloomFilterを実装してみた

2018/02/17追記
Goらしくレシーバを使うようリファクタリングしました。実装が少し変わっていますが、考え方自体は本記事から変わりありません。リファクタリング後の実装は以下のGithubのとおりです。

github.com

前回調べたBloomFilterをGolangで実装してみました。

要素を蓄えるBloomFilterの用意

BloomFilterをサイズm[bit]のboolean配列として用意します。
実装中ではmをsizeという変数にしているので、適宜読み替えてください。今回はBloomFilter型を用意します。

gistf2f5c87d2ca403d6f1b3deacb4d52ab4

使用するハッシュ関数

要素の追加および要素の有無を検証するときに、k個のハッシュ関数を用意する必要があります。今回はハッシュ関数としてMD5を用いることにします。

gist4c6a2e7a9d80775c78c209540a9d90ed

最適なハッシュ関数の数

k個のハッシュ関数と述べましたが、kはどのように決定すればよいのでしょうか。結論からいうと最適なハッシュ関数の数kは以下のように得ることができます。

$k = \frac{m}{n} ln{2} \tag{1}$

ここでnはBloomFilterに蓄える要素の数です。

導出

式(1)は偽陽性確率を最小化するようにkを決定することで得られます。
Wikipedia にも記載されていますが、まずm[bit]の配列において、あるbitを、あるハッシュ関数でマッピングした場合を考えます。そのbitが0(false)のままである確率は以下のようになります。

$\displaystyle 1 - \frac{1}{m} \tag{2}$

k個の独立なハッシュ関数を用いてマッピングしても、そのbitがまだ0(false)のままである確率は、式(2)をk回の独立な試行を繰り返すことになるので以下です。

$\displaystyle \bigl(1 - \frac{1}{m} \bigr)^{k} \tag{3}$

さらに、n個の要素を追加してなお、そのbitが0(false)のままである確率は

$\displaystyle \bigl(1 - \frac{1}{m} \bigr)^{nk} \tag{4}$

です。よってそのbitが1(true)になっている確率は1から式(4)を引けばよいので

$\displaystyle 1 - \bigl(1 - \frac{1}{m} \bigr)^{nk} \tag{5}$

として得られます。ここまでをBloomFilterに要素を蓄え終わった状態と考え、新たな要素が上記までで蓄えたBloomFilterに含まれているかを検証します。
このとき偽陽性確率は、新たな要素に対してk個のハッシュ値を計算し、そのマッピング先が既にすべて1(true)になっている場合です。つまり偽陽性確率は以下のように表されます。

$\displaystyle \Bigl(1 - \bigl(1 - \frac{1}{m} \bigr)^{nk} \Bigr)^{k} \tag{6}$

これを近似すると以下が得られます。

$\displaystyle \bigl(1 - e^{- \frac{kn}{m}} \bigr)^{k} \tag{7}$

上記に対して、m,nを固定してkの極値を求めることで最適なハッシュ関数の数 $k = \frac{m}{n} ln{2}$ を求めることができます。そもそもkはハッシュ関数の数なので整数ですし、離散最適化で考える必要があるような気もしましたが、Adamらの論文でも以下の記載があるので、実装上kを整数で丸めることにしました。

k must be an integer, and a smaller, suboptimal k might be preferred, since this reduces the number of hash functions that have to be computed.

gistcdae885488a6c951035e3aba4c3eed68

Double Hashing法

次に悩むポイントが、k種類のハッシュ関数をどのように用意すればいいのかです。Adamらの素敵な提案によると2つのハッシュ関数 $h_{1}(x), h_{2} (x)$ を用いて新しいハッシュ関数 $g_{i}(x), i = 1, 2, \cdots , k$ を以下のように得ることができます。

$\displaystyle g_{i}(x) = h_{1}(x) + i h_{2}(x) \tag{8}$

今回ハッシュ関数として用いたMD5の戻り値は128[bit]となるので、これを前半後半64[bit]ずつで分けて $h_{1}(x), h_{2} (x)$ とします。
ただし、これをそのままint64の変数として扱おうとすると式(8)を計算する際にoverflowしてしまいます。そこで多倍長計算を行うためにmath/bigパッケージを使用します。
C言語でいうところのGMPライブラリですね。

giste254088e7a699d3955f1ba1d101c13a6

要素の追加

BloomFilterに要素を追加する関数です。

gist6b13fac1db57d676e72bb39d258e6888

追加したい要素からハッシュ値を計算し、それを半分に分けて、Double Hashing法でk個のハッシュ値を求めます。
さらにそれをBloomFilterに蓄えるために、k個のハッシュ値を配列BloomFilterのindexとして、対応する箇所をtrueとしてマッピングします。

要素の検証

BloomFilterに要素が含まれているかを検証する関数です。

gistab1072fe99b8250e0783334a6ea99c7c

Addと同様に、ハッシュ値を前半後半の2つに分けて、Double Hashing法でk個のハッシュ値を求めます。 k個のハッシュ値を配列BloomFilterのindexとして、値がひとつでもfalseであれば、要素は含まれていないと判断します(全部trueのときは偽陽性の可能性あり)。

使い方

[1, 2, 3, 4, 5]をBloomFilterに追加して、要素が含まれているか、検証してみます。

gist24ff41df156b37c624f28d0cb15406b4

確かに偽陽性は起こりうる(上の例だと999のとき)ことがわかります。
一方で、偽陰性はなく、1, 2, 3, 4, 5はすべてtrueになっていることがわかります。

コードはGithubにあげてあります。
ハッシュ関数の計算は並列で行っても問題ないため、goroutineで並列化したものも別ブランチで実装してみました。
goroutineの起動コストもあるらしいので、どっちがいいかは、ちゃんとベンチマークとりたいですね。

最後に

最近データ構造アルゴリズムを実装して遊んでいるので、試すためによさげなデータ・セットが欲しいこの頃です。
(ベンチマーク取るにしても良いデータじゃないと意味なさそう...)

Wikipedia にも載っていますが、要素の削除を可能にしたCounting filterやBloomFilterのリストを作り、scalableにしたBloomier filterなどBloomFilterの亜種がたくさん存在しているようなので、そっちも実装していきたいです。

参考

2017-01-28

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 追記
実装も記事にしました。

参考

2017-01-22

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(n²)
ヒープソート	O(n log n)
挿入ソート	O(n²)
マージソート	O(n log n)
クイックソート	O(n log n)
選択ソート	O(n²)
シェルソート	O(n log n)

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

最後に

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

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

Reference

2017-01-15

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

最後に

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

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

概要

実装と結果

参考

要旨

例: A Tour of GoのFunction values

Reference

10. 行数のカウント

11. タブをスペースに置換

12. 1列目をcol1.txtに，2列目をcol2.txtに保存

13. col1.txtとcol2.txtをマージ

14. 先頭からN行を出力

15. 末尾のN行を出力

16. ファイルをN分割する

17. １列目の文字列の異なり

18. 各行を3コラム目の数値の降順にソート

19. 各行の1コラム目の文字列の出現頻度を求め，出現頻度の高い順に並べる

感想

Reference

要素を蓄えるBloomFilterの用意

使用するハッシュ関数

最適なハッシュ関数の数

導出

Double Hashing法

要素の追加

要素の検証

使い方

最後に

参考

BloomFilterとは

空間効率性

計算時間

セキュリティ

応用先

最後に

参考

ベンチマークの書き方

ハマったところ

ソート対象の初期化漏れ

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

結果

最後に

Reference

背景

どうやってテストするか

テスト結果

最後に

Reference

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