3. Built-in types and what they cost

Each built-in type is a specific data structure with specific costs, and picking the right one is often a 100× decision. Learn what each one is underneath, not just its methods.

Numbers

• int has arbitrary precision: 2**1000 just works. The price is that every int is a heap object of about 28 bytes, not a raw machine word. A list of a million ints uses roughly 8 MB of pointers plus 28 MB of objects; a NumPy int64 array uses 8 MB.
• float is an IEEE 754 64-bit double. 0.1 + 0.2 == 0.30000000000000004, so compare floats with math.isclose. The float32, bfloat16 and float16 types used in AI live in NumPy and PyTorch, not in Python itself.
• Special values: float("inf") and float("nan"). NaN is not equal to itself, so test with math.isnan. A NaN loss spreads silently through training.
• bool is a subclass of int: True + True == 2. That is why sum(x > 0 for x in xs) counts matches.
• Division: / always returns a float. // floors toward minus infinity, so -7 // 2 == -4.

Strings and bytes

• str is an immutable sequence of Unicode code points. len("é") is 1, or 2 if the accent is stored as a separate combining character.
• bytes is an immutable sequence of integers from 0 to 255. Files, networks and byte-level tokenizers see bytes.
• Converting: s.encode("utf-8") gives bytes and b.decode("utf-8") gives text. Always name the encoding: open(path, encoding="utf-8").
• Building strings: strings are immutable, so s += piece in a long loop can become quadratic. Collect pieces in a list and call "".join(parts).
• f-strings: f"{loss:.4f}" formats numbers; f"{x=}" prints x=<value>, handy for debugging.

AI context: characters, bytes and tokens are three different counts. len(text) tells you nothing reliable about token count. Byte-level BPE tokenizers work on UTF-8 bytes, which is one reason non-English text often costs more tokens.

list: a dynamic array of pointers

A list is a contiguous array of references to objects. It over-allocates so that append is amortized O(1). Indexing is O(1); inserting or removing at the front is O(n); x in lst is O(n).

Lists can mix types because they store only pointers. The same fact makes them slow for numbers: each element is a separate boxed object somewhere else in memory, which defeats the CPU cache.

tuple: a fixed record

A tuple is an immutable sequence. It is hashable if its contents are, so it can be a dict key. Use tuples for fixed records such as shapes ((batch, seq_len)) and for multiple return values.

dict: a hash table

A dict maps hashable keys to values with average O(1) lookup, insert and delete. hash(key) picks a slot in a table, and collisions are resolved by probing other slots. The contract that makes this work: objects that compare equal must have equal hashes.

• Insertion order is guaranteed (since 3.7).
• Keys must be hashable: str, int, tuples of hashables, frozenset. Lists, dicts and sets cannot be keys.
• Dicts are everywhere: object attributes (obj.__dict__), module globals, **kwargs, JSON, model.state_dict(), LLM API messages.
• Useful methods: d.get(k, default), d.setdefault(k, []), d | other (merge into a new dict), dict comprehensions.

set and frozenset

A set is a hash table with keys and no values. Membership tests are O(1), and set algebra uses |, &, - and ^. set(items) deduplicates but loses order; list(dict.fromkeys(items)) deduplicates and keeps it.

AI uses: deduplicating a dataset, building a vocabulary, checking for overlap between training and test examples.

The collections module

• deque: O(1) appends and pops at both ends. deque(maxlen=100) gives a sliding window, for example a running average of recent losses.
• defaultdict(list): creates missing keys on first access, so grouping needs no if key in d check.
• Counter: frequency counting. Counter(tokens).most_common(10) is a one-line vocabulary analysis.
• namedtuple: a tuple with named fields. For new code, prefer dataclasses (Part 7).
• OrderedDict: mostly obsolete now that dicts keep order, but move_to_end still makes it the easy way to build an LRU cache.

What each operation costs

Operation	list	dict	set	deque
x in c	O(n)	O(1)	O(1)	O(n)
Read by index or key	O(1)	O(1)	n/a	O(1) at ends, O(n) in middle
Add at the end	O(1) amortized	O(1) average	O(1) average	O(1)
Insert or remove at the front	O(n)	n/a	n/a	O(1)
Delete a given key or value	O(n)	O(1)	O(1)	O(n)

Rule of thumb: if you write if x in some_list inside a loop, you almost certainly wanted a set.

Questions to ask:

• What does this membership test or insert cost as the data grows?
• Is this a million small Python objects that should be one array?
• Is this str or bytes, and which encoding?