--- title: 'Data Structures and Functional Tools' source: 'https://academia.sh/en/courses/python-data-structures' language: en updated: '2026-08-17T04:42:16+00:00' license: 'CC BY-SA 4.0' lessons: 16 outcomes: - 'Chooses the built-in collections by their cost and meaning' - 'Builds memory-friendly streams with generators and iterators' - 'Wraps behavior reusably with decorators' --- # Data Structures and Functional Tools Two forms that give the same result can create the same number of objects but hold a different number; the course measures collections, lazy streams, and the module system through objects created, objects shared, and comparisons made. ## Collections The costs of a mutable sequential collection, the guarantee immutability brings, key-value mapping and ordering behavior, set operations, specialized containers, and what slicing copies versus shares. ### Lists Source: https://academia.sh/en/courses/python-data-structures/lists A list holds not the items but the links to them; putting a thousand items in creates 1000 objects but binding the list to a second name creates 0, appending the same item five times creates 1, and only three of eight growth forms build a new container. The Python Fundamentals course spent sixteen lessons measuring a single claim: syntax is an abbreviation, and every form of it calls a specific special method. The distinction it left at its close was this: **using a protocol and writing a protocol are separate things.** The object measured there was a fictional one; it descended from no built-in collection, and the only reason it could enter a `for` loop was that it had defined the relevant methods. In this course, the language's own containers carry the same protocols. They too define the same methods, but no longer for demonstration — for real data. And with real data, the question changes: not what a container **can do**, but what it **costs**. This is this lesson's question — when a list is built, how many objects come into existence, how many of them are the list's own product, and how many of them does the list keep alive? #### What a Container Holds A **list** does not **contain** its items. It holds an ordered sequence of slots, and every slot is a link to an object. This distinction is not specific to Python, it is a direct consequence of the object model: binding a value to a name does not copy the object, it gives it one more name. That assignment is a **binding**, the `is`/`==` distinction, and the alias concept were already established in the Programming Fundamentals course and are not repeated here. What's new is that the same binding can be made **to a slot, not just a name**. The consequence: every operation that grows a list increases the slot count, but it may not increase the object count. The same object can sit in five slots; the list is then five long and holds a single object. The structural theory of ordered containers — array, dynamic array, linked list, growth rate — was built in the Data Structures course and is not repeated here. That built the **mechanism**; here, what's measured is which container Python delivers that mechanism through, and what it costs in **objects**. #### The Shared Setup: An Item That Counts Its Own Creation A single class is enough for the measurement. `Item` increments a shared counter by one on every creation; it does nothing else. To know how many objects an operation creates, resetting the counter, doing the operation, and reading the counter is enough. The setup is its own oracle: creation is known because the object counts itself, sharing is known because `is` shows it. Three numbers are written separately throughout the course — objects **created**, slots **held**, and how many of them go to **distinct** objects. An object's identity is never printed as a number anywhere. Whether two slots point to the same object is tested only with `is`; the distinct-object count is the sum of these tests. - **CO1** — The counter counts only `Item` creation; the list, tuple, or another container itself is not counted. Container count is read separately, through an identity test. - **CO2** — In every row, the counter resets **right before** the operation; what's measured is only what that row creates. - **CO3** — The distinct-object count is found through `is` comparisons; no identity value is printed, and no further inference about identity is drawn from a number. - **CO4** — The thousand-item measurement tests not the list's growth behavior but only the count of objects created; growth class is the subject of the Algorithms course and is not measured here. - **CO5** — In the multiplication measurement, the multiplied list is **single-item**; this makes the difference between duplicating slots and duplicating objects visible on its own. ```python """A list is a container: it holds slots, it does not materialize items itself.""" COUNTER = {"created": 0} class Item: """An item that counts every time one is created.""" def __init__(self, value): COUNTER["created"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): COUNTER["created"] = 0 def created(): return COUNTER["created"] def distinct(container): """Count of identity-distinct objects. Identity is tested with `is`, never printed as a value.""" unique = [] for x in container: if not any(x is y for y in unique): unique.append(x) return len(unique) N = 1000 print(f"{'operation':<36s}{'created':>9s}{'slots':>7s}{'distinct objects':>18s}") reset() lst = [] for i in range(N): lst.append(Item(i)) print(f"{'putting a thousand items in a list':<36s}{created():>9d}{len(lst):>7d}" f"{distinct(lst):>18d}") reset() alias = lst print(f"{'binding the list to a second name':<36s}{created():>9d}" f"{len(alias):>7d}{distinct(alias):>18d}") reset() single = Item(0) manual = [single, single, single, single, single] print(f"{'appending the same item five times':<36s}{created():>9d}{len(manual):>7d}" f"{distinct(manual):>18d}") reset() product = [single] * 5 print(f"{'multiplying a one-item list by five':<36s}{created():>9d}" f"{len(product):>7d}{distinct(product):>18d}") print() print(f"alias is lst -> {alias is lst} | " f"product[0] is product[4] -> {product[0] is product[4]} | " f"product[0] is single -> {product[0] is single}") print(f"lst[0] is lst[1] -> {lst[0] is lst[1]}") ``` ``` operation created slots distinct objects putting a thousand items in a list 1000 1000 1000 binding the list to a second name 0 1000 1000 appending the same item five times 1 5 1 multiplying a one-item list by five 0 5 1 alias is lst -> True | product[0] is product[4] -> True | product[0] is single -> True lst[0] is lst[1] -> False ``` #### What the Four Rows Say The first row is as expected: putting in a thousand items creates **1000** objects, holds **1000** slots, and all of them are distinct objects. But what creates these 1000 objects is **not the list**. The `Item(i)` call produced them; the list only held the slots. The same thousand objects could have been created without ever being put in a list, and the counter would still show 1000. The second row proves this: binding the same list to a second name creates **0** objects. The slot count does not change, the distinct-object count does not change, only the number of names pointing to the object increases by one — and `alias is lst` confirms it. Passing a thousand-item list to a function is the same thing, and it costs the same: **zero**. The third row shows the distinction in reverse. There are five slots, but objects created is **1** and distinct objects is **1**. The list is five long, holding a single object. The fourth row produces the same result through the syntax itself: `[single] * 5` creates nothing — **0** — and all five slots go to the same object. Multiplication duplicates slots, not objects. The last two lines give identity tests. `product[0] is product[4]` is **True**: the slots multiplication produced share the same object. `lst[0] is lst[1]` is **False**: in the thousand-item list, every slot goes to a distinct object, because each one came from a separate `Item(i)` call. Both lists are five or a thousand long; what determines the difference is not length, it is **where** the slots point. #### Forms of Growing There is more than one way to write growing a list, and they do not all give the same length or the same container. In the Python Fundamentals course, the `n + m` versus `n += m` distinction was measured by **which method they call**: the first `__add__`, the second `__iadd__`. What's measured here is how many containers the same distinction creates. The second measurement lines up eight forms side by side and asks each three questions: how many new items were created, did the result stay **the same container**, and how many slots go to an **already existing** object. - **CO6** — All eight forms start from a **freshly built** list of the same five-item pool; the pool's items are created before the measurement, and the counter resets before each form. - **CO7** — The "same container" column is an `is` comparison between the reference held before the operation and the result; container count is not printed, only sameness is tested. - **CO8** — The "slots to old objects" column is found by testing each slot in the result with `is` against an object in the pool or the extra list. - **CO9** — The sort measurement is done with a **key function**; no comparison method is added to the item class, so the counting order does not change. How many comparisons the sort does is not measured in this lesson. ```python """Forms of growing a list: which build a new container, which grow the existing one.""" COUNTER = {"created": 0} class Item: def __init__(self, value): COUNTER["created"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): COUNTER["created"] = 0 def created(): return COUNTER["created"] def value(o): return o.value POOL = [Item(i) for i in (3, 1, 4, 1, 5)] EXTRA = [Item(i) for i in (9, 2, 6)] OLD = POOL + EXTRA def append_end(a): a.append(Item(0)) return a def insert_start(a): a.insert(0, Item(0)) return a def extend_list(a): a.extend(EXTRA) return a def concat(a): return a + EXTRA def inplace_concat(a): a += EXTRA return a def multiply(a): return a * 2 def sort_new(a): return sorted(a, key=value) def sort_inplace(a): a.sort(key=value) return a FORMS = (("a.append(new)", append_end), ("a.insert(0, new)", insert_start), ("a.extend(b)", extend_list), ("a = a + b", concat), ("a += b", inplace_concat), ("a = a * 2", multiply), ("a = sorted(a, ...)", sort_new), ("a.sort(...)", sort_inplace)) print(f"{'form':<20s}{'new items':>10s}{'same container':>16s}{'slots':>7s}" f"{'slots to old objects':>22s}") for label, op in FORMS: a = list(POOL) before = a reset() result = op(a) old_count = sum(1 for x in result if any(x is y for y in OLD)) print(f"{label:<20s}{created():>10d}{str(result is before):>16s}" f"{len(result):>7d}{old_count:>22d}") ``` ``` form new items same container slots slots to old objects a.append(new) 1 True 6 5 a.insert(0, new) 1 True 6 5 a.extend(b) 0 True 8 8 a = a + b 0 False 8 8 a += b 0 True 8 8 a = a * 2 0 False 10 10 a = sorted(a, ...) 0 False 5 5 a.sort(...) 0 True 5 5 ``` #### Same Length, Different Cost The "new items" column is **0** in six of the eight rows. Only `append` and `insert` create one object each, from the `Item(0)` call written to be appended. The remaining six forms do not produce a single item: all of them open **new slots** pointing to existing objects, or rearrange existing slots. The last column confirms this row by row — every slot, except the freshly appended item, goes to an object created before the measurement. The real distinction is in the "same container" column. `a.extend(b)` and `a = a + b` give the same eight-item result, but one grows the existing container, the other builds a **new container** and binds the name to it. `a += b`, despite its name, does not add, it extends: the result is **the same container**. In the Python Fundamentals course, these two were counted as calling separate special methods; the number here is that call's result. For the difference to be observable, another name bound to the list is enough: written as `a += b`, that name sees the lengthened list too; written as `a = a + b`, it stays on the old five-item list. `sorted` and `sort` repeat the same pair on the sorting side. Both produce **0** new items, and both results have **5** slots; the difference is that one returns a new container while the other rearranges the existing one in place. `sort` does not return a list, it returns `None` — because there is no new container to return. One thing is **outside** this table and cannot be found by looking at it: `append` and `insert(0, ...)` give the same numbers, yet what they do is not the same. Inserting at the front requires shifting every slot after it, appending at the end does not. This difference does not show up in the object count, because shifting does not create objects — it only rewrites slots. The growth class of shifting was built in the Algorithms course and is not repeated here; on the axis this lesson measures, the two forms really are equal. #### What Deleting Releases The insertion side showed that a container does not create objects. The deletion side shows the flip side: a container does not **destroy** objects either. Deletion operations only close a slot; whether the object keeps living is decided by other names and other slots still bound to it. The third measurement empties a list with four separate forms and checks, at every step, a second container bound to the same item. - **CO10** — The measurement proceeds **sequentially** on a single list; every row continues from the state the previous one left, so slot counts go down as a result. - **CO11** — The second container is built at the start of the measurement and is **never touched** throughout it; any change to it could only have come from the first container. - **CO12** — Deletion that looks at equality **falls back to identity**, since the item class defines no equality; this lesson does not measure with an item that defines equality. ```python """Deleting does not destroy an object, it breaks a link. A shared item stays in the other container.""" COUNTER = {"created": 0} class Item: def __init__(self, value): COUNTER["created"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): COUNTER["created"] = 0 def created(): return COUNTER["created"] reset() a = [Item(i) for i in range(5)] held = a[2] c = [a[0], a[2]] setup_count = created() print(f"{'operation':<26s}{'created':>9s}{'a slots':>9s}{'c slots':>9s}" f"{'c[1] is held':>14s}") print(f"{'building with five items':<26s}{setup_count:>9d}{len(a):>9d}{len(c):>9d}" f"{str(c[1] is held):>14s}") def pop_end(): a.pop() def del_start(): del a[0] def remove_eq(): a.remove(held) def clear_all(): a.clear() for label, op in (("a.pop()", pop_end), ("del a[0]", del_start), ("a.remove(held)", remove_eq), ("a.clear()", clear_all)): reset() op() print(f"{label:<26s}{created():>9d}{len(a):>9d}{len(c):>9d}" f"{str(c[1] is held):>14s}") print() print(f"item still held after a is empty: {held} | c: {c}") ``` ``` operation created a slots c slots c[1] is held building with five items 5 5 2 True a.pop() 0 4 2 True del a[0] 0 3 2 True a.remove(held) 0 2 2 True a.clear() 0 0 2 True item still held after a is empty: Item(2) | c: [Item(0), Item(2)] ``` All four deletion forms create **0** objects — that was expected. What they actually say is in the two right columns. While the first container's slot count drops from five to zero, the second container's stays fixed at **2**, and `c[1] is held` is **True** in every row. Even after the first list is completely empty, the shared item can still be read: the last row prints `Item(2)`. The rule that follows: **deleting from a container breaks that container's link to the object; not the object itself.** The object stays as long as another name or another slot remains bound to it. Emptying a thousand-item list does not mean those thousand objects become free — if some of the items sit in another container, they keep sitting there. What a container "holds" is therefore one of the three numbers measured: objects created says who did the work, slots held says the container's size, and sharing says what deleting actually released. Deletion that looks at equality adds one detail. `remove` finds a slot not by identity but by **equality**; since the item class in this measurement defines no equality, equality falls back to identity here, and the two criteria give the same result. With an item that defines equality, the two would diverge: `remove` would delete the **first** slot that looked equal, not the object actually held. #### Summary - A list does not contain its items; every slot is a link to an object. Putting in a thousand items creates **1000** objects, binding the list to a second name creates **0**. - Slot count and object count are separate numbers: appending the same item five times gives **5** slots and **1** distinct object, while `[single] * 5` creates **0** objects and binds five slots to the same object. - Of the eight forms of growing, only `append` and `insert` create a new item; the remaining six only open slots, and all those slots go to already existing objects. - `a = a + b`, `a = a * 2`, and `sorted` build a new container; `extend`, `a += b`, and `sort` mutate the existing container in place — same length, different container. - Object count does not show every difference: `append` and `insert(0, ...)` are equal on this axis, because shifting slots does not create objects. #### Next Step Every measurement in this lesson rested on the list being **mutable**: a slot could be added, deleted, rearranged. What, then, does a container gain if it allows none of these? The next lesson repeats the same measurements on an immutable ordered container and asks two questions: which operation does immutability actually make impossible, and what capability does the container gain in exchange for that impossibility? One end of the answer will show up in something a list cannot do — being another container's **key**. ### Tuples Source: https://academia.sh/en/courses/python-data-structures/tuples Three of six operations fail on a tuple with an exception, but the operation that mutates an inner item still passes on a tuple; immutability is one layer deep, and in exchange the container gains the capability to be a key, as seen in three of five candidates. Every measurement in the previous lesson rested on the list being mutable: a slot could be added, deleted, rearranged. Objects created was zero in most forms, because the list only rearranged slots. This lesson repeats the same slots in an **immutable** container. A **tuple** is also an ordered sequence of slots, but once built, its slots cannot be rewritten. The question has two countable parts: which operation does immutability actually make impossible, and what capability does the container gain in exchange? #### What Immutability Closes Off The concept of immutability itself is not this course's subject. The distinction between a mutable and an immutable object was built in the Programming Fundamentals course; the Software Design and Architecture Principles course took up immutability as a **design technique** eliminating shared state. Neither repeats here. What's measured is narrower and more concrete: when the same operations run on both containers, **which lines pass, which fail with an exception.** Where the distinction stands has to be said up front, since the measurement looks exactly there. A tuple protects **its own slots**. It cannot interfere with the objects those slots point to — those are separate objects, subject to their own rules. A tuple's guarantee is therefore not "the contents do not change" but **"which object I'm looking at does not change."** - **CO13** — Both containers try all six operations in the **same order**, each with a freshly built container from the same values. - **CO14** — The result column takes one of three values: if it passed, whether the result is **the same container** or a **new container**; if not, the **class name** of the exception raised. - **CO15** — "Same container" is an `is` comparison against the reference held before the operation. - **CO16** — Sorting uses a **key function**; no comparison method is added to the item class, so counting order does not change. - **CO17** — The line mutating an inner item never touches the container itself; it only writes to a field on the object a slot points to. ```python """Same six operations on a list and a tuple: what does immutability actually make impossible.""" COUNTER = {"created": 0} class Item: def __init__(self, value): COUNTER["created"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): COUNTER["created"] = 0 def created(): return COUNTER["created"] def value(o): return o.value POOL = [Item(i) for i in (3, 1, 4)] def overwrite_slot(k): k[0] = Item(9) return k def append_end(k): k.append(Item(9)) return k def delete_slot(k): del k[0] return k def inplace_concat(k): k += type(k)((Item(9),)) return k def mutate_inner(k): k[0].value = 9 return k def sort_new(k): return sorted(k, key=value) OPERATIONS = (("k[0] = new", overwrite_slot), ("k.append(new)", append_end), ("del k[0]", delete_slot), ("k += (new,)", inplace_concat), ("k[0].value = 9", mutate_inner), ("sorted(k, ...)", sort_new)) print(f"{'operation':<18s}{'in list':<16s}{'in tuple'}") for label, op in OPERATIONS: row = [] for kind in (list, tuple): k = kind(Item(o.value) for o in POOL) before = k try: result = op(k) row.append("same container" if result is before else "new container") except Exception as e: row.append(type(e).__name__) print(f"{label:<18s}{row[0]:<16s}{row[1]}") print() tup = tuple(POOL) reset() bigger = tup + (Item(9),) print(f"appending to tuple: created {created()} | old slots {len(tup)} -> " f"new slots {len(bigger)}") print(f"bigger is tup -> {bigger is tup} | " f"bigger[0] is tup[0] -> {bigger[0] is tup[0]}") print() print(f"reading tup[0].value: {tup[0].value}") tup[0].value = 9 print(f"after mutating the inner item: {tup[0].value} | " f"tup[0] is POOL[0] -> {tup[0] is POOL[0]}") ``` ``` operation in list in tuple k[0] = new same container TypeError k.append(new) same container AttributeError del k[0] same container TypeError k += (new,) same container new container k[0].value = 9 same container same container sorted(k, ...) new container new container appending to tuple: created 1 | old slots 3 -> new slots 4 bigger is tup -> False | bigger[0] is tup[0] -> True reading tup[0].value: 3 after mutating the inner item: 9 | tup[0] is POOL[0] -> True ``` #### Three Rows Fail, Three Pass Three of the six operations fail on a tuple with an exception, three pass. The three that fail all tried the same thing: **rewriting, adding, or deleting a slot.** How they fail differs. Writing to a slot and deleting one give `TypeError` — these spellings mean something on a tuple too, but it does not support that meaning. Appending, though, gives `AttributeError`: there **is no** `append` method on a tuple. The first says "I cannot," the second says "I know no such thing." Two of the three passing rows already did not change the container. `sorted` gives a **new container** on both, since it always returns a new list and never touches the source. `k += (new,)` sits right in the middle: **same container** on the list, **new container** on the tuple. The syntax is the same, the result looks the same, but one extends the existing container and the other builds a new one and binds the name to it. Because a tuple is immutable, growing it "in place" is not an extension there, it is a **rebuild**. The numbers in the middle give the bill: created is **1**, the appended item itself. The container grows — three slots to four — but the three old objects inside it are not recreated. `bigger is tup` is **False**, so the container really is new; but `bigger[0] is tup[0]` is **True**, so the item is old. Growing a tuple by appending one item a thousand times means building a thousand containers, not copying the objects inside it a thousand times. The last two lines are this lesson's most critical measurement. `k[0].value = 9` **passes** on a tuple — without any warning. The tuple protected its own slot: it still points to the same object, and `tup[0] is POOL[0]` confirms it. But that object's **inside** changed; the value read was **3**, then became **9**. This means **immutability is one layer deep**: a container's guarantee is limited to which object its slots point to, not the state of those objects. #### What Immutability Buys A capability opens up in exchange for the three operations closed off. An object being **hashable** means a fixed **hash value** can be computed from it, one that stays unchanged for the object's whole lifetime. A container whose slots can be rewritten cannot make that promise: when it changed, its hash value would change too, and the object would get lost wherever it had been placed. A tuple can make that promise — but only if what's inside it can too. - **CO18** — Hashability is tested directly: taking the hash value is attempted, and the exception's class name is written. **The hash value is never printed**; what's measured is whether it could be taken, not the value. - **CO19** — Whether it can be a key is a separate column, tested by building a single-entry mapping; the two columns confirm each other. - **CO20** — In the multiple-return measurement, the function returns **already existing** items, so only the cost of the return and the unpacking themselves is counted. - **CO21** — Created count during unpacking is found by subtracting the count at return time from the count after. ```python """What a tuple gains: being usable as a key and carrying a multiple return value.""" COUNTER = {"created": 0} class Item: def __init__(self, value): COUNTER["created"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): COUNTER["created"] = 0 def created(): return COUNTER["created"] CANDIDATES = (("(2031, 7)", (2031, 7)), ("[2031, 7]", [2031, 7]), ("((2031, 7), (2032, 1))", ((2031, 7), (2032, 1))), ("(2031, [7])", (2031, [7])), ("'north'", "north")) print(f"{'candidate':<24s}{'hashable':<16s}{'can be a key'}") for label, x in CANDIDATES: try: hash(x) h = "yes" except TypeError as e: h = type(e).__name__ try: {x: 0} a = "yes" except TypeError as e: a = type(e).__name__ print(f"{label:<24s}{h:<16s}{a}") RECORD = {(2031, 7): "slope", (2031, 8): "north", (2032, 1): "summary"} print() print(f"dict keyed by tuple: {len(RECORD)} entries | " f"RECORD[(2031, 8)] -> {RECORD[(2031, 8)]!r}") POOL = [Item(i) for i in (3, 1, 4)] def triple(): return POOL[0], POOL[1], POOL[2] reset() result = triple() return_created = created() a, b, c = result unpack_created = created() print() print(f"return container type {type(result).__name__} | slots {len(result)} | " f"created on return {return_created} | created on unpack " f"{unpack_created - return_created}") print(f"a is POOL[0] -> {a is POOL[0]} | c is POOL[2] -> {c is POOL[2]}") reset() x, y = POOL[0], POOL[1] x, y = y, x print(f"swapping two names: created {created()} | " f"x is POOL[1] -> {x is POOL[1]}") reset() head, *middle = POOL print(f"starred unpacking: created {created()} | middle is a " f"{type(middle).__name__} with {len(middle)} slots | " f"middle[0] is POOL[1] -> {middle[0] is POOL[1]}") ``` ``` candidate hashable can be a key (2031, 7) yes yes [2031, 7] TypeError TypeError ((2031, 7), (2032, 1)) yes yes (2031, [7]) TypeError TypeError 'north' yes yes dict keyed by tuple: 3 entries | RECORD[(2031, 8)] -> 'north' return container type tuple | slots 3 | created on return 0 | created on unpack 0 a is POOL[0] -> True | c is POOL[2] -> True swapping two names: created 0 | x is POOL[1] -> True starred unpacking: created 0 | middle is a list with 2 slots | middle[0] is POOL[1] -> True ``` #### Three of Five Candidates Pass The table shows hashability looks not at the container but at **the container as a whole**. A pair of numbers passes, a nested tuple passes too — because everything inside it is hashable as well. A list fails, as expected. The real row is the fourth: **a tuple carrying a list fails too**, even though the container itself is immutable. A tuple's hash value is computed from the hash values inside it, and if one of them cannot give one, the tuple cannot either. This is the second face of the previous section's finding. There, immutability was one layer deep; here, the language is seen to **know** it. A tuple gives its guarantee only to the extent its contents give it too, and when they cannot, it loses the capability to be a key. The two columns matching is not coincidence: a mapping's condition for being a key is exactly that a hash value can be taken. The three measurements below count a tuple's invisible use. When a function returns three comma-separated values, a **tuple** is what comes out — not a separate syntax, just the parenthesis-free spelling of building one. Created on return is **0**, created on unpacking is **0**. The function packed up three objects and handed them over, the assignment bound three names to those objects; no copy came out anywhere, confirmed by `a is POOL[0]`. Swapping two names is the shortest form of the same mechanism: the right side builds a tuple, the left side unpacks it, items created **0**. Starred unpacking adds one detail — the container collecting the remaining slots is not a tuple, it is a **list**, and its slots still go to the old objects. A multiple return value is cheap for this reason: what gets carried is not the objects, it is the links to them. #### How a Key Is Found That a tuple can be a key was measured; how the key is **found** was not. This matters, because in the previous lesson's deletion measurement, a method that looked at equality fell back to identity. There is no such fallback in a mapping: a key is always searched for by hash value and equality, never by identity. - **CO22** — The sought key is built from two variables **at runtime**; the key inside the mapping comes from the source text's spelling. That the two are separate objects is tested with `is`. - **CO23** — The **equality** of the hash values is compared; the values themselves are never printed. - **CO24** — Three tuples carrying the same values are built separately in a loop; two are equal, and entries remaining in the mapping are counted. ```python """A key is found by equality, not identity; the container's type takes part in equality.""" RECORD = {(2031, 7): "slope", (2031, 8): "north"} YEAR, MONTH = 2031, 7 SOUGHT = (YEAR, MONTH) # built at runtime, not a literal FIRST = next(iter(RECORD)) print(f"sought is the dict's key -> {SOUGHT is FIRST}") print(f"sought == the dict's key -> {SOUGHT == FIRST}") print(f"hash values equal -> {hash(SOUGHT) == hash(FIRST)}") print(f"RECORD[SOUGHT] -> {RECORD[SOUGHT]!r}") print() print(f"(2031, 7) == [2031, 7] -> {(2031, 7) == [2031, 7]}") print(f"(2031, 7) == (2031, 7, None) -> {(2031, 7) == (2031, 7, None)}") for candidate in ((2031, 7), [2031, 7]): try: found = candidate in RECORD except TypeError as e: found = type(e).__name__ print(f"{str(candidate):<12s} in RECORD -> {found}") print() TUPLES = [(2031, n) for n in (7, 8, 7)] print(f"three tuples built | distinct objects: " f"{TUPLES[0] is TUPLES[2]} | equal: {TUPLES[0] == TUPLES[2]}") MAPPING = {t: i for i, t in enumerate(TUPLES)} print(f"all three used as keys, entries remaining in the mapping: {len(MAPPING)}") ``` ``` sought is the dict's key -> False sought == the dict's key -> True hash values equal -> True RECORD[SOUGHT] -> 'slope' (2031, 7) == [2031, 7] -> False (2031, 7) == (2031, 7, None) -> False (2031, 7) in RECORD -> True [2031, 7] in RECORD -> TypeError three tuples built | distinct objects: False | equal: True all three used as keys, entries remaining in the mapping: 2 ``` The first four lines give the lookup rule: the object is **distinct**, the value is **equal**, the hashes are **equal**, and the lookup succeeds. Identity is not what finds a key. This is why a tuple is a cheap key — no need to hold on to it, building a new one from the same values is enough. The lines in between show equality **covers the container's type too**. A list carrying the same two numbers is not equal to a tuple, and no rule strips the type and looks only at content. A tuple of a different length is not equal either. The membership test is even stricter: a list is not just judged unequal, it fails with `TypeError` — a hash value has to be taken before searching, and that step never happens at all. The last two lines make equality's result concrete. Three tuples were built separately; the first and third are distinct objects but equal. With all three used as keys, **2** entries remain in the mapping: two equal keys landed in the same place, and the second overwrote the first's value. The container's identity never entered into it anywhere. #### Summary - Immutability closes off three operations: writing to a slot, deleting a slot, and adding a slot. The first two fail with `TypeError`, the last with `AttributeError` — one says "I cannot," the other "I do not know that." - `k += (new,)` on a tuple is not an extension, it is a **rebuild**: the container is new (`bigger is tup` → False) but the items are old (`bigger[0] is tup[0]` → True), and created is **1**. - Immutability is **one layer deep**: `k[0].value = 9` still passes on a tuple, because the tuple protects its slot, not the inside of the object the slot points to. - The capability a container gains is being usable as a key, and that capability **depends on its contents**: three of five candidates pass, and a tuple carrying a list fails even though the container itself is immutable. - A multiple return value is a tuple and creates **0** items; unpacking creates **0** too, because what gets carried is not objects, it is the links to them. #### Next Step A tuple **could be** a key; but the container that takes a key and reaches a value hasn't been measured yet. The next lesson looks at the mapping and pays the first half of the course's fourth debt: when the same two hundred items are searched for in a list and in a set, how many comparisons happen? The data is the same, the items are the same, only the container holding them changes. The same lesson asks a second question too: when a dictionary's keys are asked for, is what comes back a copy, or a window that keeps looking at the dictionary? ### Dictionaries Source: https://academia.sh/en/courses/python-data-structures/dictionaries Searching for the same item among two hundred does 200 comparisons in a list but 1 in a set and a dict; asking for keys returns not a copy but a view, and it sees a key added afterward — going from 2 to 3, while a list snapshot stays at 2. The previous lesson showed a tuple **could be** a key and measured that a key is found by equality, not identity. The container that takes a key and reaches a value was not measured. A **dict** is the container that binds a key to a value. This lesson asks it two questions, both answered with a number. The first pays the first half of the course's fourth debt: when the same two hundred items are searched for in a list and a set, **how many comparisons** happen? The data is the same, the items are the same; only the container holding them changes. The second is about copying: when a dict's keys are asked for, is what comes back a **copy**, or a **window** that keeps looking at the dict? #### What a Mapping Looks At A list has one way to search for an item: walk the slots in order and ask each one whether it equals the target. A dict and a set use another way — they compute which bucket a key falls into from its **hash value** and look there directly. This is why both require a hashable key; that was the condition the previous lesson measured. The mechanism itself is not this course's subject. How a hash table is built, load factor, collision resolution, and the table's growth behavior were built in the **Data Structures** course; complexity analysis and growth classes in the **Algorithms** course. Neither repeats here. That built the **mechanism**; here, what's measured is which container Python delivers it through, and how many concrete comparisons a single test costs. The numbers below are not a growth-class claim; they're a count made with specific data. - **CO25** — The item itself counts the comparison: the equality method increments a shared counter every time it is called. The setup is its own oracle; the number is a record, not a guess. - **CO26** — All three containers are built from the **same two hundred items**; the items are created once, and all three containers look at the same objects. - **CO27** — The counter resets **right before** each test; comparisons made while building the containers do not enter the measurement. - **CO28** — The sought item is **rebuilt every time**, so the search has to be done by equality, not identity. - **CO29** — Two conditions are measured separately: an item **found** in the container and one **not found**. - **CO30** — Position effect in the list is measured separately too; the count is read separately for the first, middle, and last item. ```python """Same two hundred items, three containers: how many comparisons does membership testing do.""" class Counting: """A value that counts equality comparisons.""" counter = {"comparisons": 0} def __init__(self, value): self.value = value def __eq__(self, other): Counting.counter["comparisons"] += 1 return isinstance(other, Counting) and self.value == other.value def __hash__(self): return hash(self.value) def measure(container, target): Counting.counter["comparisons"] = 0 found = target in container return Counting.counter["comparisons"], found N = 200 ITEMS = [Counting(i) for i in range(N)] CONTAINERS = (("list", list(ITEMS)), ("set", set(ITEMS)), ("dict", {o: o.value for o in ITEMS})) print(f"{'container':<10s}{'searching last item':>20s}{'found':>9s}" f"{'searching missing item':>25s}{'found':>9s}") for label, container in CONTAINERS: present, found1 = measure(container, Counting(N - 1)) absent, found2 = measure(container, Counting(N)) print(f"{label:<10s}{present:>20d}{str(found1):>9s}{absent:>25d}{str(found2):>9s}") print() first_count, _ = measure(CONTAINERS[0][1], Counting(0)) middle_count, _ = measure(CONTAINERS[0][1], Counting(N // 2)) print(f"in list, first item {first_count} | middle item {middle_count} | " f"last item {measure(CONTAINERS[0][1], Counting(N - 1))[0]}") print(f"in set, first item {measure(CONTAINERS[1][1], Counting(0))[0]} | " f"middle item {measure(CONTAINERS[1][1], Counting(N // 2))[0]} | " f"last item {measure(CONTAINERS[1][1], Counting(N - 1))[0]}") print() DICT_C = CONTAINERS[2][1] Counting.counter["comparisons"] = 0 value = DICT_C[Counting(N - 1)] print(f"reading a value from the dict: {Counting.counter['comparisons']} comparisons, " f"returned value {value}") ``` ``` container searching last item found searching missing item found list 200 True 200 False set 1 True 0 False dict 1 True 0 False in list, first item 1 | middle item 101 | last item 200 in set, first item 1 | middle item 1 | last item 1 reading a value from the dict: 1 comparisons, returned value 199 ``` #### Two Hundred Against One The upper table's first column gives the course's fourth debt: searching for the same item does **200** comparisons in a list, **1** in a set and a dict. Same data, same objects, same target value. Only the access method changes. **Cost is decided by access method, not data.** The second column sharpens the distinction further. Searching for an item **not in** the container, the list still does **200** comparisons — to know it is not there, it has to look at all of them. The set and dict do **0**: the hash computation took them to an empty bucket, and there was nothing there to compare against. Proving absence is the most expensive thing in a list, and the cheapest in a set. The two middle rows show a list's number **is not one number**: first item **1**, middle **101**, last **200** comparisons. In a list, cost depends on **where** the target sits. The same three searches in a set give **1**, **1**, **1** — position never enters the measurement, because a set does not walk slots, it computes. The last row measures a dict's real job. Reaching a value from a key does **1** comparison — the same number as set membership. A dict does the same search a set does, and keeps the value where it finds it. The two are two faces of the same mechanism: a set only says "is it there," a dict says "yes, and here's what it maps to." #### View or Snapshot The forms that ask for a dict's keys, values, or pairs do not return a list. What they return is a **view**: an object with no slots of its own that keeps looking at the dict. Its opposite is a **snapshot** — a list that freezes the state at the moment it was asked for in a separate container, breaking its link to the dict. Building both at the same moment and then mutating the dict makes the difference measurable. - **CO31** — Three views and one snapshot are built **at the same moment**, before the dict is touched; then a single key is added, and all four are read again. - **CO32** — Length is read from each container with its own method; the measurement never derives one container's length from another's. - **CO33** — In the thousand-entry measurement, the snapshot's slot count is printed; the view's slot count is **never printed**, since a view holds no slots. - **CO34** — Two view objects are compared with both `is` and `==`; no identity value is printed, only sameness is tested. - **CO35** — Mutating while looping is tried twice: once over a view, once over a snapshot. The attempt ending in an exception has **added one key** before it is cut off, and the second attempt continues from that state. - **CO36** — The order measurement uses a small three-key dict; order is read from the key list itself. ```python """View versus snapshot: which one sees a key added afterward.""" d = {"a": 1, "b": 2} keys_view = d.keys() values_view = d.values() items_view = d.items() key_list = list(d.keys()) before = (len(keys_view), len(values_view), len(items_view), len(key_list)) d["c"] = 3 after = (len(keys_view), len(values_view), len(items_view), len(key_list)) print(f"{'container':<22s}{'before add':>12s}{'after':>7s}" f"{'sees new key':>15s}") for label, before_n, after_n, contains in ( ("keys() view", before[0], after[0], "c" in keys_view), ("values() view", before[1], after[1], 3 in values_view), ("items() view", before[2], after[2], ("c", 3) in items_view), ("list(keys()) copy", before[3], after[3], "c" in key_list)): print(f"{label:<22s}{before_n:>12d}{after_n:>7d}{str(contains):>15s}") print() big = {i: i for i in range(1000)} view = big.keys() snapshot = list(big.keys()) print(f"in a thousand-entry dict, the view holds no slots; the snapshot holds " f"{len(snapshot)}") print(f"view is big.keys() -> {view is big.keys()} | " f"view == big.keys() -> {view == big.keys()}") print() try: for key in big: if key == 3: big[1000] = 1000 except RuntimeError as e: print(f"adding while looping over a view: {type(e).__name__}") snapshot_turns = 0 for key in list(big): if key == 3: big[1001] = 1001 snapshot_turns += 1 print(f"adding while looping over a snapshot: no problem, " f"{snapshot_turns} turns ran, dict grew to {len(big)} entries") print() order = {"north": 1, "slope": 2, "summary": 3} print(f"insertion order: {list(order)}") del order["north"] order["north"] = 9 print(f"after delete and re-add: {list(order)}") order["slope"] = 20 print(f"after changing an existing key's value: {list(order)}") ``` ``` container before add after sees new key keys() view 2 3 True values() view 2 3 True items() view 2 3 True list(keys()) copy 2 2 False in a thousand-entry dict, the view holds no slots; the snapshot holds 1000 view is big.keys() -> False | view == big.keys() -> True adding while looping over a view: RuntimeError adding while looping over a snapshot: no problem, 1001 turns ran, dict grew to 1002 entries insertion order: ['north', 'slope', 'summary'] after delete and re-add: ['slope', 'summary', 'north'] after changing an existing key's value: ['slope', 'summary', 'north'] ``` #### The Window Never Closes The upper table puts three of four rows on the same side. All three views go from length **2** to **3**, and all three **see** the key added afterward. The snapshot stays at **2** and does not see it. The views did not even exist at the moment of the addition — the dict had two entries when they were built. But what they carried was not two entries, it was a **link to the dict itself**; when the dict changed, what they saw changed too. The second block sets the cost and the gain side by side. In the thousand-entry dict, the snapshot opens **1000** slots — one link per key. The view opens none; no matter how large the dict it looks at, what it carries is a single link. If a dict's keys will only be looped over, taking a snapshot is a thousand-slot cost for nothing in return. The view object itself is rebuilt every time it is asked for — `view is big.keys()` is **False** — but two views count as equal, because both look at the same dict. What's paid in exchange is in the third block. Adding a key to the dict while looping over a view gives `RuntimeError`: once the dict grows during the loop, where the view is looking becomes ambiguous, and the language treats this as a fault and cuts the loop. The same work runs fine over a snapshot — it carries the state at the moment it was taken, and the turn count does not change no matter what happens to the dict afterward. The second measurement starting at **1001** turns is because the first, cut-off loop had already added one key before the exception. The rule that follows: **take a snapshot if it is going to be mutated while looping, use a view if it is only going to be read.** A snapshot's cost is slots, a view's cost is fragility. The last three lines show ordering. Keys stay in **insertion order**. A key deleted and re-added goes not to the front but to the **end**, because re-adding is a new entry. Changing an existing key's value does not disturb the order at all — the entry's place is kept, only its value is refreshed. #### Spellings for Merging and Looking Up For lists, `+` versus `+=` was the difference between building a new container and growing the existing one. The same distinction exists for dicts, in five separate spellings. Next to it sits the lookup side: five spellings do five different things when a key that does not exist is asked for. - **CO37** — All five forms start from a **freshly built** copy of the same three-entry dict; value objects are created once before the measurement. - **CO38** — The dict on the right **collides on one key** with the one on the left, showing how the merge finds the key count. - **CO39** — On the lookup side, the **class name** of the raised exception is written; if a value is returned, it is printed directly. ```python """Forms of merging a dict, and what five spellings do with a missing key.""" COUNTER = {"created": 0} class Item: def __init__(self, value): COUNTER["created"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): COUNTER["created"] = 0 def created(): return COUNTER["created"] VALUES = {name: Item(i) for i, name in enumerate(("north", "slope", "summary", "south"))} LEFT = {"north": VALUES["north"], "slope": VALUES["slope"], "summary": VALUES["summary"]} RIGHT = {"summary": VALUES["south"], "south": VALUES["south"]} def union_new(d): return d | RIGHT def union_inplace(d): d |= RIGHT return d def update_fn(d): d.update(RIGHT) return d def copy_fn(d): return dict(d) def unpack_build(d): return {**d, **RIGHT} FORMS = (("d | e", union_new), ("d |= e", union_inplace), ("d.update(e)", update_fn), ("dict(d)", copy_fn), ("{**d, **e}", unpack_build)) print(f"{'form':<14s}{'new items':>9s}{'same container':>16s}{'keys':>7s}" f"{'values shared':>16s}") for label, op in FORMS: d = dict(LEFT) before = d reset() result = op(d) shared = all(any(v is x for x in VALUES.values()) for v in result.values()) print(f"{label:<14s}{created():>9d}{str(result is before):>16s}" f"{len(result):>7d}{str(shared):>16s}") print() merged = LEFT | RIGHT print(f"colliding key 'summary' -> {merged['summary']} | " f"same object as right side's value: {merged['summary'] is RIGHT['summary']}") print() print(f"{'spelling':<24s}{'result'}") try: LEFT["missing"] except KeyError as e: print(f"{'d[missing]':<24s}{type(e).__name__}") print(f"{'d.get(missing)':<24s}{LEFT.get('missing')}") print(f"{'d.get(missing, default)':<24s}{LEFT.get('missing', Item(9))}") print(f"{'d.pop(missing, default)':<24s}{LEFT.pop('missing', Item(9))}") print(f"{'missing in d':<24s}{'missing' in LEFT}") ``` ``` form new items same container keys values shared d | e 0 False 4 True d |= e 0 True 4 True d.update(e) 0 True 4 True dict(d) 0 False 3 True {**d, **e} 0 False 4 True colliding key 'summary' -> Item(3) | same object as right side's value: True spelling result d[missing] KeyError d.get(missing) None d.get(missing, default) Item(9) d.pop(missing, default) Item(9) missing in d False ``` All five forms create **0** new values, and all five share values. A dict does on the key side what a list does: what it carries is not values, it is links to them. The distinction is again in the "same container" column — `d | e`, `dict(d)`, and `{**d, **e}` build a new container, `d |= e` and `d.update(e)` grow the existing one. Key count is not five, the sum of three and two — it is **4**. The colliding key is not counted twice; the right side's value overwrites the left's, and `merged['summary'] is RIGHT['summary']` confirms it. Merging a dict's result is therefore not a predictable number — it depends on the collision count, and only the keys can say what that is. The lower table gives the five spellings' answer to a missing key. Only bracket access produces an **exception**; the remaining four return a value. `get` without a default gives `None`, and that is not a fault report — a dict could hold a key whose value really is `None`, so getting `None` back is not a certain way to say "missing." The only spelling that tests absence for certain is membership testing, done with the **1** or **0** comparisons from this lesson's first measurement. #### Summary - On the same two hundred items, membership testing does **200** comparisons in a list, **1** in a set and a dict; searching for an item not present, the list still does **200**, the set and dict do **0**. - A list's number depends on position — first item **1**, middle **101**, last **200**; in a set all three searches give **1**, because a set computes rather than walking slots. - `keys()`, `values()`, and `items()` are views: they keep looking at the dict and see a key added afterward — their length goes from **2** to **3**. A snapshot taken with `list(...)` stays at **2**. - A view holds no slots; a thousand-entry dict's snapshot opens **1000**. In exchange, adding to the dict while looping over a view gives `RuntimeError`, while looping over a snapshot does not. - Keys stay in insertion order; a deleted and re-added key goes to the end, and changing an existing key's value does not disturb the order. #### Next Step In this lesson's measurement, the set stood quietly beside the dict and gave the same numbers — **1** and **0**. What it does on its own was never asked. The next lesson looks at the set alone and measures its most common job: dropping duplicates from a list. The question again gets a numeric answer. How many comparisons and how many objects does hand-picking duplicates cost against handing them to a set, and are the items coming back out of a set new or old? ### Sets Source: https://academia.sh/en/courses/python-data-structures/sets Deduplicating three hundred items does 15050 comparisons scanned by hand, 200 handed to a set, and all three give the same hundred items; all six set operations create 0 new items, and four build a new container while two mutate the existing one. In the previous lesson's measurement, the set stood quietly beside the dict and gave the same numbers: **1** comparison for a found item, **0** for one not found. What it does on its own was never asked. A **set** is a container that holds only membership — no value, no order, no duplicates. These three absences are the result of the same mechanism, and they're what directly makes this lesson's job possible: **dropping duplicates** from a pile of data. The question again gets a numeric answer. How many comparisons does hand-picking duplicates cost against handing them to a set, and are the items coming back out new or old? #### What a Set Asks A set does not ask "at what position" when holding an item; it only asks "is this already here." It finds the answer the same way the dict found a key in the previous lesson: it computes which bucket the item's **hash value** falls into and looks there. This is why a set's items also have to be hashable — the same condition measured in the tuples lesson applies here to items. The mechanism itself — hash table, collision, load factor — was built in the **Data Structures** course and is not repeated. What's measured here is how many concrete comparisons two spellings of the same job cost; not a growth-class claim, a count made with specific data. The item itself counts the comparisons. The hand-written spelling of deduplication is direct and readable: a result list is kept, each item is checked against "is this already in the list," and added if not. This spelling's hidden cost is that "is it there" is asked of **a list** every time — and the previous lesson measured what a membership question asked of a list costs. - **CO40** — The raw data is three hundred items carrying **a hundred distinct values**; each value appears exactly three times. The expected result is therefore known in advance, and the setup is its own oracle. - **CO41** — All three methods work on the **same raw list**; items are created once, and none of the methods builds a new item. - **CO42** — The counter resets right before each method; building the raw data does not enter the measurement. - **CO43** — The "new items" column is found by searching each result item in the raw data with `is`; zero means the result is shared. - **CO44** — The order column is filled only for methods that **guarantee order**; the order a set gives its items in is not measured and is not relied on. ```python """Deduplication: three methods, same result, different comparison counts.""" class Counting: """A value that counts equality comparisons.""" counter = {"comparisons": 0} def __init__(self, value): self.value = value def __eq__(self, other): Counting.counter["comparisons"] += 1 return isinstance(other, Counting) and self.value == other.value def __hash__(self): return hash(self.value) UNIQUE = 100 RAW = [Counting(i % UNIQUE) for i in range(3 * UNIQUE)] def manual(raw): result = [] for x in raw: if x not in result: result.append(x) return result def to_set(raw): return set(raw) def to_dict_keys(raw): return dict.fromkeys(raw) print(f"{'method':<22s}{'comparisons':>13s}{'unique':>9s}" f"{'new items':>12s}{'order kept':>14s}") FIRST = None for label, method, ordered in (("manual scan", manual, True), ("set(raw)", to_set, False), ("dict.fromkeys(raw)", to_dict_keys, True)): Counting.counter["comparisons"] = 0 result = method(RAW) count = Counting.counter["comparisons"] new_count = sum(1 for x in result if not any(x is y for y in RAW)) if FIRST is None: FIRST = list(result) same_order = list(result) == FIRST print(f"{label:<22s}{count:>13d}{len(result):>9d}{new_count:>12d}" f"{str(same_order) if ordered else 'no guarantee':>14s}") print() print(f"raw data {len(RAW)} items | duplicates {len(RAW) - UNIQUE} | " f"unique {UNIQUE}") print(f"are the items in the manual scan's result from the raw data: " f"{all(any(x is y for y in RAW) for x in manual(RAW))}") ``` ``` method comparisons unique new items order kept manual scan 15050 100 0 True set(raw) 200 100 0 no guarantee dict.fromkeys(raw) 200 100 0 True raw data 300 items | duplicates 200 | unique 100 are the items in the manual scan's result from the raw data: True ``` #### Same Hundred Items, Three Different Bills The "unique" column is the same in all three rows: **100**. All three methods give the correct result, and all three create **0** new items — every object in the result is one of the raw data's own. The difference is entirely in the left column. The manual scan does **15050** comparisons. This number comes from two parts. The first hundred items are always new, so each is compared against the entire result accumulated so far; that comes to **4950**. The remaining two hundred are duplicates, and each stops as soon as it finds its match; that is **10100**. The total grows not by **how many times** a list gets asked a membership question, but by how many **slots** each question crosses. Handing it to a set finishes the same job in **200** comparisons — about a seventy-fifth as many. The gap between the two does not come from a different spelling, it comes from a different **way of asking**: the manual scan walks the whole result every time, the set looks at a single bucket every time. And the number 200 itself is meaningful: the raw data has exactly **200** duplicates. A set makes one comparison per duplicate, none for a unique item. If an item is new, its bucket is empty and there is nothing to compare against. The third row gives both the price a set exacts and a way to avoid paying it. A set has no order; what order it gives its items is not measured in this lesson and is not relied on. But a mapping that keeps keys in insertion order does the same deduplication with the **same 200 comparisons** and keeps order too. If the result needs order, the right tool is not a set, it is a mapping used with its keys. #### Set Operations A set's second job is arithmetic between sets: union, intersection, difference, symmetric difference. These four operations come from set theory, and their meaning is beyond dispute. What's measured is not their meaning but **what they cost**: how many items they create, whether the result is a new container, and where the objects inside it come from. - **CO45** — All six forms start from a **freshly built** copy of the same three-item set; items are created once before the measurement. - **CO46** — The two sets **intersect on one item**, so the intersection and difference counts are known in advance and confirm the table. - **CO47** — The "items from pool" column is found by searching each result item in the pool, before measurement, with `is`. - **CO48** — Hashability is tested directly, and the raised exception's **class name** is written; the hash value is never printed. ```python """Set operations: each builds a new container, none creates a new item.""" COUNTER = {"created": 0} class Item: def __init__(self, value): COUNTER["created"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): COUNTER["created"] = 0 def created(): return COUNTER["created"] POOL = [Item(i) for i in range(5)] LEFT = {POOL[0], POOL[1], POOL[2]} RIGHT = {POOL[2], POOL[3], POOL[4]} def union_op(a): return a | RIGHT def intersect_op(a): return a & RIGHT def difference_op(a): return a - RIGHT def symmetric_diff_op(a): return a ^ RIGHT def inplace_union(a): a |= RIGHT return a def inplace_intersect(a): a &= RIGHT return a FORMS = (("a | b", union_op), ("a & b", intersect_op), ("a - b", difference_op), ("a ^ b", symmetric_diff_op), ("a |= b", inplace_union), ("a &= b", inplace_intersect)) print(f"{'operation':<10s}{'new items':>9s}{'same container':>16s}{'items':>7s}" f"{'items from pool':>17s}") for label, op in FORMS: a = set(LEFT) before = a reset() result = op(a) from_pool = all(any(x is y for y in POOL) for x in result) print(f"{label:<10s}{created():>9d}{str(result is before):>16s}{len(result):>7d}" f"{str(from_pool):>17s}") print() print(f"{'test':<34s}{'result'}") print(f"{'LEFT <= LEFT | RIGHT':<34s}{LEFT <= (LEFT | RIGHT)}") print(f"{'LEFT < LEFT':<34s}{LEFT < LEFT}") print(f"{'LEFT.isdisjoint(RIGHT)':<34s}{LEFT.isdisjoint(RIGHT)}") print(f"{'(LEFT - RIGHT).isdisjoint(RIGHT)':<34s}{(LEFT - RIGHT).isdisjoint(RIGHT)}") print() FROZEN = frozenset({POOL[0], POOL[1]}) print(f"frozen set can be a set's item -> {FROZEN in {FROZEN}}") for candidate in (LEFT, FROZEN): try: {candidate: 0} result = "yes" except TypeError as e: result = type(e).__name__ print(f"{type(candidate).__name__:<12s} can be a key -> {result}") try: {[1, 2]} except TypeError as e: print(f"list can be a set item -> {type(e).__name__}") ``` ``` operation new items same container items items from pool a | b 0 False 5 True a & b 0 False 1 True a - b 0 False 2 True a ^ b 0 False 4 True a |= b 0 True 5 True a &= b 0 True 1 True test result LEFT <= LEFT | RIGHT True LEFT < LEFT False LEFT.isdisjoint(RIGHT) False (LEFT - RIGHT).isdisjoint(RIGHT) True frozen set can be a set's item -> True set can be a key -> TypeError frozenset can be a key -> yes list can be a set item -> TypeError ``` #### Four Computations, Zero Items Six rows' "new items" column is entirely **0**, and "items from pool" is entirely **True**. Set operations compute, they do not produce: every object visible in the result is one created before the measurement. This is the third repeat of the pattern measured in lists and dicts — Python's built-in containers do not carry items, they arrange links to them. The item counts confirm the setup: two three-item sets intersecting on one item give a union of **5**, an intersection of **1**, a difference of **2**, a symmetric difference of **4**. The totals adding up is the measurement's own internal check. The distinction is again in the "same container" column, and it is familiar by now: the operator form builds a **new container**, the assignment form mutates the **existing** one. This is the fourth time in this course the same distinction shows up in the same place — `+` versus `+=` in a list, the same pair's forced rebuild in a tuple, `|` versus `|=` in a dict, `|` versus `|=` in a set. The rule is not specific to the container, it is specific to the language: **the operator gives a new object, the assignment operator tries to mutate the existing one.** The subset tests in the lower block give a set's comparison meaning. `<=` asks about a subset, and a set is a subset of itself; `<` asks about a **proper** subset and gives **False** for itself. These two are about a set's containment, not numbers, and shouldn't be confused with a number comparison. The last block carries the immutability measurement over to sets. A set is itself **mutable**, so it cannot be hashed and cannot be a key; it fails with `TypeError`. A **frozen set** holds the same items in an immutable container, and it can be both a key and another set's item. A list can be neither. The rule built in the tuples lesson holds here exactly the same: the condition for a container to be **placeable inside** another container is the promise it makes that its own contents will stay fixed. #### Doing the Same Computation with a List Every set operation can be written with lists too; none of them requires a capability specific to a set. Intersection means "those on the left also found on the right," difference means "those on the left not found on the right," and both are written as a one-line filter. These spellings' result is correct. What's measured is not correctness, it is **price**. - **CO49** — The two collections are **two hundred items each** and **overlap on a hundred**; that the intersection and difference results are a hundred items is known from the setup and confirms the table. - **CO50** — The list and set forms are built from the **same objects**; the counter resets right before each row, and building the containers does not enter the measurement. - **CO51** — The last block does not measure a number; it separates the question a set **can** answer from the one it **cannot**. ```python """Taking an intersection by hand versus handing it to a set; and the information deduplication drops.""" class Counting: counter = {"comparisons": 0} def __init__(self, value): self.value = value def __eq__(self, other): Counting.counter["comparisons"] += 1 return isinstance(other, Counting) and self.value == other.value def __hash__(self): return hash(self.value) LEFT_LIST = [Counting(i) for i in range(200)] RIGHT_LIST = [Counting(i) for i in range(100, 300)] LEFT_SET, RIGHT_SET = set(LEFT_LIST), set(RIGHT_LIST) def manual_intersect(): return [x for x in LEFT_LIST if x in RIGHT_LIST] def set_intersect(): return LEFT_SET & RIGHT_SET def manual_difference(): return [x for x in LEFT_LIST if x not in RIGHT_LIST] def set_difference(): return LEFT_SET - RIGHT_SET print(f"{'operation':<28s}{'comparisons':>14s}{'result items':>13s}") for label, op in (("intersection, two lists", manual_intersect), ("intersection, two sets", set_intersect), ("difference, two lists", manual_difference), ("difference, two sets", set_difference)): Counting.counter["comparisons"] = 0 result = op() print(f"{label:<28s}{Counting.counter['comparisons']:>14d}{len(result):>13d}") print() RAW = [Counting(i % 100) for i in range(300)] DEDUPED = set(RAW) print(f"raw data {len(RAW)} items -> set {len(DEDUPED)} items") print(f"question a set can answer: 'is it there' -> {Counting(7) in DEDUPED}") print("question a set cannot answer: 'how many times'") ``` ``` operation comparisons result items intersection, two lists 25050 100 intersection, two sets 100 100 difference, two lists 25050 100 difference, two sets 100 100 raw data 300 items -> set 100 items question a set can answer: 'is it there' -> True question a set cannot answer: 'how many times' ``` The four rows' "result items" column settles correctness: all four give **100** items. The list spelling is not wrong, only expensive. Taking the intersection with lists does **25050** comparisons, with sets **100** — a two-hundred-fifty-fold difference, on the same data, with the same result. The difference rows give the same number, and that is not a coincidence. In the list spelling, the right list is scanned for every item; whether the scan ends in "found" or "not found" does not determine how many slots got crossed. The same symmetry holds for sets: the intersection makes one comparison per matching item, so does the difference. Changing the access method changes the **shape** of the cost, not just its size. The last block draws a set's boundary, and it is this lesson's closing word. Three hundred items handed to a set come down to **100**. What's lost is not two hundred objects — the objects are still there, the raw list still holds them. What's lost is **information**: which value appeared how many times. A set answers "is it there" with one comparison, but it can never answer "how many times," because it never keeps that number at all. Deduplication is cheap; the source of that cheapness is the assumption that the discarded information will never be asked for again. #### Summary - On three hundred items, deduplication does **15050** comparisons scanned by hand, **200** handed to a set; all three methods give the same **100** unique items and **0** new items. - A set's **200** equals the raw data's duplicate count exactly: every duplicate costs one comparison, a unique item costs none. - A set has no order; if order needs keeping, a mapping is used that does the same **200** comparisons while also keeping insertion order. - All six set operations create **0** items, and every object in the result is old; the operator form builds a new container, the assignment form mutates the existing one. - A set cannot be a key because it is mutable; a frozen set can be both a key and a set item — the condition is the promise a container makes that its own contents stay fixed. - Taking the same intersection with lists does **25050** comparisons, with sets **100**; both give the same **100** items, but deduplication drops the "how many times" information. #### Next Step This lesson's last line wrote the question a set cannot answer: **how many times.** Anyone wanting to keep that answer writes the same pattern by hand — open a dict, increment if the key exists, start at one if not. There are other patterns written the same way by hand too: taking items from both ends of a list, preparing an empty container for a key that does not exist. The next lesson looks at the standard library's ready-made counterparts for these patterns and puts each one side by side with its hand-written equivalent. Two numbers get measured: how many lines, and how many objects. ### Specialized Collections Source: https://academia.sh/en/courses/python-data-structures/specialized-collections Writing the same grouping with setdefault creates 320 containers, with a defaultdict 100; on a thousand-item stream, all three spellings produce 1000 objects but held is 1000 against 5, and rotating builds three containers with a list against none with a deque. The previous lesson's last line wrote the question a set cannot answer: **how many times.** A set holds only membership; it does not keep the count, because it does not have to. Anyone who wants that number writes the same pattern by hand — open a dict, increment if the key exists, start at one if not. Other patterns get written by hand the same way: sorting records into bins by key, holding only a stream's last few items, moving one end of a sequence to the other. This lesson looks at these patterns' ready-made counterparts in the standard library and puts each side by side with its hand-written equivalent. Two numbers get measured: **how many lines**, and **how many objects**. #### A Pattern's Two Prices Writing a pattern by hand has two separate, independent costs. The first is **lines**: code written, read, tested, and capable of being written wrong. The second is **objects**: what the pattern creates and holds while running. One spelling can cut lines while raising objects; one of the three grouping spellings measured here does exactly that. The theory behind structures like stacks, queues, and linked lists was built in the **Data Structures** course and is not repeated here. What's measured here is which container Python delivers that queue through, and how many lines and objects it saves against its hand-written counterpart. Line count is not counted by hand: each spelling is a function body, and its non-blank line count is read from the function's own source. The number is therefore a finding from the run, not a claim. - **CO52** — Body lines are read from the function's source; **the def line and blank lines are not counted.** Every spelling is a function indented the same way, doing the same job. - **CO53** — Three counting spellings and three grouping spellings work on the **same data**; the data carries 320 records and 100 distinct keys, with one key deliberately appearing more often. - **CO54** — The correctness column compares the result against the first, hand-written spelling's result; the hand-written pattern is the oracle. - **CO55** — In grouping, a box is an object counted at each creation; what gets counted is boxes, not the records put into them. - **CO56** — The counter resets right before each spelling; building the data does not enter the measurement. ```python """Counting and grouping: hand-written pattern side by side with its ready-made counterpart.""" import inspect from collections import Counter, defaultdict COUNTER = {"created": 0} class Item: def __init__(self, value): COUNTER["created"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): COUNTER["created"] = 0 def created(): return COUNTER["created"] DATA = [f"a{i % 100:02d}" for i in range(300)] + ["a07"] * 20 def body_lines(f): """Non-blank line count of a function's body; the def line is not counted.""" lines = inspect.getsource(f).splitlines()[1:] return sum(1 for s in lines if s.strip()) def manual_count(data): counts = {} for key in data: if key in counts: counts[key] += 1 else: counts[key] = 1 return counts def get_count(data): counts = {} for key in data: counts[key] = counts.get(key, 0) + 1 return counts def use_counter(data): return Counter(data) def manual_group(data): boxes = {} for i, key in enumerate(data): if key not in boxes: boxes[key] = Item([]) boxes[key].value.append(i) return boxes def setdefault_group(data): boxes = {} for i, key in enumerate(data): boxes.setdefault(key, Item([])).value.append(i) return boxes def defaultdict_group(data): boxes = defaultdict(lambda: Item([])) for i, key in enumerate(data): boxes[key].value.append(i) return boxes EXPECTED_COUNT = manual_count(DATA) EXPECTED_GROUP = {k: v.value for k, v in manual_group(DATA).items()} print(f"{'counting spelling':<24s}{'body lines':>11s}{'created':>10s}" f"{'result correct':>16s}") for label, method in (("manual check", manual_count), ("with get", get_count), ("counter", use_counter)): reset() result = method(DATA) print(f"{label:<24s}{body_lines(method):>11d}{created():>10d}" f"{str(dict(result) == EXPECTED_COUNT):>16s}") print() print(f"{'grouping spelling':<24s}{'body lines':>11s}{'created':>10s}" f"{'result correct':>16s}") for label, method in (("manual check", manual_group), ("with setdefault", setdefault_group), ("defaultdict", defaultdict_group)): reset() result = method(DATA) correct = {k: v.value for k, v in result.items()} == EXPECTED_GROUP print(f"{label:<24s}{body_lines(method):>11d}{created():>10d}" f"{str(correct):>16s}") print() print(f"data {len(DATA)} records | distinct keys {len(EXPECTED_COUNT)} | " f"counts seen {sorted(set(EXPECTED_COUNT.values()))}") print(f"counter's two most common: {Counter(DATA).most_common(2)}") ``` ``` counting spelling body lines created result correct manual check 7 0 True with get 4 0 True counter 1 0 True grouping spelling body lines created result correct manual check 6 100 True with setdefault 4 320 True defaultdict 4 100 True data 320 records | distinct keys 100 | counts seen [3, 23] counter's two most common: [('a07', 23), ('a00', 3)] ``` #### Cheap Lines, Not Cheap Objects The upper table only measures the line side, and only in one direction. Manual counting takes **7** lines, `get` **4**, and **Counter** just **1**. All three give the correct result, and all three create **0** objects — counts are integers, not containers. What's gained is only lines; but lines are a cost too, since handling a key's first appearance separately means one more branch and one more place to get wrong. `Counter`'s extra gift shows in the last line: giving the most common keys already sorted. By hand, that means sorting the dict by value and taking the first two. What a ready-made container offers is not just the pattern itself, it is the work around it. The lower table is the real measurement, and its two columns work in opposite directions. Manual grouping creates **6** lines and **100** boxes: one for each distinct key. The `setdefault` spelling drops to **4** lines — but creates **320** boxes. The difference is in the spelling itself: `setdefault` is a **call**, and its argument gets evaluated **before** the call, without checking whether the result will be used. If the key already exists, the box created is never used and gets thrown away right there. Three hundred twenty records build three hundred twenty boxes, two hundred twenty of them for nothing. **`defaultdict`** drops to the same **4** lines with **100** boxes. Because there, what builds the box is not the caller, it is the container itself: the producer is called only if the key is **actually missing**, otherwise not. Same line count, less than a third the objects. The rule that follows looks not at spelling but at **evaluation timing**: a default value written as an argument gets created on every call; given as a producer, only when needed. Two spellings, same length, same result; where they diverge is exactly the axis this course measures. #### Holding Only the Stream's Tail The second measurement looks at a container's **holding** side. On a thousand-item stream, every item gets created — there is no escaping that, since the container is not what produces the items. What can change is **how many** of them the container keeps. The third container in this measurement is a **deque**: an ordered container that can take and give items from either end, and can be given a length cap when built. - **CO57** — All three spellings build the same thousand-item stream; items are created during the measurement, and the counter resets before each spelling. - **CO58** — The window is five items, and the last item is printed for all three spellings, confirming all three consumed the stream to the end. - **CO59** — In the rotation measurement, containers built is read **from the container-building expressions in the code**: two slices plus a concat make three, in-place rotation builds none. Container count is also confirmed with `is`. - **CO60** — The two rotation results are compared for being in the **same order**; this line shows the two spellings' equivalence. - **CO61** — Item sharing is tested by searching every result item in the pool with `is`. ```python """Deque: a bounded window and rotation, alongside their hand-written counterparts.""" import inspect from collections import deque COUNTER = {"created": 0} class Item: def __init__(self, value): COUNTER["created"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): COUNTER["created"] = 0 def created(): return COUNTER["created"] def body_lines(f): lines = inspect.getsource(f).splitlines()[1:] return sum(1 for s in lines if s.strip()) STREAM, WINDOW = 1000, 5 def list_untrimmed(): container = [] for i in range(STREAM): container.append(Item(i)) return container def list_trimmed(): container = [] for i in range(STREAM): container.append(Item(i)) if len(container) > WINDOW: del container[0] return container def with_deque(): container = deque(maxlen=WINDOW) for i in range(STREAM): container.append(Item(i)) return container print(f"{'spelling':<24s}{'body lines':>11s}{'created':>10s}" f"{'held':>8s}{'last item':>12s}") for label, method in (("list, untrimmed", list_untrimmed), ("list, manual trim", list_trimmed), ("deque", with_deque)): reset() container = method() print(f"{label:<24s}{body_lines(method):>11d}{created():>10d}" f"{len(container):>8d}{str(container[-1]):>12s}") print() POOL = [Item(i) for i in range(5)] K = 2 lst = list(POOL) reset() left, right = lst[K:], lst[:K] rotated = left + right print(f"rotating with a list: created {created()} | containers built 3 " f"(two slices and a concat)") print(f" result {rotated} | rotated is lst -> " f"{rotated is lst}") dq = deque(POOL) before = dq reset() dq.rotate(-K) print(f"rotating with a deque: created {created()} | containers built 0") print(f" result {list(dq)} | dq is before -> {dq is before}") print(f" both results in the same order -> {list(dq) == rotated}") print(f" items shared -> " f"{all(any(x is y for y in POOL) for x in dq)}") ``` ``` spelling body lines created held last item list, untrimmed 4 1000 1000 Item(999) list, manual trim 6 1000 5 Item(999) deque 4 1000 5 Item(999) rotating with a list: created 0 | containers built 3 (two slices and a concat) result [Item(2), Item(3), Item(4), Item(0), Item(1)] | rotated is lst -> False rotating with a deque: created 0 | containers built 0 result [Item(2), Item(3), Item(4), Item(0), Item(1)] | dq is before -> True both results in the same order -> True items shared -> True ``` #### Created the Same, Held Different The "created" column is the same in all three rows: **1000**. That this column does not change is the measurement's most important finding. Changing the container does not change how many objects get produced — items are not produced by the container. The only thing the container chooses is how many of the produced ones **stay held**. The "held" column diverges: the untrimmed list holds **1000** items, the manually trimmed list **5**, the deque **5**. All three consume the stream to the end, and all three end on the same last item. If only the last five items are needed, the untrimmed list holds nine hundred ninety-five objects for no reason at all. The lines column gives the second difference: manual trimming needs **6** lines, the deque **4**. The two extra lines are a condition and a delete. In the hand-written spelling, the window limit is something checked **inside the loop**, on every turn; in the deque, it is part of the container's **definition**. The lower block measures rotation and confirms the two results are **in the same order**. Rotating with a list creates **0** items but builds **3** containers: the right part's slice, the left part's slice, and the concatenation of the two. The result is a new container, and `rotated is lst` is **False**. Rotating with a deque creates **0** items and builds **0** containers; the result is the same container, and `dq is before` is **True**. Items come from the pool in both spellings. The gap between three containers and zero looks small, but if rotation sits inside a loop, every turn builds three. **The hand-written pattern usually gives the correct result; what it costs is not the result itself, it is the intermediate containers built along the way.** #### A Missing Key and a Preserved Count Both specialized containers are dicts, and both diverge from a plain dict on a missing key — but they also diverge from each other. The third measurement repeats bracket access on three containers and checks how many keys remain **after** the access. - **CO62** — All three containers are built with a single key, the same value; the only thing measured is the result of accessing a key that **does not exist**. - **CO63** — Key count is read **after** the access; whether the access changed the container shows in this number. - **CO64** — Counter arithmetic is done with two small counters; results are printed sorted by key, since what's measured is the preserved count, not order. ```python """Three containers do three different things with a missing key; a Counter computes while preserving 'how many'.""" from collections import Counter, defaultdict PLAIN_DICT = {"a07": 3} DEFAULT = defaultdict(int, {"a07": 3}) COUNT = Counter({"a07": 3}) print(f"{'container':<20s}{'d[missing] result':<19s}{'keys after'}") for label, container in (("dict", PLAIN_DICT), ("defaultdict", DEFAULT), ("Counter", COUNT)): try: result = str(container["missing"]) except KeyError as e: result = type(e).__name__ print(f"{label:<20s}{result:<19s}{len(container)}") print() LEFT = Counter("aabbbcc") RIGHT = Counter("abbdd") print(f"left counter {dict(sorted(LEFT.items()))}") print(f"right counter {dict(sorted(RIGHT.items()))}") print(f"{'operation':<22s}{'result'}") for label, result in (("counter intersection", LEFT & RIGHT), ("counter union", LEFT | RIGHT), ("counter difference", LEFT - RIGHT)): print(f"{label:<22s}{dict(sorted(result.items()))}") print(f"{'set intersection':<22s}{sorted(set(LEFT) & set(RIGHT))}") print(f"{'set union':<22s}{sorted(set(LEFT) | set(RIGHT))}") print() print(f"a Counter is a dict -> {isinstance(LEFT, dict)} | " f"total records {sum(LEFT.values())} | distinct keys {len(LEFT)}") print(f"intersection total {sum((LEFT & RIGHT).values())} | " f"set intersection item count {len(set(LEFT) & set(RIGHT))}") ``` ``` container d[missing] result keys after dict KeyError 1 defaultdict 0 2 Counter 0 1 left counter {'a': 2, 'b': 3, 'c': 2} right counter {'a': 1, 'b': 2, 'd': 2} operation result counter intersection {'a': 1, 'b': 2} counter union {'a': 2, 'b': 3, 'c': 2, 'd': 2} counter difference {'a': 1, 'b': 1, 'c': 2} set intersection ['a', 'b'] set union ['a', 'b', 'c', 'd'] a Counter is a dict -> True | total records 7 | distinct keys 3 intersection total 3 | set intersection item count 2 ``` Three containers do three different things. The dict raises an exception and does not change: key count stays at **1**. The defaultdict gives **0** and key count rises to **2** — an access meant only for reading has added a **permanent entry** to the container. The Counter gives **0** and key count stays at **1**: it says zero for a missing key but does not record it. This distinction is a direct result of the grouping measurement. Calling the producer on a missing key was the behavior wanted in grouping; the same behavior is an **unwanted side effect** in an access meant only to look. In a defaultdict, "is this key here" is not asked with brackets; it is asked with membership testing or `get`. The lower block answers the previous lesson's closing question. In data handed to a set, "how many times" was lost. A Counter does the same arithmetic while **preserving** the count: intersection gives the **smaller** of the two counts per key, union the **larger**, and difference gives the subtraction result — a key that drops below zero never appears in the result. A set on the same two pieces of data gives only the keys. The last line sums up the difference with one pair: the set intersection has **2** items, the counter intersection's total is **3**. Same two keys, two different levels of information. #### Summary - A pattern has two separate prices — lines and objects — and they can move independently: the `setdefault` spelling drops lines from **6** to **4** while raising created containers from **100** to **320**. - A default written as an **argument** gets created on every call; given as a **producer**, it is called only when the key is missing — `defaultdict` builds **100** containers with the same **4** lines. - On the counting side, the gain is only in lines: **7**, **4**, and **1** line spellings all give the same result and create **0** objects. - On a thousand-item stream, all three spellings create **1000** objects; the container decides only what's **held** — **1000** in an untrimmed list, **5** in a manually trimmed list and a deque. - Rotation builds **3** intermediate containers with a list and returns a new one, **0** with a deque and turns the same container in place; both results are in the same order and share items. - On a missing key, a dict raises `KeyError`, a defaultdict gives **0** and **adds** the key (**1** to **2**), a Counter gives **0** without adding it; a Counter also computes intersection and difference while preserving counts. #### Next Step This lesson's rotation measurement took two slices, and the result was a new container. A slice passed here as a detail; on its own, though, it is this course's most misunderstood operation. The next lesson looks at nothing else and carries a single question all the way through: when a slice is taken, **what** gets copied? The container itself, its contents, or both? The answer gets measured in a nested list, and the numbers will speak for themselves. ### Slicing Source: https://academia.sh/en/courses/python-data-structures/slicing All eight slice forms create 0 new items and return a new container; a nested list produces 4 items and both inner lists are shared in the slice copy — the outer container is new, the contents are old. The previous lesson's rotation measurement took two slices, and the result was a new container. A slice passed there as a detail; on its own it is this course's most misunderstood operation. This lesson carries one question through: when a slice is taken, what gets copied — the container itself, its contents, or both? #### A Slice Wants a Container **Slicing** syntax takes three parts: start, stop, step. All three are optional and fall back to the container's ends and to one when omitted. The Python Fundamentals course measured this syntax as an abbreviation; there, which method it called was counted — here, how many containers that call builds. An index wants a single slot, and asking for one that does not exist is a fault; a slice wants a range, and the part beyond the container is silently clipped. - **CO65** — All eight forms work on the same six-item source; items are created once, and the counter resets right before each slice. "Items from source" is found by searching each slice item against the source with `is`. - **CO66** — Slice assignment and deletion proceed sequentially on a single list; the second row continues from the first's state. ```python """Reading a slice: every slice builds a new container, none creates a new item.""" COUNTER = {"created": 0} class Item: def __init__(self, value): COUNTER["created"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): COUNTER["created"] = 0 def created(): return COUNTER["created"] SOURCE = [Item(i) for i in range(6)] FORMS = (("k[1:4]", lambda k: k[1:4]), ("k[:3]", lambda k: k[:3]), ("k[3:]", lambda k: k[3:]), ("k[::2]", lambda k: k[::2]), ("k[::-1]", lambda k: k[::-1]), ("k[:]", lambda k: k[:]), ("k[4:100]", lambda k: k[4:100]), ("k[10:20]", lambda k: k[10:20])) print(f"{'slice':<12s}{'new items':>9s}{'slots':>6s}{'same container':>16s}" f"{'items from source':>19s}{'content':>26s}") for label, take in FORMS: reset() piece = take(SOURCE) from_source = all(any(x is y for y in SOURCE) for x in piece) print(f"{label:<12s}{created():>9d}{len(piece):>6d}" f"{str(piece is SOURCE):>16s}{str(from_source):>19s}" f"{str([o.value for o in piece]):>26s}") print() try: SOURCE[10] except IndexError as e: print(f"out-of-range index: {type(e).__name__} | " f"out-of-range slice: {[o.value for o in SOURCE[10:20]]}") print() target = list(SOURCE) before = target reset() target[1:3] = [Item(9), Item(9), Item(9)] print(f"slice assignment: created {created()} | same container " f"{target is before} | slots {len(before)} -> {[o.value for o in target]}") reset() del target[::2] print(f"slice deletion: created {created()} | same container " f"{target is before} | slots {len(target)} -> {[o.value for o in target]}") print() text = "north-2031" print(f"string slice {text[6:]!r} | tuple slice " f"{tuple(o.value for o in SOURCE)[1:4]}") ``` ``` slice new items slots same container items from source content k[1:4] 0 3 False True [1, 2, 3] k[:3] 0 3 False True [0, 1, 2] k[3:] 0 3 False True [3, 4, 5] k[::2] 0 3 False True [0, 2, 4] k[::-1] 0 6 False True [5, 4, 3, 2, 1, 0] k[:] 0 6 False True [0, 1, 2, 3, 4, 5] k[4:100] 0 2 False True [4, 5] k[10:20] 0 0 False True [] out-of-range index: IndexError | out-of-range slice: [] slice assignment: created 3 | same container True | slots 7 -> [0, 9, 9, 9, 3, 4, 5] slice deletion: created 0 | same container True | slots 3 -> [9, 9, 4] string slice '2031' | tuple slice (1, 2, 3) ``` #### Eight Slices, Zero Items The first column is 0 in all eight rows: taking a slice creates no items. The third is False in all eight: every slice is a new container on a list, even a full one. The fourth is True in all eight: every slice item is the source's item. Together, the three give this lesson's one-sentence finding — a slice renews the container, not its contents. Step selects content but does not change the table; `k[::2]` takes three slots, `k[::-1]` six, both creating 0 items. The last two rows show where a slice diverges from an index: a slot outside the container raises `IndexError`; a range outside it, `k[4:100]` gives two items, `k[10:20]` gives zero, neither a fault. A range is a different question from a specific slot. The lower block's three lines are a slice's other face: reading births a new container, writing mutates one in place — `target is before` stays True. That measurement opens up in "Writing Is Not Copying." #### How Deep a Copy Goes The source measured so far was a flat list. The real question shows up with a container inside a container: taking a slice of a nested list makes the outer container new — measured already. What about the inner containers? - **CO67** — The nested source carries two inner lists and four leaf items, confirmed by the measurement's first row. The mutation test happens at the end; everything before it takes the source untouched. - **CO68** — A deep copy does not pass objects through the constructor, so the creation counter cannot see it; a new object's existence is counted by identity — copy leaves not found in the source with `is`. ```python """A copy is one layer deep: the outer container is new, the contents are old.""" import copy COUNTER = {"created": 0} class Item: def __init__(self, value): COUNTER["created"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): COUNTER["created"] = 0 def created(): return COUNTER["created"] def nested_lists(): reset() nested = [[Item(1), Item(2)], [Item(3), Item(4)]] piece = nested[:] list_copy = list(nested) shared = sum(1 for a, b in zip(nested, piece) if a is b) return created(), shared, piece[0] is nested[0], list_copy[0] is nested[0] nested_created, shared, piece_same, list_same = nested_lists() print(f"items created in the nested list {nested_created}, inner lists shared " f"in the slice copy {shared}/2") print(f"piece[0] is nested[0] -> {piece_same}, list(nested)[0] is nested[0] -> {list_same}") def leaves(k): return [o for inner_list in k for o in inner_list] def distinct_leaves(copy_, source): """Count of leaves in the copy not found in the source.""" old = leaves(source) return sum(1 for o in leaves(copy_) if not any(o is y for y in old)) print() reset() nested = [[Item(1), Item(2)], [Item(3), Item(4)]] print(f"items created while building the source: {created()} | " f"inner lists {len(nested)} | leaves {len(leaves(nested))}") COPIES = (("k[:]", nested[:]), ("list(k)", list(nested)), ("copy.copy(k)", copy.copy(nested)), ("copy.deepcopy(k)", copy.deepcopy(nested))) print(f"{'copy form':<20s}{'distinct leaves':>16s}{'outer same':>12s}" f"{'inner same':>13s}{'leaf same':>11s}") for label, c in COPIES: print(f"{label:<20s}{distinct_leaves(c, nested):>16d}{str(c is nested):>12s}" f"{str(c[0] is nested[0]):>13s}{str(c[0][0] is nested[0][0]):>11s}") print() shallow = COPIES[0][1] deep = COPIES[3][1] nested[0][0].value = 99 print(f"leaf mutated in the source -> nested[0][0] = {nested[0][0]}") print(f" shallow[0][0] = {shallow[0][0]} | deep[0][0] = {deep[0][0]}") nested.append([Item(5)]) print(f"inner list added to the source -> source slots {len(nested)} | " f"shallow slots {len(shallow)} | deep slots {len(deep)}") ``` ``` items created in the nested list 4, inner lists shared in the slice copy 2/2 piece[0] is nested[0] -> True, list(nested)[0] is nested[0] -> True items created while building the source: 4 | inner lists 2 | leaves 4 copy form distinct leaves outer same inner same leaf same k[:] 0 False True True list(k) 0 False True True copy.copy(k) 0 False True True copy.deepcopy(k) 4 False False False leaf mutated in the source -> nested[0][0] = Item(99) shallow[0][0] = Item(99) | deep[0][0] = Item(1) inner list added to the source -> source slots 3 | shallow slots 2 | deep slots 2 ``` #### The Outer Container Is New, the Contents Are Old The first two lines pay off this course's third claim exactly. The nested list creates 4 items; in the slice copy, both inner lists are shared — `piece[0] is nested[0]` is True — same for the `list()` copy. A copy is one layer deep. The lower table extends this to four copy forms and puts three in the same place. These three are shallow copy: a slice, the list constructor, the copy function. In all three, outer is separate, inner list is the same, leaf is the same, distinct-leaf count is 0. The fourth diverges: in a deep copy, all three columns are separate and distinct-leaf count is 4. That 0 against 4 is the whole difference between the two spellings. The last block shows what it means. When a leaf's inside is mutated in the source, the slice copy sees it — `shallow[0][0]` becomes `Item(99)` too — the deep copy does not. When a new inner list is added to the source, both stay at 2 slots, the source goes to 3. What's shared is the objects the outer container's slots point to, not the container itself; a shallow copy is independent by exactly one layer. #### Writing Is Not Copying The previous section read a slice and copied one layer. Writing to a slice reverses the measure: no container gets built, identity is preserved, length changes. This section measures that opposite, and the lesson's claim's limit. - **CO66 (continued)** — The write measurement proceeds sequentially on a single list. A deleted item's survival is tested with a separate name taken before the delete; the immutable-container test uses three separate, untouched containers. ```python """Writing to a slice is a mutation, not a copy; a full slice on an immutable container builds no new container.""" COUNTER = {"created": 0} class Item: def __init__(self, value): COUNTER["created"] += 1 self.value = value def reset(): COUNTER["created"] = 0 def created(): return COUNTER["created"] lst = [Item(i) for i in range(6)] identity = lst for label, d in (("k[4:1:-1]", lst[4:1:-1]), ("k[1:4:-1]", lst[1:4:-1]), ("k[::-2]", lst[::-2])): print(f"{label:<10s} slots {len(d)} -> {[o.value for o in d]}") print() reset() lst[1:4] = [Item(7)] print(f"k[1:4] = single item: created {created()} | same container {lst is identity} | " f"slots 6 -> {len(lst)} | {[o.value for o in lst]}") second = lst[1] held = lst[1:3] reset() del lst[1:3] print(f"del k[1:3]: created {created()} | same container {lst is identity} | " f"slots {len(lst)} | {[o.value for o in lst]}") print(f" deleted item lives under separate name -> {second is held[0]} | " f"stayed in container -> {any(second is x for x in lst)}") print() for label, container in (("list", [1, 2, 3]), ("tuple", (1, 2, 3)), ("string", "abc")): print(f"{label:<7s} k[:] is k -> {str(container[:] is container):<6s} k[:2] is k -> {container[:2] is container}") ``` ``` k[4:1:-1] slots 3 -> [4, 3, 2] k[1:4:-1] slots 0 -> [] k[::-2] slots 3 -> [5, 3, 1] k[1:4] = single item: created 1 | same container True | slots 6 -> 4 | [0, 7, 4, 5] del k[1:3]: created 0 | same container True | slots 2 | [0, 5] deleted item lives under separate name -> True | stayed in container -> False list k[:] is k -> False k[:2] is k -> False tuple k[:] is k -> True k[:2] is k -> False string k[:] is k -> True k[:2] is k -> False ``` The top three rows measure the negative step. `k[::-1]` already created 0 items and gave a new container in the main table; here it is the empty slice's counterpart under a negative step. `k[4:1:-1]` gives three slots while `k[1:4:-1]` gives 0: same bounds, opposite direction — a backward-going slice needs its start greater than its stop. The middle block measures writing. `k[1:4] = single item` creates 1 object — we built that one — and `lst is identity` stays True: the container did not change, its inside did. Slots drop from 6 to 4; three were taken and one put in, so assignment does not require matching counts. `del k[1:3]` completes the axis: 0 created, identity preserved, slots down to 2. On a list, `k[:]` returns a new container; assignment and deletion mutate the existing one in place. The deleted item does not vanish either: under the name taken before the delete, it is still the same object (True), no longer in the container (False) — deletion removes the slot. The lower block is the claim's limit. On a list, `k[:] is k` is False; on a tuple and a string, True — there, a full slice builds no new container, it hands back the existing one. "The outer container is new" does not hold for immutable types, since duplicating a container whose content cannot change has no measurable payoff. `k[:2] is k` is False on all three; the limit is specific to a full slice. The claim narrows — a slice renews a mutable container, never its contents. #### Who Does the Clipping All three measurements showed what a slice does; none showed who does it. Clipping an out-of-range range looked like a container's behavior, but is not: behind the colon syntax stands a named object. - **CO69** — A single slice recipe object is built and used on three separate containers; results are compared against the same recipe's spelled-out equivalent. - **CO70** — Resolved bounds are read from the recipe's own method, never computed by hand; slot count is also taken from the slice's length, and the two confirm each other. ```python """A slice recipe is an object: the same recipe is used on three containers, bounds resolve from it.""" SOURCE = list(range(6)) CONTAINERS = (("list", SOURCE), ("tuple", tuple(range(6))), ("string", "norths")) RECIPE = slice(1, 4) print(f"a recipe is an object: {type(RECIPE).__name__} | " f"start {RECIPE.start} stop {RECIPE.stop} step {RECIPE.step}") print(f"{'container':<10s}{'k[recipe]':<14s}{'same as k[1:4]'}") for label, container in CONTAINERS: print(f"{label:<10s}{str(container[RECIPE]):<14s}{container[RECIPE] == container[1:4]}") print(f"one recipe object used on {len(CONTAINERS)} different containers") print() print(f"{'spelling':<12s}{'resolved bounds':<20s}{'slots'}") for label, t in (("k[1:4]", slice(1, 4)), ("k[:]", slice(None, None)), ("k[::-1]", slice(None, None, -1)), ("k[-3:]", slice(-3, None)), ("k[4:100]", slice(4, 100)), ("k[10:20]", slice(10, 20))): print(f"{label:<12s}{str(t.indices(len(SOURCE))):<20s}{len(SOURCE[t])}") ``` ``` a recipe is an object: slice | start 1 stop 4 step None container k[recipe] same as k[1:4] list [1, 2, 3] True tuple (1, 2, 3) True string ort True one recipe object used on 3 different containers spelling resolved bounds slots k[1:4] (1, 4, 1) 3 k[:] (0, 6, 1) 6 k[::-1] (5, -1, -1) 6 k[-3:] (3, 6, 1) 3 k[4:100] (4, 6, 1) 2 k[10:20] (6, 6, 1) 0 ``` The upper block surfaces the object behind the syntax. `k[1:4]` does not pass two numbers to the container, it passes a single recipe with three fields; an unspecified one stays `None`. The same recipe is used on three separate containers and gives the same result as the spelled-out syntax in all three. The recipe is not bound to a container: it knows neither which one it'll apply to nor that container's length. The lower block shows where clipping happens. Once the recipe learns the length of the container it applies to, it resolves to three concrete numbers: `k[:]` becomes `(0, 6, 1)` and unspecified fields fill in; `k[-3:]` becomes `(3, 6, 1)`, the negative number subtracted from the length; `k[4:100]` becomes `(4, 6, 1)`, 100 clipped to 6; `k[10:20]` becomes `(6, 6, 1)` and comes up empty. An out-of-range range not counting as a fault is not a behavior choice, it is a measured step — clipping happens resolving the recipe, before ever entering the container. The negative-step recipe giving `(5, -1, -1)` is a product of the same resolution, and it explains `k[1:4:-1]`'s emptiness. #### Summary - All eight slice forms create 0 items, all eight return a new container on a list, and all eight have items from the source — a full slice included. - An out-of-range index raises `IndexError`, an out-of-range slice gets clipped, `k[1:4:-1]` gives 0 slots. Clipping happens resolving the container-independent recipe, before entering the container: `k[10:20]` → `(6, 6, 1)`. - Writing to a slice works on the same container and changes its length: `k[1:4] = single item` creates 1 object and drops slots from 6 to 4, `del k[1:3]` creates 0 and drops them to 2; identity is preserved in both, and a deleted item lives on if another name holds it. - A nested list creates 4 items; in the slice copy, both inner lists are shared (`piece[0] is nested[0]` → True), same for the `list()` copy — the outer container is new, the contents are old. Shallow copy's three spellings give 0 distinct leaves, deep copy gives 4. - The claim's limit: `k[:] is k` is False on a list, True on a tuple and a string. A full slice builds no new container on an immutable one — a slice renews a mutable container, never its contents. #### Next Step Every copy in this lesson was one layer deep, and building even that one layer touched every slot: taking a slice of a six-item container means reading six slots and writing them to a new one, a thousand on a thousand-item container. Even with 0 items created, slots touched equal the container's length. Is rebuilding the container to pass over its items required, though? The next lesson asks that in reverse: is there a way to reach a container's items in order, without building a new container and without touching the one at hand? The Python Fundamentals course measured the protocol's calling side; the next lesson moves to the building side, and its first job is this: writing the contract between `iter` and `next` by hand. ## Iteration and Functional Tools The iterator protocol, lazy evaluation, memory-friendly transformation chains, three comprehension forms, passing a function as an argument, and preserving metadata while wrapping behavior. ### Iterator Protocol Source: https://academia.sh/en/courses/python-data-structures/iterator-protocol You do not need to rebuild the container to see its items: a slice copy writes three references into a new list while an iterator writes zero, shares all three, and materializes no item. The previous lesson measured that a copy stays one layer deep: a list taken by slice was a new container, but every item inside it was the same object as before. Still, building that container was not free. The new list did not duplicate items, but it had to write each one's reference into itself — the copy produced no items, it **touched** all of them. This lesson's question goes one step further. To see a collection's items start to finish, does that container have to be rebuilt? Is it possible to pass over items without ever touching them, without building any new container? Python's answer is the **iterator** contract, and this lesson measures that contract on the course's axis: how many objects does a pass materialize, how many does it retain, how many does it share? #### The Contract The contract consists of two built-ins and two special methods. `iter(n)` requests an iterator from an object and calls the object's `__iter__` method. `next(y)` requests the next item from the iterator and calls `__next__`. When there is no item left to give, `__next__` does not return a value, it throws `StopIteration`. The Python Fundamentals course's loops lesson measured this protocol from the **consuming** side: which special method the `for` notation calls and how many times, and that what ends the loop is not a return value but an exception, were established there; that measurement is not repeated here. This lesson's side is the other one — the side that **writes** the contract. Two objects following the same protocol look identical from outside, but one materializes and retains its items ahead of time, the other materializes on demand and retains nothing at all. Syntax does not say this difference; numbers do. #### Iterable and Iterator The contract defines two roles, and confusing them is the most common mistake. An **iterable** object defines `__iter__`; it is not walked itself, it gives what will walk it. An **iterator** defines `__next__` and does the actual walking. A list is an iterable but not an iterator: `next(a_list)` does not work, `iter(a_list)` has to be called first. It is not forbidden for an object to define both. Then `__iter__`'s body returns itself, and the distinction disappears; the result of that is measured below. In the case where the distinction stays intact, `__iter__` produces a **fresh iterator** every time it is called. The definition that follows sits at the course's axis: what an iterator carries is not items, it is **where it left off**. A position is not an item, and it does not grow with item count. The measurement's assumptions: - **IF1** — The oracle is the rig itself: `Item` counts every production of itself, and sharing is shown with `is`; the measure for "how many objects were materialized" is this counter. - **IF2** — The shared reference's `Item` class is used as is, with its counting arrangement. - **IF3** — The source has three items. The count is kept small, because what is measured is not size, it is whether the pass builds a container. - **IF4** — "Held in container" is the number of item references an object coming out of the pass writes into itself: a list's length, zero for an iterator. **The measure is the reference count, not bytes measured.** - **IF5** — "Shared" is how many of the items coming out of the walk are the same, by `is`, as the object in the source. - **IF6** — `Counting` materializes items on demand and stores none of them; `Container` materializes items at construction and holds them in a list. The two classes differ only at this point, and both sign the same contract. - **IF7** — The single-pass measurement is done by calling `list()` twice on the same object; the item count the second call returns is the measure. - **IF8** — In the sentinel measurement, `next` is called with a second argument and tried twice on an exhausted iterator; the goal is showing that exhaustion is permanent. - **IF9** — In the two-pass measurement, all three of the three approaches request the same five-item source; the only thing that changes is where the items come from. The materialized count is the sum of the two passes; the retained count is the number of references staying alive between passes. #### Measurement ```python """Iterator contract: how many objects does a pass materialize, how many references does it hold.""" COUNTER = {"produced": 0} class Item: """An item that counts every production of itself.""" def __init__(self, value): COUNTER["produced"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): COUNTER["produced"] = 0 def produced(): return COUNTER["produced"] def retained(obj): """The number of Item objects an object keeps alive: on itself or in a list attribute.""" if isinstance(obj, list): return sum(isinstance(o, Item) for o in obj) count = 0 for d in getattr(obj, "__dict__", {}).values(): if isinstance(d, list): count += sum(isinstance(o, Item) for o in d) return count SOURCE = [Item(i) for i in range(3)] FORMS = (("iter(source)", lambda: iter(SOURCE)), ("source[:]", lambda: SOURCE[:]), ("list(source)", lambda: list(SOURCE)), ("reversed(source)", lambda: reversed(SOURCE)), ("copy via comprehension", lambda: [Item(o.value) for o in SOURCE])) print(f"{'pass form':<22s} {'new container':>13s} {'materialized':>12s}" f" {'held in container':>18s} {'shared':>7s}") for name, build in FORMS: reset() obj = build() container = "list" if isinstance(obj, list) else "no" held = retained(obj) shared = sum(1 for o in list(obj) if any(o is k for k in SOURCE)) print(f" {name:<20s} {container:>13s} {produced():12d} {held:18d} {shared:7d}") y = iter(SOURCE) print() print(f"iter(source) is source -> {y is SOURCE}, iter(y) is y -> {iter(y) is y}") print(f"next(y) is source[0] -> {next(y) is SOURCE[0]}") a, b = iter(SOURCE), iter(SOURCE) print(f"two separate iterators: {len(list(a))} and {len(list(b))} items") t = iter(SOURCE) print(f"same iterator twice: {len(list(t))} and {len(list(t))} items") class Counting: """An iterator that materializes items on demand.""" def __init__(self, n): self.n, self.i = n, 0 def __iter__(self): return self def __next__(self): if self.i >= self.n: raise StopIteration self.i += 1 return Item(self.i - 1) class Container: """An iterable that materializes items up front and holds them.""" def __init__(self, n): self.items = [Item(i) for i in range(n)] def __iter__(self): return iter(self.items) print() print(f"{'object':<12s} {'at setup':>9s} {'held at setup':>15s}" f" {'after two items':>16s} {'__iter__ gives':>15s}") for name, build in (("Counting(5)", lambda: Counting(5)), ("Container(5)", lambda: Container(5))): reset() n = build() setup, setup_held = produced(), retained(n) it = iter(n) next(it), next(it) print(f" {name:<12s} {setup:9d} {setup_held:15d} {produced():16d}" f" {('itself' if iter(n) is n else 'another object'):>15s}") counting = Counting(3) print() print(f"Counting(3) first pass {len(list(counting))} items, second pass {len(list(counting))} items") print(f"after exhaustion: {next(counting, 'sentinel')!r} and {next(counting, 'sentinel')!r}") container = Container(3) print(f"Container(3) first pass {len(list(container))} items, second pass {len(list(container))} items") remaining = [3, 2, 1, 0, 9] print(f"iter(callable, sentinel) -> {list(iter(lambda: remaining.pop(0), 0))}") def direct(): s = Counting(5) return len(list(s)), len(list(s)), 0 def collect_to_list(): s = list(Counting(5)) return len(list(s)), len(list(s)), len(s) def rebuild(): return len(list(Counting(5))), len(list(Counting(5))), 0 print() print(f"{'two-pass approach':<30s} {'materialized':>12s} {'retained':>9s}" f" {'first':>8s} {'second':>7s}") for name, f in (("walking the same iterator", direct), ("collecting to a list first", collect_to_list), ("rebuilding on every pass", rebuild)): reset() first, second, held = f() print(f" {name:<28s} {produced():12d} {held:9d} {first:8d} {second:7d}") ``` ``` pass form new container materialized held in container shared iter(source) no 0 0 3 source[:] list 0 3 3 list(source) list 0 3 3 reversed(source) no 0 0 3 copy via comprehension list 3 3 0 iter(source) is source -> False, iter(y) is y -> True next(y) is source[0] -> True two separate iterators: 3 and 3 items same iterator twice: 3 and 0 items object at setup held at setup after two items __iter__ gives Counting(5) 0 0 2 itself Container(5) 5 5 5 another object Counting(3) first pass 3 items, second pass 0 items after exhaustion: 'sentinel' and 'sentinel' Container(3) first pass 3 items, second pass 3 items iter(callable, sentinel) -> [3, 2, 1] two-pass approach materialized retained first second walking the same iterator 5 0 5 0 collecting to a list first 5 5 5 5 rebuilding on every pass 10 0 5 5 ``` #### A Pass That Builds No Container The top table lines up five pass forms side by side and splits them into three classes. **Those that rebuild the container.** `source[:]` and `list(source)` produce a new list and write **3** references into it. The number of `Item` objects materialized is **0** — no item is duplicated, and shared is **3**. This is the shallow copy the previous lesson measured: the outer container is new, what is inside is old. **Those that reproduce items.** The comprehension in the last row materializes **3** new `Item` objects and shared drops to **0**. Both the container and what is inside are new. **Those that do neither.** In the `iter(source)` and `reversed(source)` rows there is **no** new container, held in container is **0**, materialized is **0**, and shared is still **3**. The pass delivers all three of the three items, materializes none of them, and writes none of their references into itself. The opening question is answered here: passing over items without touching them is possible. An objection is fair here: `iter(source)` also produces an object — the iterator itself. But that object is not a **container**; it holds no items, it only carries a reference to the source and a position. The table's "materialized" column counts `Item` objects, and "held in container" counts item references; the iterator gives zero on both, because it is neither. The difference looks like a matter of one reference per three items. If the source had a thousand items, `list(source)` would write a thousand references, `iter(source)` would still write zero. The container's cost grows with item count, the iterator's does not: **the retained count is a function of item count, not of position.** #### What an Iterator Carries The three lines in the middle block separate the roles. `iter(source) is source` is **false**: a list is an iterable, but it does not do the walking itself; `iter` returns a separate object from it. `iter(y) is y` is **true**: requesting an iterator from an iterator gives back itself. This is why a `for` loop can accept both collections and iterators with the same notation — `iter` is applied to both, and on the second this call changes nothing. `next(y) is source[0]` is **true**: the item delivered is the source's own item, not a copy of it. An iterator is not a producer, it is a **deliverer**. The next two lines show where the position is held. **Two separate iterators** taken from the same list are independent of each other: each gives **3** items. The **same iterator** walked twice gives **3** and **0**. Because the position lives in the iterator, not the list, every new iterator requested from the list starts from zero; an existing iterator continues from where it left off and eventually exhausts. #### Two Classes Writing the Contract The second table compares two classes that sign the same contract. `Counting` materializes **0** objects at setup and retains **0**; once two items are requested, the produced count rises to **2**. `Container` materializes **5** at setup, retains **5**, and after two items are requested the number is still **5** — production had already finished. The two objects are indistinguishable from outside. Both go into a `for` loop, both give the same five values, `iter` and `next` work on both. The distinction is only in the numbers: one does the work **at setup**, the other **on demand**. The last column gives the second distinction. `Counting.__iter__` returns **itself**; `Container.__iter__` takes **another object** from its inner list on every call. This shows up in the two lines below: `Counting(3)` gives **3** items on the first pass, **0** on the second — it exhausts. `Container(3)` gives **3** on both passes, because every pass starts with a fresh iterator. Single-pass behavior is not a flaw, it is the contract's direct consequence. The contract says "give the next item on request"; it does not say "give the same items a second time too." For an iterator to give a second pass, it would have to store every item it saw — that is, do exactly the thing it avoids. **An object that retains nothing cannot rewind.** Exhaustion is permanent. When `next` is called two more times on an emptied `Counting`, both give the sentinel value; the object does not renew itself. #### The Cost of Two Passes The last table measures the practical counterpart of this result in three ways. On hand is a single-pass source, and items are needed twice. **Walking the same iterator twice** does not work: **5** and **0**. Materialized is **5**, retained is **0** — the cheapest row, but it does not give a second pass. **Collecting to a list and walking it twice** gives the second pass: **5** and **5**. Materialized is still **5**, because the items were produced once and stored. The cost shows in the retained column: it rose from **0** to **5**. Had item count been a thousand, this column would be a thousand. **Rebuilding the source on every pass** also gives the second pass, and retained stays at **0**. Its cost shows in the other column: materialized rose from **5** to **10**, because five items were produced twice. This route only works if the source can be rebuilt; a network stream or user input may not give the same items a second time. None of the three rows beats the sum of the others, and there is a real choice here: **there is no two-pass without retaining.** You either store the items, reproduce them, or settle for a single pass. An iterator does not remove this choice; it just makes the third option free. #### The Contract's Two Escape Hatches The last two lines show two built-in flexibilities of the contract. Called with a second argument, `next(y, sentinel)` does not throw `StopIteration`, it returns the given value. The exception turns into a value; it is the way to ask "is it done?" without setting up a `try` block. The value chosen as the sentinel has to be one that **cannot occur** in the stream, or the ending gets mixed up with an item — this is the same reason `StopIteration` is not a return value. Called with two arguments, `iter` does something entirely different: it produces an iterator whose source is not a collection but a **callable**. In the example, every `next` takes one item from the front of a list, and the pass ends when the sentinel **0** shows up. The result is `[3, 2, 1]` — the sentinel itself is not delivered. This way, a file, a queue, or any source giving one next item per call can be fed into a `for` loop without ever being turned into a collection. #### Summary - The iterator contract is two built-ins and two special methods: `iter` calls `__iter__`, `next` calls `__next__`; `StopIteration` is thrown when no item is left. - Passing, copying, and reproducing are three separate jobs: `iter` builds no container and writes **0** references, `list(source)` writes **3**, and a comprehension additionally materializes **3** new objects. Sharing is measured in all three, and is **0** only in the last. - An iterable defines `__iter__`, an iterator defines `__next__`; `iter(a_list)` gives a separate object from the list, `iter(an_iterator)` gives the object itself. What an iterator carries is not items, it is the position left off at. - Two classes signing the same contract are indistinguishable from outside but differ in their numbers: **0** versus **5** production at setup, **0** versus **5** retention. - Single-pass behavior is a consequence of the contract: an object whose `__iter__` returns itself gives **3** then **0** items, one returning a fresh iterator gives **3** on both passes. An object retaining nothing cannot rewind, and exhaustion is permanent. #### Next Step The `Counting` class needed three methods, a bound, and a position field across five lines — all for one thing: remembering where it left off. This is work repeated in every hand-written iterator, and when the position is not a single number (a nested walk, a branched search), the class grows fast. The next lesson measures the form where the language takes this job off your hands: a function whose body pauses and resumes from where it left off. The number to be measured is this — calling such a function, how many of the thousand productions in its body does it do **at call time**? ### Generators Source: https://academia.sh/en/courses/python-data-structures/generators Calling a generator function does not run a single line of its body: on a thousand-item stream, setup materializes 1000 objects for a comprehension, 0 for a generator, and stays at 3 once three items are requested. The previous lesson measured the iterator contract and built a class writing it by hand: `Counting` needed two special methods, a bound, and a position field in five lines — all for one job, remembering where it left off. That job repeats in every iterator, and when the position is not a single number, the class grows fast. A nested walk needs multiple counters, a branched search needs a stack; each has to be carried by hand. Yet an ordinary function already carries this information. While a function runs, which line it is on and which values its local names are bound to are known; they only vanish when the function ends. This lesson's question is: if a function could **pause instead of ending**, would the position ever need to be written separately? Python's answer is the **generator** function, and the number to measure is this — calling such a function, how many of the thousand productions in its body does it do at call time? #### A Pausing Function If `yield` appears in a function body instead of `return`, that function is no longer an ordinary function. When called, its body does not run; what comes back is a **generator object**. The body only starts running once an item is requested from that object, and **stops** when it reaches the first `yield` statement. Local names, loop counters, and the call frame stay exactly as they were where it stopped. When the next request arrives, execution resumes right after the `yield`. The distinction is sharp here: `return` tears down the frame, `yield` **suspends** it. The Programming Fundamentals course introduced lazy evaluation as a paradigm choice — not computing a value until the moment it is used. What is measured here is not the name of that choice, it is which mechanism Python gives it through, and **how many objects it costs**. #### A Generator Is an Iterator A generator object signs the previous lesson's contract: `__iter__` and `__next__` are defined, `__iter__` returns itself, and `StopIteration` is thrown once the body ends. That is, a generator is the language-written form of what the `Counting` class wrote by hand — the **writing side** of the contract, without building a class. Two consequences follow directly. A generator is **single-pass**, because `__iter__` returns itself. And once exhausted it does not renew, because its body has reached its end. Both were already established as consequences of the contract in the previous lesson; here they are measured once more. The measurement's assumptions: - **IF10** — The shared reference's `Item` class and the number `N = 1000` are used as is; the counting arrangement is unchanged. - **IF11** — All three forms define the **same** job: a thousand-item stream. The only thing that changes is notation; the oracle is the rig itself, because the object counts its own production. - **IF12** — The "at setup" measurement is taken right after the line defining the form runs. The "after three items" measurement is taken after three items are requested; in the comprehension this request is `list[:3]`, in the other two it is `next`. - **IF13** — The trace log is a list placed inside the body; every line writes which point was reached. This list is the measure for "did the body run." - **IF14** — In the trace measurement, item count is three; what is measured is not the count, it is the relationship between calls and the body's progress. - **IF15** — The endless-generator measurement is deliberate: setup producing zero does not come from item count being finite. - **IF16** — In the joining measurement, the two wings have **400** and **600** items; the total is still **1000**, and all three forms give the same item sequence. - **IF17** — The "up to first item" column is the production count after only one item is taken from the join; this column is what separates the forms. - **IF18** — In the closing measurement, the stream has a thousand items but is released with `close` after three are taken; the trace line placed in the `finally` block also writes the production count at that moment, so when the closing runs can be measured. #### Measurement ```python """Generator: when does the body run, how many objects does setup materialize.""" COUNTER = {"produced": 0} TRACE = [] class Item: """An item that counts every production of itself.""" def __init__(self, value): COUNTER["produced"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): COUNTER["produced"] = 0 def produced(): return COUNTER["produced"] N = 1000 def generator_function(n=N): for i in range(n): yield Item(i) def comprehension(n=N): reset() items = [Item(i) for i in range(n)] at_setup = produced() first_three = items[:3] return at_setup, produced(), len(first_three) def generator_expression(n=N): reset() stream = (Item(i) for i in range(n)) at_setup = produced() first_three = [next(stream) for _ in range(3)] return at_setup, produced(), len(first_three) def generator_call(n=N): reset() stream = generator_function(n) at_setup = produced() first_three = [next(stream) for _ in range(3)] return at_setup, produced(), len(first_three) print(f"{'form':<24s} {'at setup':>10s} {'after three items':>18s} {'got':>5s}") for name, f in (("comprehension", comprehension), ("generator expression", generator_expression), ("generator function call", generator_call)): a, b, c = f() print(f" {name:<22s} {a:10d} {b:18d} {c:5d}") def traced(n=3): TRACE.append("body started") for i in range(n): TRACE.append(f"before yield {i}") yield Item(i) TRACE.append(f"after yield {i}") TRACE.append("body ended") return "done" TRACE.clear() g = traced() print() print(f"trace after the call: {TRACE}") next(g) print(f"after first next: {TRACE}") next(g) print(f"after second next: {TRACE}") print(f"is the generator an iterator: iter(g) is g -> {iter(g) is g}") TRACE.clear() one = traced(1) next(one) try: next(one) except StopIteration as e: print(f"when the body ends: {TRACE[-1]!r}, value carried by the exception {e.value!r}") single = generator_function(3) print() print(f"generator function is single-pass: {len(list(single))} and {len(list(single))} items") def endless(): i = 0 while True: yield Item(i) i += 1 reset() stream = endless() setup = produced() [next(stream) for _ in range(3)] print(f"endless generator: at setup {setup}, once three items are requested {produced()}") def branch(a, b): yield from generator_function(a) yield from generator_function(b) def manual_branch(a, b): for o in generator_function(a): yield o for o in generator_function(b): yield o def intermediate_list(a, b): return list(generator_function(a)) + list(generator_function(b)) print() print(f"{'joining form':<22s} {'at setup':>10s} {'up to first item':>16s}" f" {'once fully walked':>17s}") for name, f in (("yield from", branch), ("nested for + yield", manual_branch), ("appending two lists", intermediate_list)): reset() n = f(400, 600) at_setup = produced() y = iter(n) next(y) first = produced() list(y) print(f" {name:<20s} {at_setup:10d} {first:16d} {produced():17d}") def accumulator(): total = 0 try: while True: incoming = yield total total += incoming finally: TRACE.append("accumulator closed") def source(n=N): try: for i in range(n): yield Item(i) finally: TRACE.append(f"source closed, produced by then {produced()}") TRACE.clear() acc = accumulator() first = next(acc) print() print(f"yield is an expression: first value {first}, send(5) -> {acc.send(5)}," f" send(7) -> {acc.send(7)}") acc.close() print(f"trace after close call: {TRACE}") TRACE.clear() reset() stream = source() three = [next(stream) for _ in range(3)] stream.close() print(f"three items taken from a thousand-item stream, then left: got {len(three)}," f" produced {produced()}") print(f"closing trace: {TRACE}") ``` ``` form at setup after three items got comprehension 1000 1000 3 generator expression 0 3 3 generator function call 0 3 3 trace after the call: [] after first next: ['body started', 'before yield 0'] after second next: ['body started', 'before yield 0', 'after yield 0', 'before yield 1'] is the generator an iterator: iter(g) is g -> True when the body ends: 'body ended', value carried by the exception 'done' generator function is single-pass: 3 and 0 items endless generator: at setup 0, once three items are requested 3 joining form at setup up to first item once fully walked yield from 0 1 1000 nested for + yield 0 1 1000 appending two lists 1000 1000 1000 yield is an expression: first value 0, send(5) -> 5, send(7) -> 12 trace after close call: ['accumulator closed'] three items taken from a thousand-item stream, then left: got 3, produced 3 closing trace: ['source closed, produced by then 3'] ``` #### The Cost of Setup The top table is the first half of the shared reference's second claim, and all three rows define the same job: a thousand-item stream. The **comprehension** materializes **1000** objects on the very line where it is written. Once three items are requested the number does not change — because all of them had already been produced; `list[:3]` only shows three of what already exists. The **generator expression** and **generator function call** materialize **0** at setup. Once three items are requested it rises to **3**. The remaining 997 objects are never born, because nobody requested them. The gap between the two numbers is invisible in the notation. All three rows are a single statement, all three name a thousand-item stream, and all three can be fed into a `for` loop afterward. The only thing that says whether setup is **1000** or **0** is the difference between square brackets and parentheses, and the `yield` keyword. The limit of the laziness here has to be read correctly. **0** does not mean the work was not done; it means it was **not done yet**. Once three items are requested, three objects are born; if a thousand were requested, a thousand would be born. The number this lesson measures only answers **when**; the answer to **how many in total** is the subject of the next lesson. The generator expression row's notation — parentheses instead of square brackets — is not this lesson's subject; the next lesson measures it on its own. It sits in this table only to give the setup count. #### Where the Body Stops The middle block shows the body's progress through the trace log, and the first line is the most surprising: after the generator function is called, the trace is **empty**. Not a single line of the body has run. The call did not start a job, it **built an object**. After the first `next` call the trace has two lines: the body started and reached the first `yield`. It stopped there. After the second call two more lines were added — execution resumed **right after** the `yield`, moved to the loop's next turn, and stopped again at the second `yield`. The local name `i` was preserved between the two calls; nobody wrote it anywhere, the frame stayed suspended exactly as it was. This is the exact counterpart of what the `Counting` class did by hand. There, position was an attribute, advanced by hand on every call; here, position **is the body itself**, and the language preserves it. The `iter(g) is g` line confirms the other end of the contract: a generator is its own iterator. Single-pass behavior comes from the same place — `3` then `0`. #### The Value Carried by the Ending When the body reaches its end, the trace writes its last line and `StopIteration` is born. What is interesting is that the exception is **not empty**: the value of the `return "done"` statement is carried on top of the exception. This shows how `return` and `yield` split roles in a generator. `yield` gives the stream's items; `return` gives the stream's **result**, and is not part of the stream. A `for` loop walking a generator never sees this value, because the loop catches `StopIteration` and discards it. Whoever wants the value has to catch the exception themselves. The endless-generator line shows laziness does not depend on finiteness: a generator whose body is a loop that never ends still materializes **0** at setup and stays at **3** once three items are requested. Writing such a stream with a comprehension is impossible — a comprehension tries to exhaust an endless source and never leaves its first line. Laziness here is not an optimization, it is a condition for **expressibility**. #### Delegation The last table measures three ways of joining two streams, and all three give the same **1000** items. `yield from` assigns a generator the job of delivering another generator's items: the outer generator suspends its own body and hands requests off to the inner one. At setup **0**, once the first item is taken **1**. The hand-written form with a `for` loop gives the same numbers; `yield from` is that loop's shorthand, and it also carries through the inner generator's ending value. The **appending two lists** row stands apart. At setup **1000** — because the `list()` calls exhaust both wings all the way through. A thousand objects are born and two intermediate lists are built before the first item is even reached; the `+` operator then produces a third list on top. The result is the same, the order is the same, the items are the same; the only thing that differs is **how many productions** the first item comes after. The measurement also says where a chain breaks: the moment a single `list()` call enters a lazy stream, laziness ends at that point in the chain. Even if the links after it are written lazily, they cannot undo the thousand productions that already happened before them. #### Two Directions of the Channel, and Closing The last four lines show `yield` is not a one-way exit. `yield` is not a statement but an **expression**, and it has a value: when a suspended generator is woken with `send`, the waiting `yield` expression returns the sent value and the body continues from there. The accumulator in the measurement gives **5** with `send(5)`, **12** with `send(7)`; the running total sits in the body's local name between the two calls. The first `next` call is mandatory in this arrangement: if the body has not yet reached its first `yield`, there is no expression to receive a sent value. This is why every generator fed with `send` is first advanced once; the **0** in the measurement is the starting value that first `yield` gives. The last two lines measure the most overlooked side of lazy streams. Taking three items from a thousand-item stream and then leaving it, produced stays at **3** — expected so far. What is unexpected is that the `finally` block **runs**: the `close` call wakes the suspended body at the point it stopped, raises an exception there, and runs the `finally` blocks. The trace line proves this, and it also writes the production count at that moment. The practical counterpart: if a generator is operating on an open resource, cutting the stream short does not leave that resource hanging. The Programming Fundamentals course's context managers lesson established that release happens even under an exception; the `try`/`finally` in a generator's body gives the same guarantee for a **suspended** frame. Laziness defers the work, not the responsibility. #### Summary - Calling a function containing `yield` runs not a single line of its body; what comes back is a generator object. `return` tears down the frame, `yield` suspends it. - On a thousand-item stream, a comprehension materializes **1000** objects at setup; a generator expression and a generator function call materialize **0**; once three items are requested, both stay at **3**. The notations are single statements and look alike; the numbers do not. - A generator signs the previous lesson's contract: `iter(g) is g` is true, the stream is single-pass, and a second pass gives **0** items. The language does what a hand-written iterator class did. - The body stops at every `yield` and resumes from that point on the next request; local names are preserved in between. Once the end is reached, the `return` value is carried on `StopIteration`, and a `for` loop walking it never sees this value. - `yield from` delegates without building an intermediate container: **1** production up to the first item. Doing the same job by appending two lists takes **1000** productions before the first item and needs three containers. - `yield` is an expression and returns the value sent with `send`; when a thousand-item stream is left with `close` after three items, production stays at **3**, but the body's `finally` block still runs. #### Next Step This lesson only measured the moment of setup, and there was a gap there: **1000** against **0**. But a stream is consumed sooner or later — if a thousand items are really going to be collected, the generator has to produce those thousand objects too. The next lesson asks exactly this question: for two notations that carry the same job to its end, how many objects has each produced by the end of the job, and how many does each still hold on to? The first half of the answer will be expected, the second half will not — and only there does it become visible what laziness actually reduces. ### Generator Expressions Source: https://academia.sh/en/courses/python-data-structures/generator-expressions Summing a thousand items, a generator and a comprehension both produce 1000 objects and both give 499500; the only place they split is what stays held in a list — 0 against 1000. Laziness defers production, it does not avoid it. The previous lesson measured only the moment of setup, and there was a gap there: a comprehension materializes **1000** objects on its first line, a generator materializes **0**. But a stream is not written to be set up and left; it is consumed sooner or later. If a thousand items are really going to be collected, the generator has to produce those thousand objects too. This lesson's question: for two notations that carry the same job to its end, how many objects has each produced once done, and how many does each still hold? Half the answer will be expected, the other half will not — and only there does it become visible what laziness actually reduces. The lesson also builds the generator expression's own notation, measured here on its own. #### Notation A generator expression is a list comprehension with its square brackets replaced by parentheses, and what it produces is not a list but a **generator object**. Given as the sole argument to a function, the parentheses are not written separately; the expression in `sum(o.value for o in stream)` is itself a generator expression on its own. The object it produces is the same kind the previous lesson's generator function returned: an iterator, single-pass, `__iter__` returning itself. The difference is only in notation. A generator function takes a name, can carry multiple statements, can branch; a generator expression is nameless and states a single transformation. The choice between them is not one of cost but of expression width — the measured numbers are the same in both. The Programming Fundamentals course introduced lazy evaluation as a concept at the entrance to functional programming: a value is not computed until it is used. This lesson does not repeat that concept; it counts **how many objects** its Python counterpart costs — and the number turns out different from what the name suggests. The measurement's assumptions: - **IF19** — The shared reference's `Item` class and the number `N = 1000` are used as is; the counting arrangement is unchanged. The oracle is the rig itself. - **IF20** — The two consumption forms target the **same** result: the value sum of a thousand items. The result column is the measurement's correctness check; if the two forms gave different results, the comparison would be invalid. - **IF21** — "Held in list" is the number of items still alive in a container once the sum is done; it is zero in the generator form because no such container is built. - **IF22** — The chain measurement has three links: produce, filter, transform. The two forms apply the same links in the same order; the only thing that changes is whether each link is a container or a stream. - **IF23** — The chain's "held in containers" count is the sum of the three lists' lengths. **The memory claim is built on the object count, not measured bytes; duration is not measured.** - **IF24** — In the early-exit measurement, the sought condition is satisfied at the fifth item; the condition's position is fixed and decides when the consumer stops. - **IF25** — The single-pass measurement is done on a small ten-item stream; what is measured is not size, it is the value the second summation returns. - **IF26** — In the source-evaluation measurement, `give_source` counts its own call count; this count is the measure of when the outer iterable is evaluated. - **IF27** — In the last table, every operation is tried separately on two containers, and setup is reset before each trial; the exception class of a failing operation is also taken from the run. Only the standard library is used. #### Measurement ```python """Generator expression: same result, same production, different retention.""" import itertools COUNTER = {"produced": 0} class Item: """An item that counts every production of itself.""" def __init__(self, value): COUNTER["produced"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): COUNTER["produced"] = 0 def produced(): return COUNTER["produced"] N = 1000 def generator_consumption(n=N): reset() stream = (Item(i) for i in range(n)) total = sum(o.value for o in stream) return produced(), total, 0 def comprehension_consumption(n=N): reset() items = [Item(i) for i in range(n)] total = sum(o.value for o in items) return produced(), total, len(items) print(f"{'consumption form':<27s} {'produced':>9s} {'total':>8s}" f" {'held in list':>13s}") for name, f in (("summing via generator", generator_consumption), ("summing via comprehension", comprehension_consumption)): p, t, held = f() print(f" {name:<25s} {p:9d} {t:8d} {held:13d}") def lazy_chain(n=N): reset() evens = (o for o in (Item(i) for i in range(n)) if o.value % 2 == 0) squares = (o.value * o.value for o in evens) at_setup = produced() total = sum(squares) return at_setup, produced(), total, 0 def list_chain(n=N): reset() all_items = [Item(i) for i in range(n)] evens = [o for o in all_items if o.value % 2 == 0] squares = [o.value * o.value for o in evens] at_setup = produced() total = sum(squares) return at_setup, produced(), total, len(all_items) + len(evens) + len(squares) print() print(f"{'chain form':<29s} {'at setup':>10s} {'produced':>9s}" f" {'total':>10s} {'held in containers':>19s}") for name, f in (("three generator expressions", lazy_chain), ("three list comprehensions", list_chain)): s, p, t, held = f() print(f" {name:<27s} {s:10d} {p:9d} {t:10d} {held:19d}") def early_exit(n=N): reset() stream = (Item(i) for i in range(n)) found = any(o.value > 4 for o in stream) return produced(), found def early_exit_list(n=N): reset() items = [Item(i) for i in range(n)] found = any(o.value > 4 for o in items) return produced(), found print() p1, f1 = early_exit() p2, f2 = early_exit_list() print(f"when the consumer stops at the fifth item: generator expression produced {p1} objects" f" (answer {f1}), comprehension {p2} (answer {f2})") reset() stream = (Item(i) for i in range(10)) first = sum(o.value for o in stream) second = sum(o.value for o in stream) print(f"same generator expression summed twice: {first} and {second}," f" produced {produced()}") CALLS = {"source": 0} def give_source(): CALLS["source"] += 1 return [1, 2, 3] stream = (x for x in give_source()) at_setup = CALLS["source"] list(stream) print(f"was the outer iterable evaluated at setup: {at_setup} calls," f" after walking {CALLS['source']}") remaining = [5, 6, 7] stream = (x * 10 for x in remaining) remaining.append(8) print(f"did an item added to the source afterward enter the stream: {list(stream)}") reset() a_set = {o.value % 3 for o in (Item(i) for i in range(9))} print(f"generator expression given to a set constructor: produced {produced()}," f" held {len(a_set)}") OPERATIONS = (("len(n)", lambda n: len(n)), ("n[2]", lambda n: n[2].value), ("n[:3]", lambda n: len(n[:3])), ("islice(n, 3)", lambda n: len(list(itertools.islice(n, 3))))) print() print(f"{'operation':<16s} {'list':>25s} {'generator expression':>28s}") for name, operation in OPERATIONS: row = [] for build in (lambda: [Item(i) for i in range(N)], lambda: (Item(i) for i in range(N))): reset() n = build() try: result = f"{operation(n)} ({produced()} productions)" except TypeError as e: result = f"{type(e).__name__} ({produced()} productions)" row.append(result) print(f" {name:<14s} {row[0]:>25s} {row[1]:>28s}") reset() stream = (Item(i) for i in range(N)) exists = any(o.value == 2 for o in stream) at_test = produced() left = sum(1 for _ in stream) print() print(f"membership test on a stream: answer {exists}, produced during test {at_test}," f" remaining in stream {left}") ``` ``` consumption form produced total held in list summing via generator 1000 499500 0 summing via comprehension 1000 499500 1000 chain form at setup produced total held in containers three generator expressions 0 1000 166167000 0 three list comprehensions 1000 1000 166167000 2000 when the consumer stops at the fifth item: generator expression produced 6 objects (answer True), comprehension 1000 (answer True) same generator expression summed twice: 45 and 0, produced 10 was the outer iterable evaluated at setup: 1 calls, after walking 1 did an item added to the source afterward enter the stream: [50, 60, 70, 80] generator expression given to a set constructor: produced 9, held 3 operation list generator expression len(n) 1000 (1000 productions) TypeError (0 productions) n[2] 2 (1000 productions) TypeError (0 productions) n[:3] 3 (1000 productions) TypeError (0 productions) islice(n, 3) 3 (1000 productions) 3 (3 productions) membership test on a stream: answer True, produced during test 3, remaining in stream 997 ``` #### Same Production, Separate Retention The top table completes the shared reference's second claim, and the first column breaks the expectation. **Produced is 1000 in both.** The lazy form does not produce fewer objects; a thousand items were requested, a thousand were born. The total column matches too: both **499500**. The two notations do the same job, give the same result, pay the same cost. The only column where they split is the last. Once summing is done, **1000** items still sit in a list in the comprehension form; **0** in the generator form. Each of the thousand produced objects was born, contributed to the sum, and became unreachable because nothing wrote it into a container. In the comprehension all of them stayed in the list, because that is exactly the list's job. From this comes the shared reference's sentence: **laziness does not reduce production, it reduces retention.** This is narrower than the name "lazy evaluation" suggests. The name implies work will not be done; the measurement shows it is done, and only **when** and **what is left afterward** change. **Laziness defers production, it does not avoid it.** The previous lesson's **0** has to be read together with this table. Zero at setup is not a promise of savings, it is a record of **deferral**. Whether the promise is kept depends on how the stream is consumed, not on how it is written. #### The Chain's Intermediate Containers The middle table measures not a single transformation but a three-link chain: produce, filter, transform. The total is the same again — **166167000** — and produced is again **1000**. Two columns split. The setup column repeats the previous lesson's result: the lazy chain **0**, the list chain **1000**. But the real difference is in the last column. Once the list chain finishes, **2000** references sit in containers: a thousand-item source list, a five-hundred-item filtered list, a five-hundred-item transformed list. In the lazy chain this number is **0**. Intermediate-container count grows with chain length. A four-link list chain builds four containers, a five-link one five; each link wants to see all of what came before and stores what it saw. In the lazy chain, container count does not grow with link count, because no link ever wants all of what came before — each wants **one** item at a time. Together with the previous lesson's last row, this gives the chain's breaking point: the moment a single `list()` call enters the chain, a container is built at that point, and the rest of the chain's laziness cannot undo it. #### Early Exit's Source The next line measures the most natural objection to the claim. When the consumer stops at the fifth item, the generator expression produces **6** objects, the comprehension **1000**. Here laziness really does look like it avoided production. The distinction: what enables the avoidance is not laziness, it is the **consumer stopping early**. `any` stops asking once it finds what it is looking for; the lazy stream produces nothing that was not asked for. In the comprehension, even if the consumer stops early, production already finished — the list was filled before `any` asked its first question. Together, the two cases give the claim's full shape: laziness **ties production to the consumer**. Wanting everything produces everything (first table: 1000); exiting early leaves what was not needed unproduced (this line: 6). In the comprehension, production is independent of the consumer and is **1000** either way. What laziness gives is not avoidance, it is the **possibility** of avoidance. Why the sixth object gets produced is part of the same pattern: the condition is satisfied at the fifth item, but `any` can only know this **after** taking it, and taking it costs one more production. #### When the Source Is Evaluated The last four lines measure two subtle sides of a generator expression. The first is single-pass behavior. Summed twice, the same generator expression gives **45** and **0**; produced stays at **10**. The second sum runs on an empty stream, and `sum` returns zero on an empty stream — no error, a silent zero. This is single-pass behavior's most treacherous consequence: an exhausted stream cannot be told apart from an empty one. The second is when the source is read. `give_source` is called **once** at setup, and stays at **1** after the stream is walked. The outermost iterable in a generator expression is evaluated **immediately**; what is deferred is pulling items, not finding the source. A wrong source name or an erroring call shows up at setup. The next line shows this rule's limit. The source list was evaluated at setup, but an item added afterward **entered** the stream: the result is `[50, 60, 70, 80]`. What got evaluated was the list **object**, not a snapshot of its content — the same distinction as the previous topic's view measurement: a binding was established, no copy taken. If a lazy stream's source changes before consumption, the stream sees the changed state. The last line shows where a generator expression can be given: a stream given to a set constructor makes it produce **9** objects, and **3** items are retained afterward. The gap between materialized and retained is visible here too — the container decides for itself how much it keeps. #### What a Stream Cannot Do The last table measures what is given up in exchange for not retaining, and the same exception sits in three of its rows. `len(n)` gives **1000** on a list, `TypeError` on a stream. A stream does not know its length, because knowing it would require going all the way to the end and remembering that it did. `n[2]` and `n[:3]` give the same answer: a stream cannot be indexed or sliced. Everything the previous topic's slicing lesson measured — a slice building a new container, sharing inner items — can never even be asked of a stream, because a slice requires looking backward, and a stream has nowhere to look back to. The shared reason: **every one of these questions requires retention.** Length, index, and slice all assume items sit together; a stream answers none of the three because it refuses to do exactly that. Zero retention costs three built-in operations. The fourth row shows where the loss can be made up. The standard library's `islice` tool takes the first three items from a stream and causes only **3** productions; the same result on a list comes only after **1000**. A job that looks like a slice, defined without looking backward, becomes possible on a stream too — but the result is not a slice, it is another stream, and it too is single-pass. The last row is single-pass behavior's most attention-demanding consequence. The membership test on a stream answers **True**, only **3** objects produced during the test; but **997** items remain in the stream after. The test **consumed** the stream: the three items asked about do not come back. A second test on the same stream would search from the third item onward, and the first three would never be seen. A list has no such side effect; asking on a stream is reading. #### Summary - Summing a thousand items, a generator and a comprehension both produce **1000** objects and both give **499500**; the only place they split is what stays held — **0** against **1000**. Laziness defers production, it does not avoid it. - In a three-link chain, produced is still **1000**, but the list form holds **2000** references in containers at the end, the lazy form **0**. Intermediate container count grows with chain length in a list, not in a stream. - When the consumer stops at the fifth item, a generator expression produces **6**, a comprehension **1000**. What enables the avoidance is not laziness but the consumer stopping; laziness only makes it **possible**. - A generator expression is single-pass and behaves silently empty once exhausted: a second sum gives not an error but **0**. - The outermost iterable is evaluated at setup (**1** call), but what gets evaluated is the object itself: an item added to the source afterward enters the stream. #### Next Step These two lessons measured the difference between square brackets and parentheses, but never opened up the square brackets themselves. Yet the same notation can build three separate containers — list, set, and dict — and all three take the same items from the same source and hold a **different** number of them. What is more, the notation can nest, and one comprehension inside another produces an unbuilt container. The next lesson counts these: of the same thousand items, how many does each of the three comprehension forms retain, and does where a filter clause is written change the number of objects produced? ### Comprehension Syntax Source: https://academia.sh/en/courses/python-data-structures/comprehension-syntax From the same thousand items, a list comprehension retains 1000, a set and a dict comprehension retain 100; whether a filter condition is written before or after production changes the materialized count from 5 to 10. The previous two lessons measured the difference between square brackets and parentheses, and separated by number what laziness reduces and what it does not. But the square brackets themselves were never opened up: in every measurement, comprehension stood only as "the form producing everything now." Yet the same notation can build three separate containers. Square brackets produce a list, curly braces a set, the same braces with a colon a dict. All three take the same items from the same source, but not all three **retain** the same number of them. This lesson asks two questions: of the same thousand items, how many does each of the three comprehension forms retain, and does where a filter condition is written change the number of materialized objects? #### Three Containers, One Notation A comprehension is a loop and a container setup squeezed into a single statement. The syntax of the three forms is nearly identical, and the only difference between them is the brace and the item expression. Comprehension notation differs from a generator expression only by the brace, and that single character entirely changes setup behavior — the previous lesson measured this. Where the three containers split is how they accept an item. A list accepts every item in order and rejects none. A set places an item by its hash value and does not take a new one if an equal one already exists. A dict does the same job on the key, but **replaces** the value: when the same key arrives a second time, the old value drops. The Data Structures course built these three containers' mechanism — the hash table, collisions, placement — and it is not repeated here. What is measured is how many **items** the same source comes down to in the three containers. #### Two Places for a Condition A comprehension accepts a condition in two separate places, and they are not the same thing. A **filter clause** comes at the end of the notation and operates on the loop variable: a turn that does not pass the condition never runs the item expression at all. A **conditional expression** sits inside the item expression itself and picks a result on every turn; it filters no turn out. Confused with each other, the result can look the same, but the number does not. The measurement separates them. The measurement's assumptions: - **IF28** — The shared reference's `Item` class is used as is, with its counting arrangement; the oracle is the rig itself. - **IF29** — All three comprehensions run on the **same** thousand-item source, and the source was set up before the measurement; this is why all three "materialized" columns are zero. What is measured is retention. - **IF30** — The set and dict comprehensions group items by `value % 100`; the number is arbitrary and chosen only so a collision can be observed. - **IF31** — "Shared Item" is whether the objects inside the container are the source's own objects; this column is zero for a container holding a derived number. - **IF32** — The condition measurement is done on ten items, and the condition lets half of them through; what is measured is not size, it is the production difference between the two notations. - **IF33** — In the nested measurement, the table has **four rows, three columns**; the total item count is **12** in all three notations. "Containers built" includes the outer container too. - **IF34** — In the scope measurement, the comprehension's loop name is deliberately made to collide with an outer variable of the same name. - **IF35** — In the last measurement, the two notations are **character-for-character identical**; the only thing that changes is whether the inner source is a list or a generator expression. The outer loop runs three turns and the inner source has two items. #### Measurement ```python """Comprehension: three containers, same source, separate retention; nested comprehension's intermediate object.""" COUNTER = {"produced": 0} class Item: """An item that counts every production of itself.""" def __init__(self, value): COUNTER["produced"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): COUNTER["produced"] = 0 def produced(): return COUNTER["produced"] N = 1000 SOURCE = [Item(i) for i in range(N)] COMPREHENSIONS = ( ("list comprehension", lambda: [o for o in SOURCE]), ("set comprehension", lambda: {o.value % 100 for o in SOURCE}), ("dict comprehension", lambda: {o.value % 100: o for o in SOURCE})) print(f"{'comprehension':<20s} {'materialized':>12s} {'held in container':>18s}" f" {'shared Item':>12s}") for name, build in COMPREHENSIONS: reset() container = build() items = list(container.values()) if isinstance(container, dict) else list(container) shared = sum(1 for o in items if isinstance(o, Item)) print(f" {name:<18s} {produced():12d} {len(container):18d} {shared:12d}") def filter_before(n=10): reset() items = [Item(i) for i in range(n) if i % 2 == 0] return produced(), len(items) def filter_after(n=10): reset() items = [o for o in (Item(i) for i in range(n)) if o.value % 2 == 0] return produced(), len(items) def conditional_expression(n=10): reset() items = [Item(i) if i % 2 == 0 else Item(-i) for i in range(n)] return produced(), len(items) print() print(f"{'condition location':<36s} {'materialized':>12s} {'retained':>8s}") for name, f in (("filtering before production", filter_before), ("filtering after production", filter_after), ("conditional expression (no filter)", conditional_expression)): p, r = f() print(f" {name:<34s} {p:12d} {r:8d}") def nested(m=4, k=3): reset() table = [[Item(i * k + j) for j in range(k)] for i in range(m)] return produced(), 1 + len(table), sum(len(row) for row in table) def flat(m=4, k=3): reset() items = [Item(i * k + j) for i in range(m) for j in range(k)] return produced(), 1, len(items) def flatten(m=4, k=3): reset() table = [[Item(i * k + j) for j in range(k)] for i in range(m)] items = [o for row in table for o in row] return produced(), 2 + len(table), len(items) print() print(f"{'nested notation':<28s} {'materialized':>12s} {'containers built':>16s}" f" {'items':>5s}") for name, f in (("row-by-row table", nested), ("single-level comprehension", flat), ("flattening the table", flatten)): p, containers, items = f() print(f" {name:<26s} {p:12d} {containers:16d} {items:5d}") i = "outer value" squares = [i * i for i in range(4)] print() print(f"outer name after comprehension: {i!r}, result {squares}") reset() mapping = {o.value: o for o in (Item(i % 4) for i in range(12))} print(f"key collision: produced {produced()}, retained {len(mapping)}," f" last value won -> {mapping[0].value}") def inner_source_list(): reset() inner = [0, 1] items = [Item(i * 2 + j) for i in range(3) for j in inner] return produced(), len(items) def inner_source_stream(): reset() inner = (x for x in [0, 1]) items = [Item(i * 2 + j) for i in range(3) for j in inner] return produced(), len(items) print() print(f"{'inner source type':<36s} {'materialized':>12s} {'retained':>8s}") for name, f in (("list (re-walkable)", inner_source_list), ("generator expression (single-pass)", inner_source_stream)): p, r = f() print(f" {name:<34s} {p:12d} {r:8d}") ``` ``` comprehension materialized held in container shared Item list comprehension 0 1000 1000 set comprehension 0 100 0 dict comprehension 0 100 100 condition location materialized retained filtering before production 5 5 filtering after production 10 5 conditional expression (no filter) 10 10 nested notation materialized containers built items row-by-row table 12 5 12 single-level comprehension 12 1 12 flattening the table 12 6 12 outer name after comprehension: 'outer value', result [0, 1, 4, 9] key collision: produced 12, retained 4, last value won -> 0 inner source type materialized retained list (re-walkable) 6 6 generator expression (single-pass) 2 2 ``` #### What the Three Containers Retain In the top table, "materialized" is **0** in all three rows. This is not an oddity, it is the rig itself: the thousand items were set up before the measurement, and none of the three comprehensions produces a new `Item` — they only take what already exists. What is measured here is not production, it is **retention**. The list comprehension retains **1000** items, and **1000** of them are the source's own objects. A new container was built, a thousand references were written into it, and no item was duplicated — the very container-building operation the first lesson measured. The set comprehension retains **100** items and shared is **0**. The two numbers have to be read together: the item expression `o.value % 100` produces a number, not an `Item`; the container never takes the source's objects at all. A thousand turns yield only a hundred distinct values, because a set does not accept an equal one a second time. A thousand items were read, a hundred were retained — the gap between read and retained is **900**. The dict comprehension also retains **100**, but shared is **100**. The key is a derived number, the value is the source's own object. So the dict both filtered and shared: each of the hundred keys is bound to the last `Item` that fell to that key. The last line shows this consequence directly. Twelve items were produced, four retained, and on colliding keys **the last value won**. What filters in a dict comprehension is silent: dropped items get neither a warning nor an exception. A thousand-row source turning into a hundred-row dict leaves the notation unchanged; the loss's trace is only visible if it is counted. #### Wherever the Condition Is Written The middle table runs the same ten turns in all three rows, but production numbers split. **Filtering before production** — the condition at the notation's end, operating on the loop variable — materializes **5** objects. The five turns that fail the condition never reach the item expression at all; `Item` is never called. **Filtering after production** retains the same five items but materializes **10**. Here the condition looks at the item itself, so the item has to exist first. Five objects are born, get filtered, and become unreachable since they enter no container. The two rows retain the same number: **5**. The result is the same too. The only thing that differs is **which side** does the filtering. If the filter condition can be written in the source's own language, production is avoided; if only a produced object's property can be checked, it cannot. This is the previous lesson's early-exit measurement, restated inside a comprehension — laziness is again a possibility, tied to where the condition can be written. The **conditional expression** row shows the third behavior: **10** production, **10** retention. The `if` here is not a filter, it is a **selector**; it filters no turn out, it only picks which object gets produced. The two notations look alike and sit in different places: the selector inside the item expression, the filter at the notation's end. The number gives the distinction — a filter reduces what is retained, a selector does not. #### Nested Comprehension's Intermediate Containers The bottom table builds the same twelve items with three notations. "Materialized" is **12** in all three, and item count is **12** in all three; the column that splits is container count. **Row-by-row table** — one comprehension inside another — builds **5** containers: four row lists and the outer list carrying them. The inner comprehension reruns on every outer turn and produces a new list each time. These lists are not intermediate objects, they are the result itself; they are needed if a table structure is wanted. **Single-level comprehension** — two `for`s side by side, one item expression — builds the same twelve items with **1** container. Two loops run nested inside a single comprehension, and no intermediate list is ever born. The order is the same too: the leftmost `for` is the outer loop. **Flattening the table** shows the third route: build the table first, then flatten it. The result matches the second row, but container count is **6**. Five containers were built, one more added, and the four row lists built along the way serve no purpose after flattening — these are real **intermediate objects**. Where the same result can be built with one container, five are extra. The distinction settles here: nested comprehension builds a **structure**, side-by-side `for` builds a **walk**. If the result is going to be a flat sequence, building the structure and then tearing it down costs more than never building it. #### How Many Times the Inner Source Is Walked The last table measures the most overlooked side of side-by-side `for` notation: the two notations are identical, the results are **6** against **2**. The difference comes from the inner source's type. The right-hand `for` is **re-walked** on every outer turn; for three outer turns, the inner source has to be passed through from the start three times. If the inner source is a list, this is fine — a list gives a fresh iterator every time one is requested, and three turns of two items each give **6** items total. If the inner source is a generator expression, it does not work. The stream is consumed on the first outer turn; the second and third turns want to pass through the same stream again, and the stream comes back **empty**. The result is **2** items, and there is neither an exception nor a warning. The single-pass behavior measured in the first lesson produces a consequence here: because an exhausted stream cannot be told apart from an empty one, the comprehension silently builds an incomplete list. This is the practical counterpart of the distinction the three lessons have built up. If a stream is placed somewhere it will be re-walked — a nested loop's inner source, a variable read twice — it has to be collected into a list first. If not, the second pass produces not an error but a **silent shortfall**. #### A Comprehension's Own Scope The last two lines measure a detail specific to Python. A comprehension's loop variable does not **overwrite** the outer variable of the same name: after the comprehension, `i` still carries its own value, while the comprehension produces `[0, 1, 4, 9]` with its own `i`. The reason is that a comprehension has its own scope. The Python Fundamentals course's scope lesson built which level a name is searched at; what is added here is that a comprehension **opens one of these levels itself**. The loop name is born inside the comprehension and dies there. An ordinary `for` loop is not like this: there, the loop variable is written into the enclosing scope and lives on after the loop ends. Of two notations doing the same job, one leaves a name behind, the other does not. This shows a comprehension is not just a shorthand — it is a separate mechanism where name visibility is concerned. #### Summary - From the same thousand-item source, a list comprehension retains **1000**, a set and a dict comprehension **100**; shared `Item` count is **1000**, **0**, and **100** respectively. A container decides for itself how much it keeps, and filtering is silent. - If a filter condition can be written before production, materialized stays at **5**; if only a produced object can be checked, it becomes **10**. Retained is **5** in both notations. - A conditional expression inside the item expression is not a filter: it filters no turn out, it produces **10** and retains **10**. - A nested comprehension builds **5** containers for twelve items, two side-by-side `for`s give the same items with **1** container; building then flattening makes **6** containers, four of them intermediate objects. - A comprehension has its own scope: the loop name does not overwrite an outer variable of the same name and disappears once the comprehension ends; an ordinary `for` loop leaves the name behind. - In side-by-side `for` notation, the right-hand source is re-walked on every outer turn: a list gives **6** items, a generator expression in the same notation gives **2**. Because an exhausted stream behaves silently empty, the shortfall produces no exception. #### Next Step In this lesson, both the filter condition and the item expression were written **inside** the comprehension; both stayed embedded where they were written and could not be reused in another comprehension. Yet both express a rule — "let this through," "turn this into that" — and rules can be named. The next lesson treats a rule as an object: can a function be passed as an argument to another function, and if so, **how many times** is it called when passed? In sorting, is the key computed once per item, or freshly on every comparison? ### Lambda and Higher-Order Functions Source: https://academia.sh/en/courses/python-data-structures/lambda-and-higher-order-functions A function is an object and can be passed as an argument: on two hundred items, the key function for sorted, min, and max is called exactly once per item — a hand-written sort doing the same job calls it 39800 times. In the previous lesson, both the filter condition and the item expression stayed embedded inside the comprehension. Both stated a rule — "let this through," "turn this into that" — but the rule could not be used outside where it was written. Repeating the same filter in a second comprehension meant writing it again. Rules can be named. A function is exactly this: a named rule. This lesson's question is whether that function can be passed as an **argument**, and **how many times** it is called when it is. Is a sort's key computed once per item, or freshly on every comparison? The gap between the two will produce two numbers on two hundred items, and they will not be the same order of magnitude. #### A Function Is an Object In Python, `def` is not a declaration, it is a **statement**: when run, it produces a function object and binds it to a name. The binding is like any other — the object can go into a list, be a value in a dict, be passed as an argument to a function, be returned from a function. `lambda` produces the same kind of object without binding a name. It carries a single expression, `return` is not written, its result is the expression's value. The produced object is the **same type** as what `def` produces; the only place they differ is the name it carries. A function that takes a function as an argument or returns one is called a **higher-order function**. The Programming Fundamentals course built this concept at the entrance to functional programming; it is not repeated here. What is measured is **how many times** Python's built-in higher-order functions call the given function, and **how many objects** they materialize. #### The Key Function's Contract `sorted`, `min`, and `max` accept a `key` argument: a function giving the comparison value computed for each item. The contract's measurable side is this — how many times **per item** is this function called? Two answers come to mind. Sorting compares items with each other, and comparison count exceeds item count; if the key is computed on every comparison, call count would be the same. Or the key is computed once and stored, and comparisons run on the stored values. The second route lowers call count but raises **retention**: a key value has to stay alive for every item. The measurement says which one holds. The measurement's assumptions: - **IF36** — The shared reference's `Item` class is used as is, with its counting arrangement; `Item` only counts production, key calls are kept in a separate counter. - **IF37** — The key function counts every call to itself; the measure for "how many times was it called" is this counter, and it is the oracle itself. - **IF38** — The source has **200** items, and all four operations run on the same source. The counter is reset before every operation. - **IF39** — The key value is computed with `-o.value % 97`; the number is arbitrary and chosen only so sorting produces an order different from the source's. - **IF40** — The hand-written selection sort computes the key **twice** per comparison; this is the behavior of a notation that does not store the key, and is the measurement's opposite end. Sorting is used here not as an algorithm but as a **rig producing a call count**. - **IF41** — The distinction between `sorted` and `list.sort` is measured by identity; **identity is shown with `is`, no number is printed.** - **IF42** — In the map and filter measurement, the counter is read right after the setup line; the item-producing function deliberately produces new `Item`s, so laziness becomes visible through production. - **IF43** — That the three functions are separate objects is shown with pairwise `is` comparisons; no identity number is printed. - **IF44** — In the binding measurement, all three notations build the **same** three functions, and all are called with the same item; the only thing that changes is where the factor is written. #### Measurement ```python """Function is an object: how many times is the key function called, when does a stream materialize.""" import functools COUNTER = {"produced": 0, "key_calls": 0} class Item: """An item that counts every production of itself.""" def __init__(self, value): COUNTER["produced"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): COUNTER["produced"] = 0 COUNTER["key_calls"] = 0 def produced(): return COUNTER["produced"] def key_function(o): """The item's sort key; counts every call to itself.""" COUNTER["key_calls"] += 1 return -o.value % 97 N = 200 SOURCE = [Item(i) for i in range(N)] def manual_select(items, key): """Selection sort that recomputes the key on every comparison.""" remaining, ordered = list(items), [] while remaining: min_idx = 0 for i in range(1, len(remaining)): if key(remaining[i]) < key(remaining[min_idx]): min_idx = i ordered.append(remaining.pop(min_idx)) return ordered OPERATIONS = (("sorted(n, key=f)", lambda n: len(sorted(n, key=key_function))), ("min(n, key=f)", lambda n: min(n, key=key_function)), ("max(n, key=f)", lambda n: max(n, key=key_function)), ("manual selection sort", lambda n: len(manual_select(n, key_function)))) print(f"{'operation':<24s} {'key calls':>16s} {'per item':>11s}") for name, operation in OPERATIONS: reset() operation(SOURCE) print(f" {name:<22s} {COUNTER['key_calls']:16d} {COUNTER['key_calls'] / N:11.1f}") reset() ordered = sorted(SOURCE, key=key_function) print() print(f"sorted(n) is n -> {ordered is SOURCE}, materialized {produced()}," f" shared {sum(1 for o in ordered if any(o is k for k in SOURCE))}") copy = list(SOURCE) before = copy result = copy.sort(key=key_function) print(f"list.sort return value {result!r}, container stayed the same -> {before is copy}") def named(o): return o.value unnamed = lambda o: o.value print() print(f"{'function':<12s} {'callable':>13s} {'__name__':>12s} {'same type':>12s}") for name, f in (("via def", named), ("via lambda", unnamed)): print(f" {name:<10s} {str(callable(f)):>13s} {f.__name__:>12s}" f" {str(type(f) is type(named)):>12s}") REGISTRY = {"increment": lambda o: o.value + 1, "double": lambda o: o.value * 2} print(f"functions held in dict: {sorted(REGISTRY)}," f" REGISTRY['double'](Item(21)) -> {REGISTRY['double'](Item(21))}") reset() mapped = map(lambda o: Item(o.value * 2), SOURCE) filtered = filter(lambda o: o.value % 2 == 0, SOURCE) at_setup = produced() first = next(mapped) print() print(f"map and filter materialized {at_setup} objects at setup," f" once the first item is requested {produced()}") print(f"once fully walked: map {len(list(mapped)) + 1} items," f" filter {len(list(filtered))} items, materialized {produced()}") reset() total = functools.reduce(lambda a, o: a + o.value, SOURCE, 0) print(f"total via reduce {total}, materialized {produced()}") def factor_maker(k): def multiply(o): return o.value * k return multiply three_funcs = [factor_maker(k) for k in (1, 2, 3)] separate = all(a is not b for i, a in enumerate(three_funcs) for b in three_funcs[i + 1:]) print() print(f"are the three functions separate objects -> {separate}," f" results {[f(Item(10)) for f in three_funcs]}") print(f"factor_maker(2) is factor_maker(2) -> " f"{factor_maker(2) is factor_maker(2)}") late = [lambda o: o.value * k for k in (1, 2, 3)] early = [lambda o, k=k: o.value * k for k in (1, 2, 3)] partial = [functools.partial(lambda o, k: o.value * k, k=k) for k in (1, 2, 3)] print() print(f"{'binding form':<26s} {'objects':>7s} {'results':>16s}") for name, funcs in (("free name in body", late), ("default argument", early), ("via partial", partial)): print(f" {name:<24s} {len(funcs):7d} {str([f(Item(10)) for f in funcs]):>16s}") ``` ``` operation key calls per item sorted(n, key=f) 200 1.0 min(n, key=f) 200 1.0 max(n, key=f) 200 1.0 manual selection sort 39800 199.0 sorted(n) is n -> False, materialized 0, shared 200 list.sort return value None, container stayed the same -> True function callable __name__ same type via def True named True via lambda True True functions held in dict: ['double', 'increment'], REGISTRY['double'](Item(21)) -> 42 map and filter materialized 0 objects at setup, once the first item is requested 1 once fully walked: map 200 items, filter 100 items, materialized 200 total via reduce 19900, materialized 0 are the three functions separate objects -> True, results [10, 20, 30] factor_maker(2) is factor_maker(2) -> False binding form objects results free name in body 3 [30, 30, 30] default argument 3 [10, 20, 30] via partial 3 [10, 20, 30] ``` #### One Call Per Item The top table's first three rows give the same number: **200** calls, exactly **1.0** per item. Sorting, finding the minimum, finding the maximum — in all three, the key function is called once per item, no more. For `min` and `max` this is expected; looking at each item once is enough. For `sorted` it is not. Sorting has to compare items with each other, and comparison count exceeds item count. Yet the key call stays at **200**: keys must be computed once and **stored**, with all comparisons run on the stored values. The fourth row shows the opposite end of this decision. A sort doing the same job, never storing the key and recomputing it on every comparison, calls the key **39800** times on the same two hundred items — **199.0** per item. The ratio between the two numbers is two hundred, and it grows as item count grows. Read from the course's axis: built-in `sorted` makes a **trade**. Storing key values means holding as many references as there are items; in exchange, call count drops to item count. The notation avoiding retention — the fourth row — stores no intermediate value and pays with call count instead. This is the second lesson's result reversed: there, the non-retaining form won; here, the retaining form wins. **What is retained matters as much as what retaining removes.** This measurement is not a sorting-algorithm comparison; algorithms and complexity analysis are the Algorithms course's subject. The fourth row here was hand-built only to show how many calls a notation not storing the key produces. #### New Container or In Place The next two lines separate two notations of the same job. `sorted` produces a new list: `sorted(n) is n` is **false**, materialized `Item` is **0**, shared is **200**. Sorting duplicates no items, it only writes them into a new container in a different order — the same container-building measurement from the first lesson. `list.sort` builds no new container: the container stays the same and the return value is **`None`**. This is the shared signature of in-place methods in Python, and it has a consequence — the notation `n = n.sort()` replaces the list with `None`. The distinction shows in one line: want the result, use `sorted`; want to keep the container, use `sort`. #### Proof That a Function Is an Object The middle table compares two functions and gives the same answer on two of three columns. The objects defined with `def` and produced with `lambda` are both **callable**, both the **same type**. The only column they differ on is `__name__`: one carries its own name, the other ``. This single difference looks minor but is a preview of the next lesson's measurement. A function object carries its own name in an attribute, and that attribute is used in error traces, log records, and documentation generation. A nameless object cannot give this information. The next line shows the practical payoff of being an object: two functions sit as values in a dict and get called by key. The rule now lives in the same place as data — nameable, storable, passable. The filter that stayed embedded in the previous lesson's comprehension could have been a dict value here. #### Lazy Higher-Order Built-ins The last three lines measure the `map` and `filter` built-ins, and a familiar number comes out: **0** objects at setup. Both return a stream; the given function is never called at setup time. Once the first item is requested, produced becomes **1**; once fully walked, **200**. This is the third lesson's claim, restated on built-ins: `map` does not avoid production, it defers it. Requesting two hundred items births two hundred objects. Filtering follows the same pattern and lets **100** of two hundred items through; no new object is built for the ones that do not pass, so production stays at two hundred. The choice between `map` and a comprehension is therefore not a cost choice, it is a notation choice — one gives a stream, the other a container. Their numbers were measured in the previous two lessons and do not change here. The last line shows a third higher-order tool: the standard library's `reduce` function applies a two-argument function across a stream and collapses it into a single value. Total is **19900**, materialized **0** — no intermediate container is built, only the accumulating value is carried at every step. A comprehension produces a container, `map` a stream, `reduce` a **value**; all three take the same function as an argument. #### A Function That Returns a Function The last two blocks reverse the direction: a function is now not an argument but a **return value**. When `factor_maker` is called, the `def` inside its body runs and produces a new function object. Three calls give **three separate objects**, and three produce separate results — each carrying its own factor. Even two calls with the same argument give separate objects: `factor_maker(2) is factor_maker(2)` is **false**. Producing a function means materializing an object every time; ten separate factors mean ten separate function objects. The Programming Fundamentals course's closures — an inner function carrying an outer scope's name — was built as a concept; the only thing added here is measuring that carrying **by object count**, and that what is carried is not a **value** but a **name**. The last table gives the consequence of this distinction. All three notations produce three functions, and object count is **3** in all three. But the results are not the same. The **free name in body** form gives `[30, 30, 30]`: all three functions look at the same name `k`, and by the time they are called, that name's last value is **3**. The closure did not copy `k`'s value, **it bound to its name**. The **default argument** form gives `[10, 20, 30]`. The Programming Fundamentals course's function-definition lesson measured that a default value is evaluated **once, at definition time**; there it was a trap, here it is the fix. Since the value is computed at definition time, each function carries its own factor along. The standard library's `partial` tool gives the same result by binding the argument in advance. The three rows are three readings of the same notation, and the difference between them is the difference between a name and a value. In a comprehension, the loop name vanishes once the comprehension ends; the function bound to it does not vanish and sees the last value. **Binding to a name is not the same as taking a value.** #### Summary - `def` is a statement producing a function object; `lambda` gives the same kind of object without binding a name. Both are callable, both the same type, and the only place they differ is `__name__`. - A function object can be held as a value in a container and passed as an argument; a function taking or returning a function is higher-order. - On two hundred items, the key function for `sorted`, `min`, and `max` is called **200** times — exactly **once** per item. A hand-written sort not storing the key calls the same function **39800** times. - `sorted` builds a new container and shares **200** items, duplicating none; `list.sort` runs in place and returns **`None`**. - `map` and `filter` materialize **0** objects at setup, **200** once fully walked; filtering lets **100** of two hundred items through. `reduce` collapses to a single value without building any container. #### Next Step In this lesson functions always passed as arguments; none of them was changed. Yet if a function can be returned, it is also possible to take a function and return **another function in its place** — a wrapper that preserves the original behavior and adds something around it. The next lesson measures this pattern: how many objects does wrapping a function materialize, what happens to the original object, and what does the wrapped function's `__name__` attribute say? This lesson's one seemingly minor column will produce a result there. ### Decorators Source: https://academia.sh/en/courses/python-data-structures/decorators Wrapping does not delete the original function, it adds a layer on top: one decorator builds two layers, two decorators build three, and when metadata is not preserved, the function's name, doc, and signature change to the wrapper's. In the previous lesson functions always passed as arguments, and none of them was changed. But the same lesson also measured that a function can be **returned**: `factor_maker` produced a new function object on every call. The two directions can be combined — a function that **takes** a function and **returns** another function **in its place**. Such a function is called a **decorator**, and the object it returns is called a **wrapper**. This lesson's questions are: how many objects does wrapping bring into existence, what happens to the original function, and what does the wrapped function's `__name__` attribute say? The previous lesson's seemingly minor column — the name gap between `def` and `lambda` — will produce a result here. #### The Wrapper Pattern The pattern has three steps. A decorator takes a function; defines a new function in its body; returns that new function. When the inner function is called, it does its own work and **also calls the function it received** — this is how the original behavior is preserved while something is added around it. The form written with `@` before a name is a shorthand. When a `@decorator` line sits above a function definition, once the definition finishes, `compute = decorator(compute)` runs. So nothing new is set up underneath it — the previous lesson's higher-order function has its result bound back to the same name. An important consequence follows: **the original function is not destroyed.** The name is now bound to the wrapper, but the wrapper's body refers to the original object and keeps it alive. Wrapping is not a deletion, it is **adding a layer** — and layers can be counted. #### Two Separate Moments Wrapping does work at two separate moments, and the two are often confused. **Definition time:** the decorator's body runs and produces the wrapper. This happens once — where the function is defined, even if it is never called. **Call time:** the wrapper's body runs. This happens on every call. The measurable consequence of this split is this: the work inside the decorator body runs as many times as functions are wrapped; the work inside the wrapper body runs as many times as calls are made. The measurement's assumptions: - **IF45** — The shared reference's `Item` class is used exactly as is; the decorator body, the wrapper, and the original body are kept in separate counters. The oracle is the rig itself. - **IF46** — Layer count is found by following the `__wrapped__` chain; this chain is only built when metadata preservation is used. - **IF47** — All four forms wrap the **same** original function, and all four are called once. Counters are reset before the measurement. - **IF48** — The parameterized decorator deliberately calls the original body **three** times; the number is arbitrary and chosen only to make the wrapper's added behavior visible. - **IF49** — The metadata measurement compares three forms: unwrapped, one that does not use preservation, and one that does. **Identity is shown with `is`, no number is printed.** - **IF50** — The doc column asks whether the doc exists, not what it contains; the signature column is taken from the standard library's introspection tool. - **IF51** — In the memoization measurement, twenty requests collapse into five distinct values; the request sequence is fixed, and the ratio of repeated requests is the measurement itself. - **IF52** — In the order measurement, the two decorators are the **same** decorator and differ only by their labels; the trace records entry and exit points separately so order can be read. - **IF53** — The narrow-signature wrapper deliberately accepts only a single positional argument; what is measured is that the call fails, and which exception class is raised. #### Measurement ```python """Decorator: how many layers does wrapping build, and what is lost when metadata is not preserved.""" import functools import inspect COUNTER = {"produced": 0, "decorator": 0, "wrapper": 0, "body": 0} class Item: """An item that counts every production of itself.""" def __init__(self, value): COUNTER["produced"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): for k in COUNTER: COUNTER[k] = 0 def bare(function): """Wrapper that does not preserve metadata.""" COUNTER["decorator"] += 1 def wrapper(*a, **k): COUNTER["wrapper"] += 1 return function(*a, **k) return wrapper def guarded(function): """Wrapper carrying metadata via functools.wraps.""" COUNTER["decorator"] += 1 @functools.wraps(function) def wrapper(*a, **k): COUNTER["wrapper"] += 1 return function(*a, **k) return wrapper def repeating(times): """Parameterized decorator: the factory is called first, then the decorator.""" def decorator(function): COUNTER["decorator"] += 1 @functools.wraps(function) def wrapper(*a, **k): COUNTER["wrapper"] += 1 for _ in range(times): result = function(*a, **k) return result return wrapper return decorator def compute(n: int): """Produces an item from the given number.""" COUNTER["body"] += 1 return Item(n) def layer_count(function): count = 1 while hasattr(function, "__wrapped__"): function, count = function.__wrapped__, count + 1 return count def core(function): while hasattr(function, "__wrapped__"): function = function.__wrapped__ return function reset() unwrapped = compute single = guarded(compute) double = guarded(guarded(compute)) parameterized = repeating(3)(compute) at_definition = COUNTER["decorator"] print(f"{'form':<26s} {'layers':>7s} {'core is original':>18s}" f" {'body calls':>12s}") for name, f in (("unwrapped", unwrapped), ("single decorator", single), ("two decorators", double), ("parameterized decorator", parameterized)): COUNTER["body"] = 0 f(7) print(f" {name:<24s} {layer_count(f):7d}" f" {str(core(f) is compute):>18s} {COUNTER['body']:12d}") print() print(f"decorator body run while building the four forms: {at_definition};" f" wrapper run once each is called:" f" {COUNTER['wrapper']}") print(f"single is compute -> {single is compute}," f" single.__wrapped__ is compute -> {single.__wrapped__ is compute}") print() print(f"{'form':<16s} {'__name__':>12s} {'has doc':>9s} {'signature':>18s}") for name, f in (("unwrapped", compute), ("no wraps", bare(compute)), ("with wraps", guarded(compute))): print(f" {name:<14s} {f.__name__:>12s} {str(bool(f.__doc__)):>9s}" f" {str(inspect.signature(f)):>18s}") @functools.cache def expensive(n): COUNTER["body"] += 1 return Item(n % 5) reset() requests = [i % 5 for i in range(20)] for i in requests: expensive(i) print() print(f"memoization: {len(requests)} requests, body calls {COUNTER['body']}," f" produced {COUNTER['produced']}, held in cache" f" {expensive.cache_info().currsize}") TRACE = [] def tracing(label): def decorator(function): @functools.wraps(function) def wrapper(*a, **k): TRACE.append(f"{label} enter") result = function(*a, **k) TRACE.append(f"{label} exit") return result return wrapper return decorator @tracing("outer") @tracing("inner") def top_down(n): TRACE.append("body") return Item(n) @tracing("inner") @tracing("outer") def bottom_up(n): TRACE.append("body") return Item(n) print() for name, f in (("@outer @inner", top_down), ("@inner @outer", bottom_up)): TRACE.clear() f(1) print(f" {name:<14s} {' -> '.join(TRACE)}") def narrow(function): @functools.wraps(function) def wrapper(n): return function(n) return wrapper @narrow def two_args(n, k=2): return n * k try: two_args(3, k=5) except TypeError as e: print(f"narrow-signature wrapper with a keyword argument: {type(e).__name__}") print(f"wide-signature wrapper on the same call:" f" {tracing('x')(lambda n, k=2: n * k)(3, k=5)}") ``` ``` form layers core is original body calls unwrapped 1 True 1 single decorator 2 True 1 two decorators 3 True 1 parameterized decorator 2 True 3 decorator body run while building the four forms: 4; wrapper run once each is called: 4 single is compute -> False, single.__wrapped__ is compute -> True form __name__ has doc signature unwrapped compute True (n: int) no wraps wrapper False (*a, **k) with wraps compute True (n: int) memoization: 20 requests, body calls 5, produced 5, held in cache 5 @outer @inner outer enter -> inner enter -> body -> inner exit -> outer exit @inner @outer inner enter -> outer enter -> body -> outer exit -> inner exit narrow-signature wrapper with a keyword argument: TypeError wide-signature wrapper on the same call: 15 ``` #### The Number of Layers In the top table, the layers column counts directly: the unwrapped function is **1**, a single decorator is **2**, two decorators are **3**. Every wrapping adds one link to the chain, and link count is one more than decorator count. The second column says the more important thing: on every row, the object sitting at the bottom of the chain is **the original function itself**. Wrapping neither changes nor destroys the original object; it keeps it alive at the end of a reference. The bottom two lines show this directly: `single is compute` is **false** — the name is now bound to a different object — but `single.__wrapped__ is compute` is **true**. A new object was materialized, the old object was **shared**. Read from the course's axis, wrapping is not a copy, it is **building a container**: the outer object is new, the one inside it is old. The same pattern as the first topic's slicing measurement, this time on functions. The fourth row shows that a layer adds **behavior**: when the function wrapped by the parameterized decorator is called once, the original body runs **3** times. Layer count is still **2** — the parameter does not add a layer, it only decides the layer's behavior. The parameterized decorator has three stages: first the factory is called and produces the decorator, then the decorator is called and produces the wrapper, then the wrapper is called. The number's cost side reads just as directly. Every wrapping materializes a function object and keeps the original object alive; a function wrapped by two decorators leaves **3** function objects standing in memory, and every call opens three frames. Wrapping a function is cheap, but not free, and the cost is paid **per layer**. The next line separates the two moments. While the four forms were being built, the decorator body ran **4** times — once for every wrapped function, before any of them was called. The wrappers, in turn, ran only once calls were made. The work at definition time is paid once; the work at call time is paid on every call. #### Lost Metadata The middle table answers the lesson's second question, and the middle row shows the loss. When metadata preservation is not used, the wrapped function's `__name__` attribute becomes **wrapper**, its doc **disappears**, and its signature shows as `(*a, **k)`. All three pieces of information still sit on the original object, but nobody looks at it anymore: the object bound to the name is the wrapper, and these three attributes are its own. Where the loss is paid matters. The name appears in error traces and log records; if ten separate functions are wrapped by the same decorator, all ten carry the same name, and a trace cannot say which function ran. The doc is read in online help and in doc generation. The signature is the most deceptive of the three: `(*a, **k)` is not a signature, it is the absence of one — no tool inspecting which arguments are expected gets a correct answer. The bottom row shows the fix. The standard library's `wraps` tool is a decorator, and when applied to a wrapper, it copies the original object's name, doc, and signature information onto it, and also sets up the `__wrapped__` link. The layer count in the top table was possible exactly because of this link — without preservation the chain cannot be followed, and what lies beneath a wrapped function cannot be seen from outside. The distinction in one sentence: the wrapper preserves the original **behavior** on its own, because it calls it; it does not preserve the original **identity**, because that has to be carried separately. #### What Retention Buys The last line measures one of the decorator's most common uses, and it reverses the course's axis. Twenty requests are made, and they collapse into five distinct values; the original body runs only **5** times, produced is **5**, and held in cache is **5**. Unwrapped, twenty requests would have meant twenty body calls and twenty objects. The wrapper cuts production to a quarter by **storing** the result for the arguments it has seen. The Programming Fundamentals course established memoization as a technique; the contribution here is giving it a number — and the number has to be read across two columns at once. Production dropped from **20** to **5**, but retention rose from **0** to **5**. The third lesson measured that laziness lowers retention; this line does the opposite: it raises retention to lower production. The two measurements together give the course's axis its final form — **there is a trade-off between materializing and retaining, and which side to land on depends on the job itself.** For a thousand items used once and discarded, not retaining is correct; for five values that will be asked for twenty times, retaining is correct. The cache's unbounded growth is this trade-off's open end: retained count grows with the number of distinct arguments, and nothing shrinks it. The standard library therefore also offers a bounded form; once a bound is set, retention is capped and body calls rise again. #### Order and Signature The last four lines measure two practical details of wrapping. When two decorators are stacked, **order changes the result.** With `@outer` on top, the trace runs: outer enter, inner enter, body, inner exit, outer exit. When the order is reversed, the trace reverses too. The rule is: **the bottommost decorator applies first** and lands deepest in the chain; the topmost applies last and sits outermost. Call order is the reverse of this — the outermost layer runs first, the body is reached last, and on the way back the layers close in reverse order. The distinction is not minor. If one layer does access control and another does logging, which one is outermost decides whether a rejected call gets logged at all. The two forms look the same; the trace differs. The bottom two lines show why a wrapper's signature is written wide. A wrapper accepting only a single positional argument cannot pass a call through even if the original function accepts a keyword argument, and a `TypeError` is raised. The same call works on a wide-signature wrapper that passes arguments through as given, and gives **15**. The reason is that the wrapper is now the **call surface**: every argument form coming from outside passes through it first. If it does not accept every form the original function accepts, it cannot pass through the ones it does not accept. The variable-argument collecting form is therefore not a style preference but a requirement of wrapping — and the `(*a, **k)` signature in the earlier table is exactly the trace of this. When preservation is not used, the signature visible from outside is this wide form; when it is used, the visible signature is the original function's, but what actually satisfies the call is still the wide form. #### Summary - A decorator takes a function and returns another function in its place; the `@` form is shorthand for the binding `compute = decorator(compute)`. - Wrapping does not destroy the original object, it adds a layer: unwrapped **1**, single decorator **2**, two decorators **3** layers. The object bound to the name changes (`single is compute` is false) but the original object is shared (`single.__wrapped__ is compute` is true). - The decorator body runs **at definition time**, once per wrapped function; the wrapper runs **at call time**, on every call. The parameterized decorator has three stages and does not increase layer count. - When metadata is not preserved, the name becomes `wrapper`, the doc is empty, and the signature is `(*a, **k)`; when preservation is used, all three take on the original value and the `__wrapped__` link is set up. The wrapper preserves behavior on its own; identity has to be carried separately. - A memoizing wrapper cuts twenty requests down to **5** body calls and retains **5** items in exchange: production drops, retention rises. The direction of the trade-off depends on the job itself. - The bottommost decorator applies first and sits innermost; call order is the reverse. Because the wrapper is a call surface, it has to pass arguments through as given — a narrow-signature wrapper raises a `TypeError` on a call the original function accepts. #### Next Step Up to this point, everything sat inside **a single file**. Every measured class, every generator, every decorator was defined in the same body and used in the same body; the question of where a name is written never came up, because there was only one place to write it. Yet this lesson's wrapper could just as well have wrapped a function defined in another file. When code is spread across multiple files, where are names written, how does one file see another's names, and if the same file is requested twice, is it read twice? The next topic sets up this machinery. ## Modules and Packages Import mechanics and the search path, subpackages and relative imports, the standard library's scope, and when the script/module duality runs the body. ### The Module System Source: https://academia.sh/en/courses/python-data-structures/module-system Import is an act of creation: when the same module is requested three times, two objects get created, and the body runs once while the cache is full; search path order only decides while the cache is empty. Everything up to this point sat inside **a single file**. Closures, generators, wrappers, and decorators all stood in the same namespace; a name was visible from where it was defined, and where it was not, scope was the reason. When code spreads across more than one file, the shape of this problem changes: where do names get written now, and by what operation does one file get another's name? The answer comes from this course's measure. Import is not a name-copying operation, it is an act of **creation**: the first time a file is requested, a **module** object is created from it, its body runs once, and every module-level name is written into that object's dictionary. A second request does not create a new object. This lesson's question is: when the same module is requested more than once, **how many objects get created**, **how many times does the body run**, and **which record** blocks the second run? #### What Import Creates An import request does three things. First, it checks whether the name is registered in the **module cache**; if it is, the object there is handed back and the job is done. If not, the source is searched for on the **search path**, a module object is created from the source found, that object is **written to the cache first**, and then its body is run. In the last step, the name in the request is bound to the module object on the requesting side. The order detail matters: the object is written to the cache **before the body runs**. This is why, even if a module's body indirectly imports another module that requests it back, no infinite loop is born — the second request finds, in the cache, a module whose body has not finished but whose object already exists. A direct consequence follows: import is **not cheap, it is expensive once**. Whatever is in the body — class definitions, module-level computations, tables — all of it runs once on the first request, and the results are held in the module object. Subsequent requests do no more work than a dictionary lookup. #### Two Notations, the Same Object Import has two notations, and both create **the same module object**; where they differ is **which name gets bound to what** on the requesting side. The first notation binds the module object itself to a name; the second reads **a single value** from the module's dictionary and binds that value to a local name. The second does not create a new object — it gives a second name to an object already created. The observable consequence of the distinction is this: the two names share **the object**, they do not share **the binding**. If the name in the module's dictionary is later bound to a different object, the name taken outside stays on the old object — because that name was written not into the module's dictionary but into its own. By contrast, if the shared object is mutated in place, both sides see the same change. The measurement's last section tests these two cases separately. #### The Search Path Is a List For a name not found in the cache, next comes the search path. The search path is a list of directory names, and it is **ordered**: the first matching source wins, the rest are not looked at. If two sources in two different directories carry the same name, which one gets imported is decided not by the files' content but by their **order** in the list. The practical consequence of the order shows up when a file carrying the same name as a standard-library module sits in a directory near the **front** of the search path: the request finds that file, and the standard library's module is never searched for. There is no error message, because the rule worked correctly — the first match won. The sign of a name clash is that the expected name cannot be found in the module; the reason is that the name came from **a different source**. These two mechanisms — cache and search path — work together, and which one has the final say first is a measurable question. If we change the search path's order after a module has been imported, does the next request follow the new order, or does it get the old object from the cache? The measurement answers this. #### Where a Module-Level Name Is Written Scope rules are not this course's subject; the four levels — local, enclosing, global, built-in — were built in the Python Fundamentals course's scope lesson and are not repeated here. What is added here is this: of those four levels, the **global** one is not an abstract space, it is the dictionary of a concrete object. Every name bound at module level is written into that module object's `__dict__` dictionary; the `vars` built-in gives that same dictionary. Assigning an attribute to a module from outside is also writing into that same dictionary. This explains why the phrase "global variable" is misleading. Nothing is global; what exists **belongs to a module**. Two modules' variables carrying the same name are independent of each other, because they sit in two separate dictionaries. The measurement's assumptions: - **MP1** — The measurement leaves no file in the repository. Module sources are produced in a temporary directory, and the directory is deleted when the job ends; **the directory's path is not printed.** - **MP2** — An import from the standard library is a real import; the oracle is an `is` comparison and **no identity number is printed.** - **MP3** — How many times the body ran is counted by a record the body itself appends to a shared list. The counting side is the measured module itself. - **MP4** — The number of module objects created is found by collecting the objects seen into a list and telling them apart from each other with `is`. - **MP5** — In the search-path measurement, two separate directories carry two sources with **the same name**; the two differ only in the value of a module-level name. - **MP6** — After the order is changed, the cache is checked twice: once full, once cleared. - **MP7** — When the measurement ends, the added path entries and cache records are rolled back; the interpreter's starting state does not carry over into the measurement. - **MP8** — Where a name is written is read with `vars`; that the result of `vars` and `__dict__` is the same object is also tested with `is`. - **MP9** — In comparing the two notations, the second notation is run in a separate namespace dictionary; the measurement does not touch the main run's own names. - **MP10** — Testing the sharing takes two steps: first the object is mutated in place, then the name in the module is bound to a different object. The two steps are read separately. #### Measurement ```python """Module system: how many objects does import create, how many times does the body run.""" import importlib import sys import tempfile from pathlib import Path LOG_SOURCE = "RUNS = []\n" MEASUREMENT_SOURCE = ("import log\n" "log.RUNS.append('run')\n" "LABEL = 'measurement'\n") CHOICE_SOURCE = "SOURCE = '{name}'\n" NAMES = ("log", "measurement", "choice") def distinct_objects(objects): """Counts how many separate objects were seen, without printing identity.""" distinct = [] for n in objects: if not any(n is f for f in distinct): distinct.append(n) return len(distinct) def clear_cache(): for name in NAMES: sys.modules.pop(name, None) def import_twice(): import json as first import json as second return first is second, "json" in sys.modules def how_many_body_runs(root): (root / "log.py").write_text(LOG_SOURCE, encoding="utf-8") (root / "measurement.py").write_text(MEASUREMENT_SOURCE, encoding="utf-8") sys.path.insert(0, str(root)) importlib.invalidate_caches() seen = [importlib.import_module("measurement")] seen.append(importlib.import_module("measurement")) log = sys.modules["log"] cached_count = len(log.RUNS) sys.modules.pop("measurement") seen.append(importlib.import_module("measurement")) result = (len(seen), distinct_objects(seen), cached_count, len(log.RUNS), seen[-1].log is log) sys.path.remove(str(root)) clear_cache() return result def search_path(root): for name in ("one", "two"): (root / name).mkdir() (root / name / "choice.py").write_text(CHOICE_SOURCE.format(name=name), encoding="utf-8") one, two = str(root / "one"), str(root / "two") sys.path[:0] = [one, two] importlib.invalidate_caches() before = importlib.import_module("choice").SOURCE sys.path.remove(one) sys.path.insert(1, one) cached = importlib.import_module("choice").SOURCE sys.modules.pop("choice") uncached = importlib.import_module("choice").SOURCE sys.path.remove(one) sys.path.remove(two) clear_cache() return before, cached, uncached def module_level_name(root): (root / "choice.py").write_text(CHOICE_SOURCE.format(name="one"), encoding="utf-8") sys.path.insert(0, str(root)) importlib.invalidate_caches() m = importlib.import_module("choice") same_dict = vars(m) is m.__dict__ present = "SOURCE" in vars(m) m.ADDED = "added" from_outside = vars(m)["ADDED"] == "added" sys.path.remove(str(root)) clear_cache() return same_dict, present, from_outside def two_notations(root): (root / "choice.py").write_text("SOURCE = ['one']\n", encoding="utf-8") sys.path.insert(0, str(root)) importlib.invalidate_caches() m = importlib.import_module("choice") namespace = {} exec("from choice import SOURCE", namespace) shares = namespace["SOURCE"] is m.SOURCE m.SOURCE.append("changed") saw_mutation = "changed" in namespace["SOURCE"] m.SOURCE = ["new"] saw_rebinding = namespace["SOURCE"] is m.SOURCE sys.path.remove(str(root)) clear_cache() return shares, saw_mutation, saw_rebinding same, registered = import_twice() print(f"module imported twice is the same object -> {same}, " f"registered in the cache -> {registered}") with tempfile.TemporaryDirectory() as d: requests, objects, cached, after_clear, shared = how_many_body_runs(Path(d)) print() print(f"import requests {requests} | module objects created {objects} | " f"body runs while cached {cached}, after cache cleared {after_clear}") print(f"log module the two modules see is the same object -> {shared}") with tempfile.TemporaryDirectory() as d: before, cached, uncached = search_path(Path(d)) print() print(f"search path order one-two -> {before}") print(f"order two-one, cache full -> {cached}") print(f"order two-one, cache cleared -> {uncached}") with tempfile.TemporaryDirectory() as d: same_dict, present, from_outside = module_level_name(Path(d)) print() print(f"vars(m) is m.__dict__ -> {same_dict} | module-level name in the dict " f"-> {present} | name written from outside in the same dict -> {from_outside}") with tempfile.TemporaryDirectory() as d: shares, mutation, rebinding = two_notations(Path(d)) print() print(f"imported name is the same object as the module's -> {shares} | " f"saw the object's mutation -> {mutation} | " f"saw the rebinding -> {rebinding}") ``` ``` module imported twice is the same object -> True, registered in the cache -> True import requests 3 | module objects created 2 | body runs while cached 1, after cache cleared 2 log module the two modules see is the same object -> True search path order one-two -> one order two-one, cache full -> one order two-one, cache cleared -> two vars(m) is m.__dict__ -> True | module-level name in the dict -> True | name written from outside in the same dict -> True imported name is the same object as the module's -> True | saw the object's mutation -> True | saw the rebinding -> False ``` #### Three Requests, Two Objects, Two Runs The first line is the shared measurement's fifth reading: when the same module is requested twice, two names bind to **the same object**, and that object is registered in the cache. Module objects created: **1**, kept: **1**, shared by the two names: **1**. The second section shows this bond's cost. Three import requests were made; module objects created came to **2**. Between the first two requests, because the cache was full, the body run count stayed at **1** — the second request did not create a new object, did not rerun the body, only handed back the cached object. Before the third request, the record was removed from the cache; that request found the source again, **created a new module object**, and ran the body a second time. Body run count went up to **2**. Three separate things are counted here. Module objects **created**: 2. **Kept** — that is, registered in the cache at the measurement's end: 1. And the **shared** one: the `log` module. The last line states this: the `log` imported inside the measurement module's body and the `log` the main run gets from the cache **are the same object**. The measurement module was created twice, but the `log` both see is singular, because its record was never removed. The rule that follows is: **the count of module objects depends not on the number of files but on how many times the cache record dropped.** Two module objects can be created from the same file, and the two objects' dictionaries are independent of each other — a class defined in one is a separate object from the class defined in the other. Because the two objects were produced from the same source, they carry the same names; the objects those names are bound to, though, are not shared. An identity test gives an unexpected result in this case: two classes coming from the same file, despite having the same name, do not stand in for each other. #### Order or Cache The third section puts the two mechanisms face to face. While directory `one` sits at the front of the search path, import gives **one**, as expected. Then the order was changed: `two` was moved to the front. Because the cache was full, the result did not change — it was still **one**. Once the cache record was removed, the same request gave **two**. This is direct proof that the cache comes **before** the search path. The search path only decides while the cache has no record; if there is a record, the path is never even read. Changing the path while the program runs has no effect on any module already imported up to that point. The fourth section settles where the name is written. `vars` and `__dict__` give **the same dictionary**, the module-level bound name sits there, and an attribute assigned to the module from outside is also written to **the same dictionary**. This shows that a module's namespace and a module's attributes are not two separate things: writing `SOURCE = "one"` inside the file and writing `m.SOURCE = "one"` from outside bind the same key in the same dictionary. #### The Object Is Shared, the Binding Is Not The last section gives the two notations' difference in three values. The imported name and the module's name are bound to **the same object**: objects shared: **1**, new objects created: **0**. The second notation created nothing; it gave a second name to an object already created. The second value shows the sharing is live. When the module's object was mutated **in place**, the imported name **saw** the change — since they look at the same object, it could not have been otherwise. The third value draws the boundary: when the module's name was **rebound** to a different object, the imported name did **not see it**. That name now sits on the old object and has no link to the module's dictionary. Reduced to a single sentence: **import shares the object, it copies the name.** If a module's name that will change later needs to be tracked, the module itself is imported and access is made through the module every time; for an object that will not change, the second notation earns a saved lookup each time. The difference between the two is not a matter of style, it is a measured behavioral difference. #### Summary - Import is not a name-copying operation, it is an act of **creation**: the source is read once, a module object is created from it, and the body runs once. - The order is cache, search path, body; the object is written to the cache **before the body runs**, and a module imported twice **is the same object**. - Three requests, with the cache cleared once, create **2** module objects and run the body **2** times; without the disruption, both would have stayed at **1**. - The search path's order only decides while there is no record in the cache: change the order and leave the cache full, the result does not change; clear the record, it does. - Every module-level name is written into the module object's `__dict__`; `vars` gives the same dictionary, and an attribute assigned from outside goes there too. - Taking a single name from a module creates **0** new objects and shares the object: the object's in-place mutation is visible, the module's name being rebound is not. #### Next Step In the measurement, modules stood flat: all of them sat directly inside one directory on the search path, and their names were single pieces. When code grows, names get split by dots and directories get nested. At that point, the same short name can be found in more than one place — one in a parent directory, another in a subdirectory. The next lesson measures this: when the same short name is called with two requests, one from a neighboring location and one from the root, **which object** does it resolve to, and how many bodies of the nested directories run? ### Package Structure Source: https://academia.sh/en/courses/python-data-structures/package-structure The same short name resolves to the neighbor in relative notation and to the root in absolute notation, giving two separate objects; a single submodule request runs five bodies and writes five module objects to the cache. The previous lesson searched for modules in a flat list: every source sat directly inside a directory on the search path, and its name was a single piece. In that layout, two files carrying the same name were a clash, and order alone decided the winner. When code grows, this layout is not enough; files doing related work want to sit close to each other, carrying the same short name in **different contexts**. A **package** is the layout where directories join the namespace: a directory and the `__init__.py` file inside it together give a module object, and what is inside that directory is attached to it with a dot. This makes a name two-part — it gets a path and a short name. The lesson's question is: while the same short name exists at two separate levels, which object does **relative** and **absolute** notation resolve to, and how many bodies does a single request run? #### How a Directory Becomes a Module A package is a directory with `__init__.py` inside it. That file is the package's **body**, and it runs once when the package is first requested; being empty is also an option, in which case the body binds no name, but the module object still gets created. The files and subdirectories inside a package are its **submodules** and **subpackages**. A dotted name is resolved left to right, and every level is a separate module object. A request for `pkg.sub.tool` needs not one object but three: `pkg`, `pkg.sub`, and `pkg.sub.tool`. All three are written to the cache separately, and all three bodies run in order. This is a direct consequence of the previous lesson's rule — every name gets its own record. Every resolved level is also **bound as an attribute** one level up. Once `pkg.sub` has been imported, the name `sub` exists in the `pkg` module object's dictionary, and that name is bound to **the very same** `pkg.sub` object in the cache. This is how dotted access works: the dot is not a search-path lookup, it is an attribute read. #### Two Notations, Two Starting Points The same submodule can be reached by two routes. **Absolute** notation starts the name from **the root**: the name's first piece is searched for on the search path, and the chain is resolved from there. **Relative import**, by contrast, starts the name from **the requesting module's package**; a leading dot means "the package I am in," two dots mean "the package one level up." The two produce two separate addresses carrying the same letters. If a package's root has a module named `tool`, and its subpackage also has another module named `tool`, a relative request written from inside the subpackage gives **the neighboring** one, an absolute request gives **the one at the root**. The names are the same; the objects they resolve to are not. Relative import has one condition: the requesting module has to **belong** to a package. For a module that is not inside a package, there is no such thing as "the package I am in," and the request cannot be resolved. The measurement tests this case too. #### Whose Bill Is the Package's Body `__init__.py` is a package's door, and it runs whenever **any** module belonging to the package is requested. This means whatever is written there gets billed to every user of the package. There are two common notations, and the difference between them is measurable. In the **plain** notation, `__init__.py` only binds the package's own names, it does not import the submodules; whichever submodule the user wants, they write it separately. In the **eager** notation, `__init__.py` imports the submodules itself and carries their names up to package level; the user reaches all of them from a single name. The second earns shorter notation, but it makes a user requesting a single leaf run **all** the siblings' bodies. The measurement's last section compares the same single-leaf request across the two notations. #### How Many Bodies a Request Runs The previous lesson measured that import is an act of creation. In packages, this count grows with **the chain's length**, and one side of the chain also comes from the imported module's own requests. If a submodule imports other modules inside its body, those run within the same request too. The measurement writes down the bodies a single request runs, **in run order**. The measurement's assumptions: - **MP11** — The measurement leaves no file in the repository; the package tree is produced in a temporary directory, deleted when the job ends, and **the directory's path is not printed.** - **MP12** — The bodies that ran are counted by every body appending its own name to a shared list; the counting side is the running module itself, and the list preserves **run order**. - **MP13** — The root and the subpackage carry two modules with **the same short name**; the two differ only in the value of a module-level name. - **MP14** — The relative and absolute requests are made from the body of a third, measured module; the two results are read from that module's dictionary. - **MP15** — Which name gets bound is measured in a separate namespace dictionary; names other than the two defined ones are filtered out. - **MP16** — A relative request is tried in a module that does not belong to a package; the oracle is the exception's **class name**, not its message text. - **MP17** — When the measurement ends, the added path entry and all cache records are rolled back. - **MP18** — Plain and eager notation carry **the same tree shape**: one package and three leaves. The only difference is a single line in the eager notation's `__init__.py` file. - **MP19** — In comparing the two notations, **a single leaf** is requested, and the count is reset before each measurement; the two measurements do not carry each other's count. #### Measurement ```python """Package structure: which object does the same short name resolve to in two notations.""" import importlib import sys import tempfile from pathlib import Path def body_marker(name, extra=""): return f"import log\nlog.RUNS.append('{name}')\n{extra}" SOURCES = { "log.py": "RUNS = []\n", "pkg/__init__.py": body_marker("pkg"), "pkg/tool.py": body_marker("pkg.tool", "NAME = 'pkg.tool'\n"), "pkg/sub/__init__.py": body_marker("pkg.sub"), "pkg/sub/tool.py": body_marker("pkg.sub.tool", "NAME = 'pkg.sub.tool'\n"), "pkg/sub/user.py": body_marker("pkg.sub.user", "from . import tool as relative\n" "from pkg import tool as absolute\n"), "alone.py": "from . import tool\n", "plain/__init__.py": body_marker("plain"), "eager/__init__.py": body_marker("eager", "from . import x, y, z\n"), } for root_name in ("plain", "eager"): for leaf in ("x", "y", "z"): SOURCES[f"{root_name}/{leaf}.py"] = body_marker(f"{root_name}.{leaf}") TOPS = ("log", "alone", "pkg", "plain", "eager") def setup(root): for name, text in SOURCES.items(): path = root / name path.parent.mkdir(parents=True, exist_ok=True) path.write_text(text, encoding="utf-8") sys.path.insert(0, str(root)) importlib.invalidate_caches() def teardown(root): sys.path.remove(str(root)) for name in list(sys.modules): if name.split(".")[0] in TOPS: sys.modules.pop(name) def measure(root): setup(root) user = importlib.import_module("pkg.sub.user") log = sys.modules["log"] ran = list(log.RUNS) registered = sorted(a for a in sys.modules if a.split(".")[0] == "pkg") relative, absolute = user.relative, user.absolute attribute_bound = (sys.modules["pkg"].sub is sys.modules["pkg.sub"] and sys.modules["pkg.sub"].tool is sys.modules["pkg.sub.tool"]) importlib.import_module("pkg.sub.tool") second_request = len(log.RUNS) - len(ran) ns_dotted, ns_from = {}, {} exec("import pkg.tool", ns_dotted) exec("from pkg import tool", ns_from) bound_dotted = sorted(a for a in ns_dotted if not a.startswith("__")) bound_from = sorted(a for a in ns_from if not a.startswith("__")) same_object = ns_dotted["pkg"].tool is ns_from["tool"] try: importlib.import_module("alone") error = "none" except Exception as e: error = type(e).__name__ log.RUNS.clear() importlib.import_module("plain.x") plain_result = list(log.RUNS) log.RUNS.clear() importlib.import_module("eager.x") eager_result = list(log.RUNS) teardown(root) return {"ran": ran, "registered": registered, "second": second_request, "same": relative is absolute, "relative_name": relative.NAME, "absolute_name": absolute.NAME, "attribute_bound": attribute_bound, "bound_dotted": bound_dotted, "bound_from": bound_from, "same_object": same_object, "error": error, "plain": plain_result, "eager": eager_result} with tempfile.TemporaryDirectory() as d: s = measure(Path(d)) print(f"single request ran {len(s['ran'])} bodies: {' -> '.join(s['ran'])}") print(f"package modules written to cache {len(s['registered'])}: {s['registered']}") print(f"bodies run when the same submodule is requested a second time {s['second']}") print() print(f"relative notation -> {s['relative_name']}") print(f"absolute notation -> {s['absolute_name']}") print(f"same object -> {s['same']}") print() print(f"name the dotted notation binds {s['bound_dotted']}, " f"name the from notation binds {s['bound_from']}") print(f"the module both reach is the same object -> {s['same_object']}") print(f"the subpackage is bound as an attribute on the parent package -> {s['attribute_bound']}") print(f"relative import in a package-less module -> {s['error']}") print() print(f"{'single-leaf request':<22s} {'bodies run':>12s} run order") print(f"{'plain package':<22s} {len(s['plain']):12d} {' -> '.join(s['plain'])}") print(f"{'eager importer':<22s} {len(s['eager']):12d} " f"{' -> '.join(s['eager'])}") ``` ``` single request ran 5 bodies: pkg -> pkg.sub -> pkg.sub.user -> pkg.sub.tool -> pkg.tool package modules written to cache 5: ['pkg', 'pkg.sub', 'pkg.sub.tool', 'pkg.sub.user', 'pkg.tool'] bodies run when the same submodule is requested a second time 0 relative notation -> pkg.sub.tool absolute notation -> pkg.tool same object -> False name the dotted notation binds ['pkg'], name the from notation binds ['tool'] the module both reach is the same object -> True the subpackage is bound as an attribute on the parent package -> True relative import in a package-less module -> ImportError single-leaf request bodies run run order plain package 2 plain -> plain.x eager importer 4 eager -> eager.x -> eager.y -> eager.z ``` #### Five Bodies, Five Objects The first line gives the cost of a single request, in order. `pkg.sub.user` was requested; bodies run came to **5**. The order explains itself: first `pkg`, then `pkg.sub` — the dotted name resolves left to right, and every level's body runs in its own turn. Third in line, the requested module's own body starts, and that body makes two more requests: the relative request runs `pkg.sub.tool`, the absolute one runs `pkg.tool`. Module objects created: **5**, kept: **5** — all stay registered in the cache. The third line pays this off: when the same submodule is requested a second time, bodies run: **0**. The second request creates no new object, runs no body, only hands back the cached record. The measure that follows is: **a package request's cost does not end at the requested module.** Every level in the chain, and every request made in those levels' bodies, enters the same bill. Whatever is inside a package's `__init__.py` file gets paid by anyone requesting **any** module belonging to that package. #### Same Name, Two Objects The middle section is the lesson's central measure. Inside `pkg/sub/user.py`, the same short name is written twice; the relative notation gives **`pkg.sub.tool`**, the absolute notation gives **`pkg.tool`**, and the `is` comparison is **False**. Two names, two separate objects. Created: **2**, shared: **0**. The distinction sits entirely in the **starting point**. Relative notation starts the name from the requesting module's package; because `user` sits inside `pkg.sub`, it finds its neighbor. Absolute notation starts the name from the search path and finds the package at the root. The short name written in the source files is the same in both; only the notation itself makes the difference. There is a reverse side to this too, and it follows from the rule the previous lesson measured: a cache record is kept **by name**, not by file. If the same source is requested under two separate names, two separate records open, and two separate module objects get created — the exact situation measured in the previous lesson when a cache record was removed. Because those two objects' dictionaries are independent, classes defined inside them are separate objects too; an instance produced from one does not give the expected answer when tested against the other's class. Being reachable both by package name and directly is therefore not a convenience for the same tree, it is a namespace split in two. This has a consequence on the reading side: seeing only the short name in a file does not say **which module** is meant. The same line's meaning depends on which package the file sits in. When the file is moved to a different package, a relative request silently resolves to a different object, or does not resolve at all; an absolute request is unaffected by the move. The choice between the two notations is not a matter of style, it is a decision about **which context the name binds to**. #### Which Name Gets Bound The last section gives the two notations' name-binding difference. The dotted notation only binds the name **`pkg`** on the requesting side — not the submodule's name. The submodule is reached from that name with a dot, because every level of the chain is bound as an attribute one level up. The `from` notation, by contrast, only binds the name **`tool`**; the package's name never appears on the requesting side. Even though the two notations bind different names, they reach the same object: the `is` comparison is **True**. New objects created: **0**; both share the single record in the cache. The next line shows the package side of this — the name `sub` in the parent package's dictionary and the `pkg.sub` record in the cache are **the same object**, and the same holds one level below too. The next line is relative notation's boundary. A relative request in a module that does not belong to a package results in **`ImportError`**. The reason is clear: a relative name starts from the requesting module's package; for a module with no package, there is no place to start from. This is a situation that can come up depending on **how a file is run**, and it is measured in this topic's last lesson. #### The Cost of Eager Importing The last table compares the same request in the two package notations, and the difference is born from a single line. In the plain package, requesting a single leaf runs **2** bodies: the package itself and the requested leaf. In eager notation, the same request runs **4** bodies — the package's body, and all **three** leaves it requests from within itself. The requested leaf is already among those three; looking at the order, `eager.x` ran during the package's own body, and the outside request found it already sitting in the cache once its turn came. The numbers read as a ratio: the user requested **one** leaf, paid for **three**. This ratio grows as the leaf count grows; in a ten-leaf package, a single leaf request runs all eleven. Module objects created: **2** in plain notation, **4** in eager; kept is the same, because all of them stay in the cache. This is not a defect, it is a **trade-off**, and both sides of it are measurable. Eager notation gives the user a short name and presents the package as a single surface; its cost is that it makes anyone requesting any part of the package pay for every part's body. Plain notation leaves the cost to the requester; its cost is that it requires the user to know what is in which submodule. What decides the choice is whether the package's parts are used **together or separately**. #### Summary - A package is a directory that gives a module object together with `__init__.py`; a dotted name resolves left to right, **every level is a separate object**, and every level is bound as an attribute one level up. - A single submodule request ran **5** bodies and wrote **5** module objects to the cache; the same module's second request ran **0** bodies. - The same short name gave `pkg.sub.tool` in relative notation, `pkg.tool` in absolute notation, and `is` came out **False**; the only thing making the difference is **where the name starts from**. - Dotted notation binds only the root package's name, `from` notation binds only the taken name; both create **0** new objects and share the same module object. - When `__init__.py` eagerly imports its submodules, a single-leaf request runs **4** bodies instead of **2**; the user requests one leaf, pays for three. - A relative import in a module that does not belong to a package gives `ImportError`, because there is no package for the name to start from. #### Next Step Every package measured up to here was produced for the measurement: their bodies were one line, their job was counting themselves. Yet there is a large set of packages present in every run, requiring no installation, that comes bundled with the language itself. The next lesson looks at that set's scope and measures it with a single question: writing the same job with a standard-library module versus writing it by hand — how many **objects** and how many **lines** differ, and under which conditions does the hand-written version silently diverge? ### A Tour of the Standard Library Source: https://academia.sh/en/courses/python-data-structures/standard-library-tour Writing the same job with the standard library versus by hand is measured on three axes: in the stream job the line count stays equal but objects created are 800 against 3, in name splitting 1 of five names diverges, in adding days 1 of six dates silently diverges. Every package measured in the previous lesson was produced for the measurement: their bodies were one line, their only job was counting themselves. Yet there is a large set of modules and packages present in every run, requiring no installation; it comes bundled with the language itself and already sits on the search path. This lesson looks at that set's scope. The question is not "what does each module do" — a reference list is not this lesson's job. The question is: what is the difference when the same job is written with **a standard-library module** versus **by hand**? Three axes are measured: how many objects get **created**, how many get **held**, and how many **lines** get written. A fourth thing is also counted: in how many cases the hand-written version **silently** diverges. #### The Library's Scope The standard library is part of the language and is imported without bringing anything in from outside. The areas it covers gather into a few groups. **Text and data formats:** `re` gives pattern matching, `textwrap` text wrapping, `unicodedata` character properties; `json`, `csv`, and `configparser` read and write common data formats. **Date and calendar:** `datetime` carries date and time arithmetic, `calendar` calendar queries, `zoneinfo` time zones. **File system and resources:** `pathlib` gives path objects, `shutil` bulk file operations, `tempfile` temporary space, `glob` pattern-based file selection. **Data structures:** `collections` gives specialized containers, `heapq` priority access, `bisect` position-finding in a sorted list, `array` a uniformly typed number sequence. **Functional tools:** `itertools` gives iterator combination and slicing, `functools` wrapping and caching, `operator` operators' function counterparts. **Numbers:** `math`, `statistics`, `decimal`, `fractions`, and `random` cover separate numeric domains. **Types and contracts:** `typing`, `dataclasses`, `enum`, and `abc`. **System and execution:** `sys`, `os`, `subprocess`, `argparse`, and `logging`. **Concurrency:** `threading`, `multiprocessing`, `asyncio`, and `concurrent.futures`. **Networking and transport:** `socket`, `http`, `urllib`. **Compression and digests:** `zipfile`, `tarfile`, `gzip`, `hashlib`, `hmac`, `secrets`. **Testing:** `unittest` and `doctest`. This is not memorized as a list; the useful reading is asking, when starting a job, **which group** that job falls into. Once the group is found, the module is found. #### The Cost of Importing the Library The standard library's modules also fall under the rule measured in this topic's first two lessons; they have no separate mechanism. When a library module is requested for the first time, its body runs once, the module object gets created and written to the cache; every later request for the same module runs **0** bodies and creates no new object. The `is` comparison measured in the first lesson showed this directly. In the same way, the second lesson's eager-import measurement applies to the library's package parts: when a package's submodule is requested, every level in the chain's body runs. This means using the library has a cost — but it is a cost paid **once**, and it is not the same kind as the cost hand-written code makes you pay. Hand-written code runs on every call; import runs once, then does no more work than a dictionary lookup. This is why "avoiding unnecessary imports" and "avoiding unnecessary object creation" are two separate jobs. The first is a one-time thing and is measured in module count; the second repeats on every call and is measured in item count. The measurement's first table is of the second kind. #### Three Jobs, Two Notations The measurement is run on three jobs, and each job is written twice. The first is **taking the first three items from two sources**: in the hand-written version, two lists are built and concatenated, and the first three items are sliced off at the end; in the library version, `itertools` chains the two streams and the first three items are taken. The second is **splitting a file name into its root and extension**: in the hand-written version, the name is split at the last dot; in the library version, `pathlib` builds a path object and reads the two pieces from it. The third is **adding days to a date**: in the hand-written version, month lengths and the leap-year rule are written out; in the library version, `datetime` adds two objects together. The three jobs are deliberately chosen to be of different kinds. In the first, the two notations give the same result, and the distinction is purely in cost; in the second and third, **the result itself** diverges on some inputs. This heads off a one-dimensional reading like "the library writes shorter" from the start: the gain shows up in the object in one job, in the line count in another, in correctness in a third. For an honest line count, all six notations are kept as source text; the line count is counted from that text, and the functions are produced from that same text. This way, the line counted and the line that runs are the same. The measurement's assumptions: - **MP20** — The `Item` class is taken from the shared setup; its counting scheme is unchanged, and the counter is reset before every measurement. - **MP21** — In the stream measurement, each of the two sources carries **400** values; the total is **800**. - **MP22** — "Held in the intermediate container" is the number of items sitting in an intermediate list the moment the function returns its result; because the lazy notation builds no such list, **0** is written for it. - **MP23** — Line count is the number of lines in the function's source text with blank ends stripped; the same text produces the function that runs. - **MP24** — Six names and six dates are **chosen by hand**, to cover edge cases, not at random. - **MP25** — The oracle is the standard library's result; the hand-written version diverges from or agrees with it. - **MP26** — The hand-written leap-year rule is the **divisible-by-four** rule; the century correction is deliberately not written. - **MP27** — The dates in the day-adding measurement cover year, month, and century boundaries; results are compared as a year, month, day triple. - **MP28** — The measurement touches no file; path objects are built purely as names and never asked of the file system. #### Measurement ```python """Standard library: how many objects and lines when the same job is written by hand.""" from datetime import date, timedelta from itertools import chain, islice from pathlib import PurePosixPath COUNTER = {"created": 0} class Item: """Counts every creation of itself; the shared setup's counting scheme is unchanged.""" def __init__(self, value): COUNTER["created"] += 1 self.value = value SOURCE = { "manual_stream": """ def manual_stream(a, b): combined = [Item(d) for d in a] + [Item(d) for d in b] return combined[:3], len(combined) """, "library_stream": """ def library_stream(a, b): stream = chain((Item(d) for d in a), (Item(d) for d in b)) return list(islice(stream, 3)), 0 """, "manual_split_name": """ def manual_split_name(name): base = name.rsplit("/", 1)[-1] if "." not in base: return base, "" root, dot, tail = base.rpartition(".") return root, dot + tail """, "library_split_name": """ def library_split_name(name): path = PurePosixPath(name) return path.stem, path.suffix """, "manual_add_days": """ def manual_add_days(y, m, d, days): lengths = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] for _ in range(days): days_in_month = lengths[m - 1] if m == 2 and y % 4 == 0: days_in_month = 29 d += 1 if d > days_in_month: d, m = 1, m + 1 if m > 12: m, y = 1, y + 1 return y, m, d """, "library_add_days": """ def library_add_days(y, m, d, days): result = date(y, m, d) + timedelta(days=days) return result.year, result.month, result.day """, } NAMESPACE = {"Item": Item, "chain": chain, "islice": islice, "date": date, "PurePosixPath": PurePosixPath, "timedelta": timedelta} for source in SOURCE.values(): exec(source, NAMESPACE) def line_count(name): return len(SOURCE[name].strip().splitlines()) def measure_stream(function_name, n=400): COUNTER["created"] = 0 result, intermediate = NAMESPACE[function_name](range(n), range(n)) return COUNTER["created"], intermediate, len(result) NAMES = ["data.csv", "archive.tar.gz", ".hidden", "folder/name.txt", "name"] DATES = [(2024, 2, 28, 1), (2023, 2, 28, 1), (2100, 2, 28, 1), (2000, 2, 28, 1), (2024, 12, 31, 1), (2024, 1, 31, 45)] print(f"{'first three items from two sources':<26s} {'lines':>5s} {'created':>10s}" f" {'held in intermediate':>17s} {'returned':>10s}") for name, label in (("manual_stream", "manual"), ("library_stream", "library")): created, intermediate, returned = measure_stream(name) print(f" {label:<24s} {line_count(name):5d} {created:10d} {intermediate:17d}" f" {returned:10d}") print() print(f"name splitting: manual {line_count('manual_split_name')} lines, " f"library {line_count('library_split_name')} lines") diverging = [(a, NAMESPACE["manual_split_name"](a), NAMESPACE["library_split_name"](a)) for a in NAMES if NAMESPACE["manual_split_name"](a) != NAMESPACE["library_split_name"](a)] print(f"names tried {len(NAMES)}, diverging {len(diverging)}") for a, m, l in diverging: print(f" {a:16s} manual {m} library {l}") print() print(f"adding days: manual {line_count('manual_add_days')} lines, " f"library {line_count('library_add_days')} lines") deviating = [(t, NAMESPACE["manual_add_days"](*t), NAMESPACE["library_add_days"](*t)) for t in DATES if NAMESPACE["manual_add_days"](*t) != NAMESPACE["library_add_days"](*t)] print(f"dates tried {len(DATES)}, deviating {len(deviating)}") for t, m, l in deviating: print(f" {t} manual {m} library {l}") ``` ``` first three items from two sources lines created held in intermediate returned manual 3 800 800 3 library 3 3 0 3 name splitting: manual 6 lines, library 3 lines names tried 5, diverging 1 .hidden manual ('', '.hidden') library ('.hidden', '') adding days: manual 12 lines, library 3 lines dates tried 6, deviating 1 (2100, 2, 28, 1) manual (2100, 2, 29) library (2100, 3, 1) ``` #### Same Lines, Different Objects The first table is this lesson's most contrarian result: the two notations' **line count is equal**, both **3**. The library does not shorten the writing here. Where they part is in the object counted: the hand-written version creates **800** items, the library version **3**. Returned is **3** in both. The difference comes from **at which point** the work is done. In the hand-written version, two lists are built with a comprehension; the moment a comprehension is built, it creates every item, then the two get concatenated, and only at the very end are the first three taken. In the other notation, `itertools` chains the two streams **without consuming** them, and when the first three items are requested, only three items get created; the remaining 797 never get produced at all. The intermediate-container column shows the holding separately: in the hand-written version, **800** items are still sitting in a list the moment the result returns; in the library version, **0**. This is the standard library's face of the course's second claim — the lazy notation here does not merely delay production, it **never produces what is never requested at all**, because the stream is not consumed to the end. This distinction's boundary must not be misread. The library's chained stream does **not avoid** production; it only ties production to consumption. Had the same stream been consumed to the end, it too would have created **800** items, and the production difference between the two notations would have zeroed out; the only difference left standing would be the item count held in the intermediate list. The source of the gain is not laziness itself, it is **how little was requested**: three items were requested, three items were produced. The rule that follows is: **what the standard library earns you is not always lines.** Some modules shorten the writing, some leave the writing the same and lower the objects created instead. The two are separate gains and are measured separately. The question to ask when choosing a module should not be "how many lines does it shorten" but "which axis does it change." #### Line Difference and Silent Divergence In the second and third measurements, the table flips: the line difference is large. Name splitting is **6** lines by hand, **3** with the library; adding days is **12** by hand, **3** with the library. A quarter-ratio difference — but the real cost is not in the lines. In name splitting, **1** of the **5** names tried diverges. For the leading-dot name `.hidden`, the hand-written version leaves the root empty and counts the extension as `.hidden`; the library, by contrast, takes the whole name as the root and the extension as empty. For the multi-extension `archive.tar.gz` and the directory-carrying `folder/name.txt`, the two notations agree — the divergence is not in **every** case, only at the edges. In adding days, **1** of the **6** dates tried deviates, and the deviation sits at a century boundary. The hand-written leap-year rule looks only at divisibility by four; since 2100 divides by four, the hand-written version counts February as 29 days and gives **(2100, 2, 29)**. The library gives **(2100, 3, 1)**, because it also applies the century rule. In the remaining five cases — a year boundary, a leap year, and a forty-five-day jump — the two notations give the same result. The lesson shared by both measurements is this: **hand-written code does not give a wrong result loudly.** No exception is raised, no warning appears; the result is merely, silently, different. Because agreement holds in most of the tried cases, if the test set does not include the edges, the divergence never shows at all. What the standard library mainly earns you is that those edge cases are **already written**. #### Why the Two Divergences Are Not the Same Kind Even though the numbers sit in the same column, the two divergences are not the same thing, and confusing them is this measurement's easiest misreading. The deviation in adding days is a **mistake**. The calendar rule is not the language's preference, it is a rule defined outside it; a notation that does not write the century correction fails to follow that rule, and the date it gives is not correct under any reading. Here the library is the oracle, because it applies the whole rule. The divergence in name splitting, by contrast, is a **difference in contract**. Whether a leading-dot name has an extension is not an externally fixed fact the way the calendar is; the library chose one rule, the hand-written version chose another. Treating hidden file names as extensionless is a common convention and the library applies it; but an application may need the opposite. The **1** diverging case is not the hand-written version's defect, it is the point where two contracts part ways. The criterion that follows from this: the decision to write a job by hand is justified when it can **show** that the library's contract does not fit the job. A hand-written solution written without knowing what the library does fails this criterion; a solution written knowing the difference meets it. The two situations' source text looks the same; the only thing that tells them apart is whether the difference was measured. #### Summary - The standard library is part of the language; it covers text, data format, calendar, file system, data structure, functional tool, number, system, concurrency, network, and testing groups. - In the stream job, the two notations' line count is equal (**3** and **3**), but the hand-written version creates **800** items, the lazy version **3**; held in the intermediate container is **800** against **0**. - The library's gain is not always lines: some modules shorten the writing, some lower the objects created instead; the two gains are measured separately. - In name splitting, the hand-written version costs **6** lines and diverges from the library on **1** of **5** names tried; the divergence sits only at the edge names. - In adding days, the hand-written version costs **12** lines and deviates on **1** of **6** dates tried; the deviation comes from not writing the century rule. - A hand-written mistake raises no exception; the result comes out silently different, which is why a test set with no edge cases never shows the divergence at all. #### Next Step In this lesson, everything was imported: the library modules and the measurement functions alike were defined inside a body and called from outside. Yet the same file can run in two separate forms — one as an imported module, the other as a directly run script. The same body runs in both forms, but the module's own name changes, and a block that looks at that name runs in only one case. The next lesson measures this duality: when the same file is run in two forms, **how many module objects** get created, and what happens to the old objects when a module gets reloaded? ### Reloadability and the Main Block Source: https://academia.sh/en/courses/python-data-structures/reloadability-and-main-block The same file creates one module object when imported and a second when run as a script, and the main block runs only in the second; reload keeps the module object but renews every function inside it. In the previous lesson, everything was imported: the library modules and the measurement functions alike were defined inside a body and called from outside. Yet the same file can work in two separate forms. One is the form measured up to here — the file is requested as a **module**, its body runs, and its names are opened up for others to use. The other is running it directly: the file is launched as a **script** and becomes the program's entry point. The same body runs in both forms. The only thing that differs is what gets written into the module's **own name**, and a block that looks at that name runs in only one case. This lesson's question is: when the same file is run in two forms, **how many module objects** get created, which record holds which, and what happens to old objects taken from a module when it gets reloaded? #### The Module's Own Name Every module object's dictionary has an entry named `__name__`, and import fills that entry with the module's **name in the cache**. When a file is imported, the file's module name gets written there. When the same file is run directly, `"__main__"` gets written there instead, because that run has no import name — it was not requested, it was launched. The **main block** is the condition that reads this distinction. A block at the end of the body that compares `__name__` to `"__main__"` runs when the file is run as a script, and does not run when it is imported. This is how a file can be both a library and an entry point: definitions sit in the body and are open to everyone, running sits inside the block and only works on a direct run. This has a measurable consequence, and it does not contradict the rule established in the first lesson, it follows from it: a cache record is kept **by name**. A file run as a script gets registered under the name `__main__`, the same file imported under its own name. Two separate names, two separate records, meaning **two separate module objects** — from the same file. #### What Reload Changes When the module cache drops a record, the next request creates a new object; this was measured in the first lesson. **Reload**, by contrast, is a different job: it reruns the body, but writes into **the existing module object's dictionary**. The module object stays the same, the names inside it get refreshed. The distinction has two observable consequences, and the measurement tests both: because the body reruns, every definition produces **a new object**, and the write is done **without emptying** the dictionary. The measurement's assumptions: - **MP29** — The measurement leaves no file in the repository; sources are produced in a temporary directory and **the directory's path is not printed.** - **MP30** — The measured file writes its own name to a shared list on every run; the counting side is the measured file itself. - **MP31** — The script run opens no separate process. It is run in the same interpreter, with the module's own name set to `__main__`; this is why the measurement can read the shared list. - **MP32** — The main block only drops a record into the list; no other work is done inside it. - **MP33** — Before reloading, **a single string** in the source text is changed; the only thing that changes is the value the function returns. - **MP34** — Before reloading, a name is added to the module from outside, and that name's fate is separately read. - **MP35** — The old function object is bound to a separate name before reloading; comparisons are made with `is` and **no identity number is printed.** - **MP36** — When the measurement ends, the added path entry and all cache records are rolled back. #### Measurement ```python """Main block and reload: how many module objects does the same file create.""" import importlib import runpy import sys import tempfile from pathlib import Path TOOL = """import log log.EVENTS.append(('body', __name__)) def greet(): return 'first' if __name__ == '__main__': log.EVENTS.append(('main block', __name__)) """ LOG_SOURCE = "EVENTS = []\n" def setup(root): (root / "log.py").write_text(LOG_SOURCE, encoding="utf-8") (root / "tool.py").write_text(TOOL, encoding="utf-8") sys.path.insert(0, str(root)) importlib.invalidate_caches() def teardown(root): sys.path.remove(str(root)) for name in ("log", "tool"): sys.modules.pop(name, None) def measure(root): setup(root) log = importlib.import_module("log") tool = importlib.import_module("tool") import_run = list(log.EVENTS) log.EVENTS.clear() script = runpy.run_module("tool", run_name="__main__") script_events = list(log.EVENTS) separate_object = script["greet"] is not tool.greet cache_intact = sys.modules["tool"] is tool log.EVENTS.clear() tool.ADDED = "before reload" old_greet = tool.greet (root / "tool.py").write_text(TOOL.replace("'first'", "'second'"), encoding="utf-8") importlib.invalidate_caches() reloaded = importlib.reload(tool) result = { "import_run": import_run, "script": script_events, "separate_object": separate_object, "cache_intact": cache_intact, "reload_events": list(log.EVENTS), "same_module": reloaded is tool, "old_function": old_greet is tool.greet, "old_value": old_greet(), "new_value": tool.greet(), "added_survived": getattr(tool, "ADDED", "deleted"), } teardown(root) return result with tempfile.TemporaryDirectory() as d: s = measure(Path(d)) print(f"ran during import: {s['import_run']}") print(f"ran when run as a script: {s['script']}") print(f"function in the script namespace is a separate object from the module's -> {s['separate_object']}") print(f"the cache record is not disturbed -> {s['cache_intact']}") print() print(f"ran during reload: {s['reload_events']}") print(f"module object is the same -> {s['same_module']}, " f"function object is the same -> {s['old_function']}") print(f"the function bound to the old name gives {s['old_value']}, " f"the module's function gives {s['new_value']}") print(f"name added before reload -> {s['added_survived']}") ``` ``` ran during import: [('body', 'tool')] ran when run as a script: [('body', '__main__'), ('main block', '__main__')] function in the script namespace is a separate object from the module's -> True the cache record is not disturbed -> True ran during reload: [('body', 'tool')] module object is the same -> True, function object is the same -> False the function bound to the old name gives first, the module's function gives second name added before reload -> before reload ``` #### Two Runs, Two Objects The first two lines give the main block's rule directly. The only thing that ran on import is the body, and the module's own name is `tool`; there is **no** main block record. Running as a script reruns the same body, but this time the module's own name is `__main__`, and the main block runs too. Same file, same lines, two different results — the only thing making the difference is the value written to the name. The third line shows the cost: the function in the script run's namespace is **a separate object** from the module's function. Because the body ran a second time, the `def` statement created a second function object. Module objects created from the same file: **2**, shared between them: **0**. The fourth line completes this: the `tool` record in the cache is not disturbed, it is still bound to the first object. The two runs stand side by side and do not see each other. This explains why writing work into the main block is limited. If a file gets both imported and run as a script, the two runs produce **two separate namespaces** carrying the same names. A counter or cache kept at module level gets created twice; what gets written into one is not visible in the other. The only reason this does not show up in the measurement is that the counted list sits not in `tool` but in the `log` module both share. The rule is: **an entry point is a shell** — state and definitions stay in the body, the main block only calls a function. #### Reload The lower section measures a separate mechanism. What ran during reload is again the body, and the module's own name stays as **`tool`** — this is the difference from the script run. The next line gives the heart of the distinction: the module object is **the same**, the function object is **not**. Because the body reran, `def` created a new function object, and the name in the module's dictionary got bound to it; the module object itself never changed. The third line shows whose view this breaks. The side that took the function under its own name before reloading holds the **old** object, and that object gives **first**; the function called through the module gives **second**. Only those reading the change from the module's dictionary saw it. Function objects created: **2**, held: **2**, shared: **0**. The distinction the first lesson measured is paid off again here: import shares the object, it copies the name — a copied name does not get refreshed. The last line confirms the dictionary was not emptied: the name added to the module from outside before reloading **is still there**. Reload is not a cleanup, it is an overwrite. Every name with no counterpart in the new body — a removed definition, an attribute added from outside — keeps its old value. What the two measurements say together is: **rerunning a source has three separate outcomes.** If the cache record is removed and it is requested again, a new module object gets created; if it is reloaded, the module object is kept, its contents get renewed; if it is run as a script, a second object gets created under a second name, and the first stays as it was. In all three, the body runs one more time, but the objects created and held are different in all three. #### Summary - The module's own name is filled with the module name on import, with `__main__` on a direct run; the main block only runs in the second case. - When the same file is run in two forms, **2** module objects get created; the definitions the two namespaces share is **0**, and the cache record from the import is not disturbed. - The main block is written as a shell: definitions and state stay in the body, because the body runs in both forms and every module-level piece of state gets created twice. - Reload **keeps** the module object, reruns the body, and binds the names inside it to new objects; an old function object taken beforehand keeps giving its old value. - Reload does not empty the dictionary; names with no counterpart in the new body stay in place with their old values. #### Course Wrap-Up The course ran on a single question: how many objects did the written form **create**, how many did it **hold**, what did it **share**? The result itself was never counted as the measure in any lesson, because the counts of two notations giving the same result diverged every time. | Lesson | Form measured | Created / held / shared | |---|---|---| | `collections/01` Lists | a thousand-item list and eight growth forms | 1000 created and held; binding a second name creates 0, `[one] * 5` creates 0 and shares one item across five slots | | `collections/02` Tuples | six operations immutability closes off and `t += (new,)` | 1 created; the container is new, items are shared (`big[0] is tup[0]` → True); multiple return creates 0 | | `collections/03` Dictionaries | membership on two hundred items and the `keys()` view | 200 comparisons in a list, 1 in a set and dict; the view shares the dict and grows from 2 to 3, a snapshot copy holds 1000 slots | | `collections/04` Sets | deduplicating three hundred items and six set operations | 15050 comparisons by hand, 200 with a set; six operations create 0 items and every object in the result is shared | | `collections/05` Specialized Collections | three notations of the same grouping and trimming a thousand-item stream | `setdefault` creates 320, a default dict 100 containers; in the stream all three notations produce 1000, held is 1000 against 5; returning creates 3 intermediate containers with a list, 0 with a deque | | `collections/06` Slicing | eight slice forms and copying a nested list | all eight create 0 items and return a new container; in a nested list 4 get produced and a slice copy shares both inner lists, a deep copy gives 4 | | `iteration/01` Iterator Protocol | the `iter` and `next` contract, three traversal forms | `iter` writes 0 references, `list()` writes 3, a comprehension creates 3 new objects; the first two share items, the last shares 0 | | `iteration/02` Generators | calling a function containing `yield`, and `yield from` | at setup a comprehension creates 1000, a generator 0; at three items it stays at 3, `yield from` stays at 1 up to the first item | | `iteration/03` Generator Expressions | two notations of summing a thousand items | both create 1000 and give 499500; held is 1000 against 0 in the list | | `iteration/04` Comprehension Syntax | list, set, dict comprehension, and where the filter condition sits | 1000 / 100 / 100 held, shared 1000 / 0 / 100; filtering before production creates 5, after creates 10 | | `iteration/05` Lambda and Higher-Order Functions | how many times the key function is called, and `map` with `filter` | key called once per item, 200 calls total; a hand-written sort makes 39800; `sorted` builds a new container and shares 200 items, `map` creates 0 at setup | | `iteration/06` Decorators | the layers wrapping builds and preserving metadata | unwrapped 1, one decorator 2, two decorators 3 layers; the object bound to the name changes, the original function is shared (`single.__wrapped__ is compute` → True); a memoizing wrapper reduces 20 requests to 5 calls and holds 5 items | | `modules-and-packages/01` The Module System | three import requests and search path order | 2 module objects created, 1 held; two names share the same object and the shared log module stays at 1 | | `modules-and-packages/02` Package Structure | the object relative and absolute notation resolve to | a single request runs 5 bodies and holds 5 objects; relative and absolute share 0 (`is` → False) | | `modules-and-packages/03` A Tour of the Standard Library | the same three jobs written with the library and by hand | by hand creates 800 and holds 800, with the library creates 3 and holds 0; the result is 3 in both | | `modules-and-packages/04` Reloadability and the Main Block | import, script run, and reload | a script run creates a 2nd module object, the first is kept, shared definitions 0; reload shares the module, renews the function | Four readings cut across the table. **Laziness does not reduce production, it reduces holding:** in summing a thousand items, both notations produce 1000 objects and both give 499500; the only place they part is what is held in the list. **A copy is one layer deep:** every operation that builds a new container renews the outer container and shares what is inside it — in tuples, in slicing, in set operations alike. **What decides the cost is not the data but the form of access:** the same two hundred items ask for 200 comparisons in a list, 1 in a set. **A module is an object too, and it gets created once:** the last topic carried the same counting scheme past the file boundary and measured that import is an act of creation too. Throughout the course, the containers stood ready-made. List, tuple, dict, set, generator, and module — all were objects the language gave, and what was measured was the cost of **choosing** them. The next course stands on the other side of this boundary. **Choosing a container and writing a container are different things:** an object having a length, being comparable, and being able to serve as a key in a container is not a chosen trait, it is a contract that gets **written**. The Object-Oriented Python and Types course builds the side that writes that contract: classes that fit the language's syntax, situations where composition is chosen over inheritance, and contracts made explicit with type hints. Here, how many objects each container cost was counted; there, the object that will stand in its place will itself be written.