Hidden loops
Read · 1 of 2
One line, many steps
Python manages roughly 10 million simple steps a second. A loop over 100,000 items is fine; a loop inside a loop is 10 billion steps: minutes, when the limit is seconds.
The inner loop isn't always visible. x in some_list, some_list.count(x), some_list.index(x) and some_list.remove(x) each walk the whole list. Inside a loop, they make it quadratic. A set or dict answers x in in about one step.
Read this lesson as text
One line of Python can hide a whole loop.
One line, many steps
Python manages roughly 10 million simple steps a second. A loop over 100,000 items is fine; a loop inside a loop is 10 billion steps: minutes, when the limit is seconds.
The inner loop isn't always visible. x in some_list, some_list.count(x), some_list.index(x) and some_list.remove(x) each walk the whole list. Inside a loop, they make it quadratic. A set or dict answers x in in about one step.
Counting repeats
n = int(input())
nums = list(map(int, input().split()))
seen = []
repeats = 0
for x in nums:
if x in seen:
repeats += 1
else:
seen.append(x)
print(repeats)n can be 100,000. Is this fast enough?
- Yes: it's only one loop
- No:
x in seenwalks the whole list every time, so it's about n² steps - No:
appendis slow
Show the answer
No: x in seen walks the whole list every time, so it's about n² steps. seen grows to 100,000 items and x in seen checks them one by one: about 5 billion steps. Make seen a set and the same code runs in a blink.