Performance measures how efficiently a program or function processes data and responds to requests. Compare alternatives by timing representative operations, then explain differences through time complexity such as O(1) and O(n). section 3.5.1 section 7.3
Choose data structures and measurement techniques according to the operation your application performs:
- Use sets for membership checks: hash-table lookup remains approximately O(1), while searching a list grows linearly with its length. section 4.5.1
- Use deques for FIFO queues: removing the first list item requires shifting remaining items and costs O(n), whereas deque removal is O(1). section 4.5.2
- Use decorators to apply shared timing behavior across many functions instead of repeating start-and-end timing code. section 7.3
Compare list and set lookup
Run repeated membership tests with timeit while increasing the collection size. Set timings stay near the same magnitude, whereas list timings increase substantially; at 100,000 items, the displayed list lookup is much slower than the set lookup. section 3.5.1
Listing 3.7 Comparing data retrieval speed between lists and sets
from timeit import timeit
for count in [10, 100, 1000, 10000, 100000]:
setup_str = f"""from random import randint; n = {count};
numbers_set = set(range(n));
numbers_list = list(range(n))""" #1
stmt_set = "randint(0, n-1) in numbers_set" #2
stmt_list = "randint(0, n-1) in numbers_list" #3
t_set = timeit(stmt_set, setup=setup_str, number=10000) #4
t_list = timeit(stmt_list, setup=setup_str, number=10000) #4
print(f"{count: >6}: {t_set:e} vs. {t_list:e}")
Inspect the complete timeit comparison, including setup, repeated membership statements, collection sizes, and printed timings. section 3.5.1
