MERの日記

リニアサーチとバイナリサーチ

Python, Ishikawa

リニアサーチとバイナリサーチは、一般にはバイナリサーチの方が速いわけだけど、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 使うのもありだなーと思ったりしました。

ツイートする

Permalink | コメント(0) | トラックバック(0) | 02:01