Syllabus Lesson 53 of 141 · Speed without the cache
Speed without the cache

Why not just cache it?

Why it matters Ask an assistant to make something faster and the first answer is very often "add a cache". Sometimes that is right. Often the problem has a rule that makes it wrong, and the faster route is to do less work, not to remember more of it.

A cache trades memory for repeated work. It pays off when the same question comes back many times, the answer does not go stale, and there is room to keep the answers. Take away any one of those and the cache becomes a cost: it grows without limit, serves old data, or never gets a hit.

Cache: a store of answers already computed, kept so the same question can be answered again without the work.

Routes that need no cache

  • Precompute once: one pass that builds exactly what the questions need, such as running totals.
  • Use the order you were given: sorted data lets two pointers or a binary search skip most of it.
  • Stream it: keep a running summary and never hold the whole input.
  • Bound the search: stop as soon as nothing left can beat the best answer so far.

In this module the data comes as a Tape, which counts every value you read, and some problems cap the memory your function may use while it runs. The cap is measured with Python's own tracemalloc, which sees copies made inside built-ins too: list(tape) and set(tape) are not free.

import tracemalloc
tracemalloc.start()
result = my_function(tape)
peak_bytes = tracemalloc.get_traced_memory()[1]
tracemalloc.stop()

Recap A cache needs repeats, freshness and room. When a problem rules one out, look for work you can skip instead of work you can remember.

Spotted a problem in this lesson? Report it · Ask about this lesson

This exercise opens soon

Finish the lesson before it and this one unlocks. The whole course is free, no account needed, and you can read this lesson right now.

Start at lesson 1 Back to syllabus