Lessons · Python · scanning a list is slow

One pass, one running fact

Many problems that look like they need to look backwards can be solved by walking forward once and remembering a single number.

Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.

What it is for

Data that streams past you (prices, sensor readings, log lines) cannot be re-read. And one pass over a million items is fine; a pass per item is a million million.

How to think about it

Ask: as I move through the items, what is the ONE thing about the past that decides the answer at this point? The minimum so far? The running total? Keep that, update it each step.

Worked example

readings = [5, 3, 8, 2, 9]

We want the biggest jump from any earlier reading to a later one.

lowest = readings[0]; best = 0

The one fact about the past: the lowest value seen so far.

for r in readings[1:]:

Walk forward once.

    best = max(best, r - lowest)

The best jump ending here uses the lowest value before here.

    lowest = min(lowest, r)

Then update the fact for the next step.

Your turn

Find the largest value in one pass without max().

biggest = nums[0]
for n in nums:
    if n > :
         = n

The trap

Updating the running fact BEFORE using it. Use the past to judge the present, then update.

Practise scanning a list is slow on HoneA question on it now, a coding challenge where there is one, and it is remembered for review. Free, no email needed.