2011-04-07
リニアサーチとバイナリサーチ
リニアサーチとバイナリサーチは、一般にはバイナリサーチの方が速いわけだけど、RubyとかPythonみないな、速くはない言語でどれほど変わるのだろうかと思う。
普通に想像すると、バイナリサーチのほうが速いといっても、0.00001と0.00005秒の差みたいな物なんだろう。
リニアサーチに比べてバイナリサーチはロジックが若干面倒(リニアサーチがシンプルすぎというべきな気もするが)なので、シンプルにリニアサーチしようとおもったら、Python には bisect (http://www.python.jp/doc/2.5/lib/module-bisect.html)という二分探索アルゴリズムのモジュールがあるらしい*1。というわけで、ベンチとってみた。
import timeit setup1 = ''' DATA = range(1000) ''' setup2 = ''' DATA = range(1000) import bisect ''' bench2 = ''' bisect.bisect_left(DATA, 500) ''' bench1 = ''' for value in DATA: if 500 <= value: break ''' if __name__ == '__main__': print timeit.Timer(bench2, setup2).repeat(3, 100000) print timeit.Timer(bench1, setup1).repeat(3, 100000)
1000個の要素から500を探すという、バイナリサーチに有利な比較。
バイナリ [0.090467929840087891, 0.089236974716186523, 0.089040040969848633] リニア [3.5519189834594727, 3.5491249561309814, 3.5511660575866699]
まぁ、当然ですね。
次は1000個の要素から7を探すという、リニアリサーチが得意な比較。
バイナリ [0.099443912506103516, 0.099334001541137695, 0.099302053451538086] リニア [0.074399948120117188, 0.074351787567138672, 0.074512004852294922]
リニアサーチがぎりぎり逃げ切った。まぁ、比較(ループ)回数はほぼ同じだから普通かな。
最後は1000個の要素から993を探すという、リニアサーチが不得意な比較。
バイナリ[0.094233989715576172, 0.094151020050048828, 0.094120025634765625] リニア[7.0629780292510986, 6.9660470485687256, 6.9703299999237061]
バイナリサーチは要素が多ければ多いほど利点が出てくるのだけど、1000個という小数でもコンスタントに速い。
モジュール呼ぶだけなので、コードもシンプル。というわけで、0.00001と0.00005秒の差みたいなもんだろうけど、実装が難しくないので、ソートされたデータの探索なら bisect 使うのもありだなーと思ったりしました。
*1：ちなみに、bisectはぴゅあパイソンモジュールだよ
2011-03-05
共有リポジトリの作り方
これも、何度やっても覚えない系です。
分かる人にはわかると思うので解説なしのメモです。
前提としては、共有するユーザーが全員共有リポジトリのあるサーバ(git.example.com)のアカウントを持っていて、ssh接続でき、なおかつ git グループに属しているものとします。
サーバ側
cd /var/git/repositories/ # リポジトリ用のディレクトリ mkdir etc.git # etc というリポジトリにします (好きな名前にする) cd etc.git git --bare init --shared cd .. chgrp -R git etc.git # リポジトリのグループをgitにする
ローカルとか、ホームディレクトリ等個人の環境で作業する
# 空のリポジトリは clone できないので、なんらかのファイルを登録(push)するための一時的なリポジトリ mkdir ~/etc_tmp cd ~/etc_tmp # 任意のファイルを作成 (clone するために何かのファイルを push する必要がある) touch README # ローカルリポジトリの初期化 git init # remote サーバを登録 git remote add origin ssh://foobar@git.example.com/var/git/repositories/etc.git # ファイルを追加 git add README git commit # この push でリモートリポジトリが空のリポジトリではなくなる git push origin master cd .. # push してファイルが登録され、clone 可能になったので、このリポジトリはもういらない rm -rf ~/etc_tmp # clone して今後はこのリポジトリで作業して commit & push する git clone ssh://foobar@git.example.com/var/git/repositories/etc.git
2011-02-24
appengine な人におすすめのスライド
他人のふんどしエントリーで恐縮です。appengine の一番の肝である、datastoreの設計についての勘所がまとまっています。
デブサミでの発表資料らしい。発表者はgoogleの松尾さん。
2011-02-23
MongoDBを使ってみる その1
MongoDBつかってみました。
brew install mongodb
DB用のディレクトリを作ります。デフォルトだと/data/dbが使われるようです
mkdir /tmp/mongodb
MongoDBサーバーを起動します。上記で作ったディレクトリを--dbpathで指定
mongod --dbpath /tmp/mongodb/
クライアントで接続します
mongo
できました！ためしに保存してみます
> db.foo.save({a:1})
> db.foo.find()
{ "_id" : ObjectId("4d646d1b6d3554285d50ab7f"), "a" : 1 }
動いてるっぽいですねー。
クエリ等かなり強力そうなので結構良さそうです。
大規模なプロダクトでの実績があるか気になるところです。
2011-02-20
Python で「へぇ、そうなんだ」と思ったこと
bool 型が int 型のサブクラス
>>> 1 == True True >>> 0 == False True >>> 2 == True False >>> isinstance(True, int) True >>> isinstance(False, int) True >>> isinstance(1, int) True >>> 1 is True False >>> 0 is False False
