Why is my Python loop so slow when checking if an item is in a list?
Short answer
Checking membership in a list scans it from the start, so doing that inside a loop makes the work grow with the square of the size. Convert the list to a set first and each check becomes effectively instant.
The short version
x in some_list scans the list item by item, so it gets slower as the list grows. Doing it inside a loop over another large collection means the total work grows with the product of the two sizes, which is why an apparently harmless script suddenly takes minutes. Convert the list you are searching into a set first, and each check becomes effectively instant.
The slow pattern
known = [...] # a list of, say, 100,000 ids
results = []
for row in rows: # another 100,000 rows
if row.id in known: # scans up to 100,000 items EACH TIME
results.append(row)
That is up to ten billion comparisons. The code looks perfectly reasonable, which is what makes this trap so common.
The fix
known = set(known) # build once, hash-based
results = [row for row in rows if row.id in known]
Membership in a set is effectively constant time, so the total work is now proportional to the number of rows, not to rows times ids. The same script drops from minutes to a fraction of a second.
Why sets are so much faster
A set stores items by hash, so it can jump straight to where an item would be, rather than walking the whole collection. That is the whole difference: a list answers "is this here" by looking everywhere, a set by looking in one place.
The cost of building the set
Building the set is a single pass over the list, which is cheap and done once. If you only ever test membership once, converting is not worth it. The moment you test repeatedly, inside a loop, converting pays for itself immediately.
The same trap in pandas
The pandas version of this mistake is filtering inside a loop, or using in against a Series. Use isin, which does the whole thing at once in optimised code.
# slow
df[df["id"].apply(lambda i: i in known_list)]
# fast
df[df["id"].isin(known_set)]
Dictionaries too
The same hashing applies to dictionary keys, so key in some_dict is fast for the same reason. If you find yourself scanning a list of records to find one by id, you probably want a dictionary keyed by id, built once.
by_id = {r.id: r for r in records} # build once
by_id.get(wanted_id) # instant lookup
The general lesson
Most mysteriously slow Python is not slow because Python is slow; it is slow because of an accidental quadratic. The signature is a scan (a list membership test, a repeated filter, a nested loop over the same data) hidden inside another loop. Learn to spot it, and reach for a set or a dictionary, and you will fix more performance problems than any amount of micro-optimisation.