A data structure organizes data for operations such as lookup, traversal, and storage. In Python, choosing a list, set, dictionary, or array can change both runtime and memory use. Start with the operations the program actually performs, then measure before replacing a familiar container. section 1.4 section 2.6
Repeated membership tests
Put the same 100,000 distinct integers in a list and a set, then time membership tests. Searching for 50,000 took about 455 µs in the list versus 40 ns in the set; searching for an absent 500,000 took about 936 µs versus 28 ns. The difference is not explained by duplicate removal: the containers hold the same number of elements. CPython’s hash-based set supports fast lookup of a known value, while list search examines elements. These are measured results, not a promise of constant-time lookup in every case. section 2.3.3
a_list_range = list(range(100000)) a_set_range = set(a_list_range) %timeit 50000 in a_list_range %timeit 50000 in a_set_range %timeit 500000 in a_list_range %timeit 500000 in a_set_range
Run these `%timeit` tests to compare present and absent membership queries on equally sized containers. section 2.3.3
Match the structure to the query. Sets and dictionary keys suit repeated searches for specific values; an ordered list with bisection is better suited to finding an interval. A fast membership test does not make a set the best choice for every access pattern. section 2.3.3
Account for storage as well as speed. `sys.getsizeof` reports a container’s own size, not the full footprint of objects it refers to. A list of file data, for example, can consume far more memory than the file because its entries are references to Python objects. To estimate a whole structure, traverse its contents, include dictionary keys and values, and track object identities to avoid double-counting. Even that approach has limits for objects supplied by external libraries. section 2.4.1 section 2.4.4
A better data structure may be a low-cost optimization, but there is no universal replacement rule. Profile the workload, compare the relevant operations and memory footprint, and revisit assumptions when Python’s underlying implementations change. section 1.1 section 2.6
