おまぬけ活動日誌

● B木の勉強をしたい

B木の勉強と一緒に言語の勉強もしたいことにした。

今度こそプログラミングの基礎を身につけたくて、 「定本 Cプログラマのためのアルゴリズムとデータ構造」 を読み始めた。 B木の実装のリストまで辿りついたのだけれどぜんぜん頭に入ってこない。 どうしようかな。 B木のべんきょーやっぱりC++でやってみっかねえ？それともGoかねえ？体力欲しいやねえ と悩んでいたら、@finalfusionさんから

両方やって比較記事を書く

と素晴しい提案が。 ひとつぶで3度おいしい!というわけでやってみることにしますよ。

3倍大変なのにはまだ気づいていない。

● GoとC++を試してみる環境の整備

Pentium Mのマシンを使いますよ、というわけで ミラーサイトからdebian-7.3.0-i386-netinst.isoをいただいて来ました。 そこからか。

とりあえず追加でインストールしたのは下記。 build-essential firmware.zip fonts-inconsolata git gnome-terminal ibus-skk mercurial vim-nox xfce4

このマシンはCPUもディスクも遅いので、 firefoxでgtk-gnashをdisableしました。 普通のページを閲覧してるだけでCPU持ってかれることがある。 あと、下記の作業中にふと気づいてスワップも使わないことにしました。 /etc/fstabのswapの行をコメントストして、とりあえず、

さて、B木のテストコードが走るところまで進めます。

● [cpp] C++によるB木の実装例

cpp-btreeというのを見つけた。

してREADMEを読みつつ。 cmake、googletest、gflagsが必要とのこと。

cmakeはapt-get installできました。

googletestは、libgtest-devとしてapt-get installできました。Debianすごい。 The Big Blob » Getting started with Google Test (GTest) on Ubuntu によると、ビルドしておく必要があるようです。

gflagsはさすがに無いみたい。 https://code.google.com/p/gflagsから辿って、 schuhschuh/gflags をいただいてきておきます。

Errorとかいう文字がどっばーと表示されて絶望したけど最後には、 All 5 tests passedだって。

で/usr/local以下に、例えば、 /usr/local/include/gflags/gflags.hなどが インストールできたようです。

さて。B木に戻る。

swapいっぱいになって大変に遅い。速いマシンが欲しいなあ。 なんとかバイナリができたようです。

なんかいろんな型の値でいろんな順番に挿入してメモリ効率とかかかった時間とか 測ってくれてるみたい。

これもだねー。

何も表示しないがCPUを85%くらい、メモリを13%くらい使っている。 メモ書きやめたらCPUは98%、メモリは20%に成長。うーん？ と思ったら標準出力のバッファがやっとフラッシュされはじめた。

BM_btree_2048_multimap_string_fwditer 299 3463394BM_btree_256_multimap_string_fwditer 303 3448275BM_stl_multimap_string_fwditer 512 2072747BM_btree_2048_multimap_string_fifo 3173 319424BM_btree_256_multimap_string_fifo 1346 742731BM_stl_multimap_string_fifo 1312 850435BM_btree_2048_multimap_string_mixedaddrem 94078 10849BM_btree_256_multimap_string_mixedaddrem 21541 46634BM_stl_multimap_string_mixedaddrem 11150 98951BM_btree_2048_multimap_string_queueaddrem 87954 13398BM_btree_256_multimap_string_queueaddrem 19815 50847BM_stl_multimap_string_queueaddrem 9136 110738BM_btree_2048_multimap_string_delete 47878 21407BM_btree_256_multimap_string_delete 10585 94642BM_stl_multimap_string_delete 6461 155363BM_btree_2048_multimap_string_fulllookup 3771 272180BM_btree_256_multimap_string_fulllookup 3905 271137BM_stl_multimap_string_fulllookup 4675 221181BM_btree_2048_multimap_string_lookup 4024 272692BM_btree_256_multimap_string_lookup 4142 243902BM_stl_multimap_string_lookup 4054 269541BM_btree_2048_multimap_string_ins

なんか改行がうまくいっていない気がする(上記はブラウザにまかせて改行してもらってますが端末では改行がいっさいありませんでした)けれど、 真夜中すぎにたぶん無事に終了していた。

● [golang] GolangによるB木の実装例

btreeというものを見つけた。 お初mercurialだ!

どーすんだこれ。mainないけど実行ファイルできるのかな？うろうろうろうろ…。 Go for Rubyists - SitePointによると、

For me, Go was the missing link between C++ and Ruby

お。 やっぱりC++とGo一度にべんきょすべきかw と思ったけれど、C++知りませんでした。 golangはじめました - アリ (rebuild.fm仲間だ!) によると、go testというのが使えそう。 golang golang-go golang-srcをapt-get installしておいて、

お。何か進んだ

実行ファイルが作られるというわけじゃないようですね。 もうちょっとGo自体の勉強が必要なようですね。

さて。これでとりあえずC++版とGo版の既存のB木は動いたということで、 Goのツールについても勉強しながら、 これからこれらのコードを眺めながら自分で書いていきたいと思います。 テストは共通のを使えるといいな。