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
- License under
CC BY-NC 4.0
- Copyright issue feedback
me#imzye.me
, replace # with @ - Not all the commands and scripts are tested in production environment, use at your own risk
- No privacy information is collected here
Try iOS App