Skip to content

Python bisect module demo

#!/usr/bin/env python

import random
import timeit
from bisect import bisect_left

size = 10 ** 5
iterations = 1000

eg_data = list(range(size))
eg_to_lookup = [random.randint(0, size) for _ in range(iterations)]


def run_linear(data, to_lookup):
    for index in to_lookup:
        data.index(index)


def run_bisect(data, to_lookup):
    for index in to_lookup:
        bisect_left(data, index)


if __name__ == '__main__':
    baseline = timeit.timeit(stmt='run_linear(eg_data, eg_to_lookup)',
                             globals=globals(), number=10)
    print(f'Linear search takes {baseline:.6f}s')
    comparison = timeit.timeit(stmt='run_bisect(eg_data, eg_to_lookup)',
                               globals=globals(), number=10)
    print(f'Bisect search takes{comparison:.6f}s')
    slowdown = 1 + ((baseline - comparison) / comparison)
    print(f'{slowdown:.1f}x time')

Disclaimer
  1. License under CC BY-NC 4.0
  2. Copyright issue feedback me#imzye.me, replace # with @
  3. Not all the commands and scripts are tested in production environment, use at your own risk
  4. No privacy information is collected here
Try iOS App