手動実装とライブラリ関数実装の二分検索実行時間テスト

以前に手動で実装し、bisectライブラリで二分検索を実装したのに続き、実行時間の差がどれほど大きいかをテストします.まず装飾器を作って時間を計算します.

def timefunc(repeat_times=1):
    if callable(repeat_times):  # @timefunc
        func = repeat_times
        @functools.wraps(func)
        def wrapper(*args, **kwargs):
            start = time.time()
            func(*args, **kwargs)
            stop = time.time()
            # print(f'time cost: {stop - start:.5f} s')
            return stop - start
        return wrapper
    else:                       # @timefunc(...)
        assert repeat_times >= 1
        def decorator(func):
            @functools.wraps(func)
            def wrapper(*args, **kwargs):
                start = time.time()
                [func(*args, **kwargs) for _ in range(repeat_times)]
                stop = time.time()
                # print(f'average time cost: {(stop - start) / repeat_times:.5f} s')
                return (stop - start) / repeat_times
            return wrapper
        return decorator

これは装飾器の基本的な実装であり、パラメータ付き装飾器とパラメータなし装飾器を区別するためにif-elseのセットを用いた.(自画自賛:D私も前に簡単な文章を書いて装飾器を紹介しました)今、パラメータ付きの装飾器を使って平均実行時間をテストしています.

@timefunc(repeat_times=100)
def test_manual(nums):
    k = random.choice(nums)
    binary_search_manual(nums, k)

@timefunc(repeat_times=100)
def test_bisect(nums):
    k = random.choice(nums)
    binary_search_bisect(nums, k)

回数は暫定100回.そのうちのbinary_search_manual(nums, k)およびbinary_search_bisect(nums, k)は、bisectを用いて二分検索を実現する前の文書を参照する.リスト長を1000000と入力し、次のように実行します.

if __name__ == "__main__":
    nums = list(range(1000000))
    
    t1 = test_manual(nums)
    print(f'average time cost: {t1:.4e} s')
    t2 = test_bisect(nums)
    print(f'average time cost: {t2:.4e} s')

    print(f'difference: {abs(t1-t2):.4e} s')

私のパソコンで実行した結果は次の通りです.

average time cost: 1.0493e-04 s
average time cost: 1.3177e-05 s
difference: 9.1753e-05 s

ライブラリ関数は明らかに速いが、1000000というレベルでは差は大きくなく、結局二分アルゴリズムである.
参考資料:

装飾器-廖雪峰の公式サイト

bisect公式ドキュメント