timings for different operations on a list

bisect.md

The bisect module allows fast searches on sorted arrays.

import  bisect
collection = [1, 2, 4, 5, 6]
bisect.bisect(collection, 3)
# Result: 2

This function uses the binary search algorithm that has O(log(N)) running time.

Code	N=10000 (µs)	N=20000 (µs)	N=30000 (µs)	Time
list.index(a)	87.55	171.06	263.17	O(N)
index_bisect(list, a)	3.16	3.20	4.71	O(log(N))

deques.md

Code	N=10000 (µs)	N=20000 (µs)	N=30000 (µs)	Time
list.pop()	0.50	0.59	0.58	O(1)
list.pop(0)	4.20	8.36	12.09	O(N)
list.append(1)	0.43	0.45	0.46	O(1)
list.insert(0, 1)	6.20	11.97	17.41	O(N)

Deques, in addition to pop and append, expose the popleft and appendleft methods that have O(1) running time:

Code	N=10000 (µs)	N=20000 (µs)	N=30000 (µs)	Time
deque.pop()	0.41	0.47	0.51	O(1)
deque.popleft()	0.39	0.51	0.47	O(1)
deque.append(1)	0.42	0.48	0.50	O(1)
deque.appendleft(1)	0.38	0.47	0.51	O(1)

The efficiency gained by the appendleft and popleft operations comes at a cost: accessing an element in the middle of a deque is a O(N) operation

Code	N=10000 (µs)	N=20000 (µs)	N=30000 (µs)	Time
deque[0]	0.37	0.41	0.45	O(1)
deque[N -  1]	0.37	0.42	0.43	O(1)
deque[int(N / 2)]	1.14	1.71	2.48	O(N)

list.md

Code	N=10000 (µs)	N=20000 (µs)	N=30000 (µs)	Time
list.pop()	0.50	0.59	0.58	O(1)
list.pop(0)	4.20	8.36	12.09	O(N)
list.append(1)	0.43	0.45	0.46	O(1)
list.insert(0, 1)	6.20	11.97	17.41	O(N)