Python - Lists(in operator, sorted list, bisection search(binary search))

Think Python

開発環境

• OS X El Capitan - Apple (OS)
• Emacs (Text Editor)
• Python 3.5 (プログラミング言語)

Think Python (Allen B. Downey (著)、 O'Reilly Media)のChapter 10.(Lists)のExercises 10-10.(No. 2366)を取り組んでみる。

Exercises 10-10.(No. 2366)

コード(Emacs)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import math
import time
import random
import bisect


def words2list(filename):
    out = []
    with open(filename) as f:
        for word in f:
            word = word.strip()
            out.append(word)
    return out


def in_bisect(elems, val):
    i = 0
    j = len(elems)
    while i < j:
        middle = math.floor((i + j) / 2)
        if elems[middle] == val:
            return middle
        if elems[middle] > val:
            j = middle
        else:
            i = middle + 1
    return None


def in_bisect_module(elems, val):
    i = bisect.bisect_left(elems, val)
    if elems[i] == val:
        return i
    return None

if __name__ == '__main__':
    filename = 'words.txt'
    words = words2list(filename)
    words.sort()
    for word in [random.choice(words) for _ in range(10)] + ['abcde']:
        print('in operator')
        t = time.time()
        res = word in words
        t1 = time.time() - t
        print('{0}秒: {1}'.format(t1, res))
        print('in_bisect')
        t = time.time()
        i = in_bisect(words, word)
        t2 = time.time() - t
        print('{0}秒: {1}'.format(t2, i))
        print('bisect module, bisect_left function')
        t = time.time()
        i = in_bisect_module(words, word)
        t3 = time.time() - t
        print('{0}秒: {1}'.format(t3, i))
        print('in operator - in_bisect = {0}'.format(t1 - t2))
        print('in_bisect - in_bisect_module = {0}'.format(t2 - t3))

入出力結果(Terminal, IPython)

$ ./sample10.py
in operator
0.007658958435058594秒: True
in_bisect
0.00010585784912109375秒: 88566
bisect module, bisect_left function
1.5974044799804688e-05秒: 88566
in operator - in_bisect = 0.0075531005859375
in_bisect - in_bisect_module = 8.988380432128906e-05
in operator
0.005478858947753906秒: True
in_bisect
6.604194641113281e-05秒: 77359
bisect module, bisect_left function
1.5020370483398438e-05秒: 77359
in operator - in_bisect = 0.0054128170013427734
in_bisect - in_bisect_module = 5.1021575927734375e-05
in operator
0.0024268627166748047秒: True
in_bisect
5.698204040527344e-05秒: 29378
bisect module, bisect_left function
1.0967254638671875e-05秒: 29378
in operator - in_bisect = 0.0023698806762695312
in_bisect - in_bisect_module = 4.601478576660156e-05
in operator
0.001416921615600586秒: True
in_bisect
4.506111145019531e-05秒: 21045
bisect module, bisect_left function
1.0013580322265625e-05秒: 21045
in operator - in_bisect = 0.0013718605041503906
in_bisect - in_bisect_module = 3.504753112792969e-05
in operator
0.004530906677246094秒: True
in_bisect
7.605552673339844e-05秒: 60326
bisect module, bisect_left function
1.5020370483398438e-05秒: 60326
in operator - in_bisect = 0.004454851150512695
in_bisect - in_bisect_module = 6.103515625e-05
in operator
0.0011467933654785156秒: True
in_bisect
4.00543212890625e-05秒: 14060
bisect module, bisect_left function
1.1920928955078125e-05秒: 14060
in operator - in_bisect = 0.0011067390441894531
in_bisect - in_bisect_module = 2.8133392333984375e-05
in operator
0.007181882858276367秒: True
in_bisect
7.104873657226562e-05秒: 88138
bisect module, bisect_left function
1.5020370483398438e-05秒: 88138
in operator - in_bisect = 0.0071108341217041016
in_bisect - in_bisect_module = 5.602836608886719e-05
in operator
0.005607128143310547秒: True
in_bisect
6.4849853515625e-05秒: 68332
bisect module, bisect_left function
1.4066696166992188e-05秒: 68332
in operator - in_bisect = 0.005542278289794922
in_bisect - in_bisect_module = 5.078315734863281e-05
in operator
0.007380008697509766秒: True
in_bisect
7.295608520507812e-05秒: 98799
bisect module, bisect_left function
1.5020370483398438e-05秒: 98799
in operator - in_bisect = 0.0073070526123046875
in_bisect - in_bisect_module = 5.793571472167969e-05
in operator
0.007649898529052734秒: True
in_bisect
6.890296936035156e-05秒: 85575
bisect module, bisect_left function
1.5020370483398438e-05秒: 85575
in operator - in_bisect = 0.007580995559692383
in_bisect - in_bisect_module = 5.3882598876953125e-05
in operator
0.008687019348144531秒: False
in_bisect
6.794929504394531e-05秒: None
bisect module, bisect_left function
1.4066696166992188e-05秒: None
in operator - in_bisect = 0.008619070053100586
in_bisect - in_bisect_module = 5.3882598876953125e-05
$