deep_sizeof: count every distinct object exactly once

Write the traversal that sys.getsizeof is not.

def deep_sizeof(
    obj: object,
    sizer: Callable[[object], int],
    seen: set[int] | None = None,
) -> int: ...

Sum sizer(x) over every distinct object reachable from obj, counting each one exactly once.

The sizer is a parameter, and fake_size — provided, with fixed made-up numbers — is what the tests use. In production you would pass sys.getsizeof; here that would make the expected values depend on your build, your platform and your Python version, which is precisely the class of test that fails on someone else’s laptop for reasons unrelated to the code. Injecting the measurement is how you make a memory tool testable at all, and it is worth noticing that this is the same move as injecting a clock.

build(scenario, n) is provided and constructs the structure. solve returns {"deep": deep_sizeof(root, fake_size), "shallow": fake_size(root)} so the gap between the two is visible.

Three constraints, and all three are load-bearing.

Identity, not equality. The visited set must be set[int] keyed on id(). Lists, dicts and sets are unhashable, so set[object] does not work at all; and if obj in seen on a list calls __eq__, which is a deep comparison (slow) that also treats two structurally-equal distinct objects as one (wrong). id() is unique among simultaneously-live objects, which is exactly the guarantee you need here because you hold the whole graph alive while walking it.

Cycles. scenario="cyclic" builds a list containing itself. The same visited set handles it.

str is atomic. A str is a Sequence of str, and "h"[0] is "h", so a traversal that treats every Sequence uniformly either recurses forever or terminates by accident. str, bytes and bytearray must be sized and not descended into. This is the single most common bug in hand-written deep_sizeof implementations.

And one that is about the harness rather than the algorithm: scenario="chain" builds a 5,000-deep nesting. A recursive implementation raises RecursionError there, on a shape — deeply nested JSON, a long linked list — that production produces routinely.

Dispatch over collections.abc.Mapping (keys and values) and Sequence/Set rather than concrete dict/list checks, so the function also works on Counter, defaultdict and anything else that registers.

Your submission must pass mypy --strict.