Use a Set for Lookups and a Deque for Queues

Your script reads 200,000 user IDs from a log and skips any ID it has already seen. It keeps the seen IDs in a list, and it gets slower the further it reads. This snippet shows the effect. It checks 1,000 times for a name that is not there:

import time

for size in (10_000, 20_000, 40_000):
    names = [f"user{i}" for i in range(size)]
    name_set = set(names)

    start = time.perf_counter()
    for _ in range(1_000):
        found = "nobody" in names
    list_ms = (time.perf_counter() - start) * 1000

    start = time.perf_counter()
    for _ in range(1_000):
        found = "nobody" in name_set
    set_ms = (time.perf_counter() - start) * 1000

    print(f"{size:>6} names: list {list_ms:5.1f} ms, set {set_ms:.2f} ms")

On a laptop with Python 3.15, it printed:

 10000 names: list  42.1 ms, set 0.03 ms
 20000 names: list  84.2 ms, set 0.03 ms
 40000 names: list 169.4 ms, set 0.03 ms

Twice the names take the list twice as long. The set takes the same time at every size.

A list checks every item, a set goes to one place

x in some_list compares x with the first item, then the second, and so on until one is equal. When x is missing, it compares every item. So the time grows with the length of the list.

A set keeps its items in a table. To store an item, it calls hash(item), which turns the value into a number, and uses that number to pick a slot. x in some_set computes hash(x), goes straight to that slot and compares only what it finds there. The time stays about the same however many items the set holds.

Dictionaries store their keys the same way, so key in some_dict is fast too. It checks the keys, not the values.

A set accepts only hashable values, whose hash never changes. Strings, numbers and tuples of them are hashable. Lists, dictionaries and sets are not, because they can change after you add them. {[1, 2]} raises a TypeError that calls the list unhashable. Use a tuple instead.

Common mistakes

• Building the set inside the loop. if user in set(seen): builds a new set on every pass, which costs more than scanning the list. Build the set once, before the loop, and add to it.
• Testing a generator twice. x in some_generator reads items until it finds x, and the items it read are gone. If you need to test the same input more than once, build a set from it first.

Use a deque for a queue

A queue takes items from the front and adds them at the back. With a list, jobs.pop(0) moves every remaining item one place to the left, so each call gets slower as the list grows.

A deque, short for double-ended queue and said "deck", is a sequence from collections built for this. Adding or removing an item at either end takes the same short time however long the deque is. Give it a maxlen and it keeps only the newest items. When it is full, append drops the oldest item from the other end:

from collections import deque

jobs: deque[str] = deque(["resize", "upload"])
jobs.append("notify")  # add at the back
assert jobs.popleft() == "resize"  # take from the front
assert list(jobs) == ["upload", "notify"]

recent: deque[str] = deque(maxlen=3)
for event in ["start", "load", "run", "finish"]:
    recent.append(event)
assert list(recent) == ["load", "run", "finish"]

Reading jobs[0] or jobs[-1] is fast. Reading an item near the middle is slow, because the deque has to walk to it. If your code reads items[i] at any position, keep a list.

Going further

A set lookup is fast on average. Values with the same hash collide, and many collisions make lookups slow. Built-in types rarely cause this. The Python wiki's time complexity page lists the cost of each list, deque, set and dictionary operation. The deque documentation lists its methods.