🔬 Python Code Lab — ⚡ List vs Set Lookup: How Big Is the Difference? 🐍

Python provides several built-in data structures, and choosing the right one can significantly affect application performance.

Lists and sets both support membership checks using the in operator. However, they use different internal mechanisms to determine whether an element exists.

A list generally searches through its elements sequentially, while a set uses a hash table to perform lookups.

But how much of a difference does this actually make?

In this Python Code Lab experiment, we'll use Python's built-in timeit module to benchmark list and set membership checks across increasing collection sizes.

---

What Are We Testing?

We'll compare two collections containing identical integer values:

• List: An ordered collection that supports indexing and duplicate elements.
• Set: A collection of unique, hashable elements optimized for efficient membership checks.

Our experiment will measure lookup performance across four collection sizes:

collection_sizes = [100, 1_000, 10_000, 100_000]

We'll test two scenarios:

1. Existing Element: Searching for the final element in each list.
2. Missing Element: Searching for a value that doesn't exist in either collection.

This helps us understand how membership-check performance changes as collections grow.

---

Creating the Collections

First, we'll create a list and a set containing the same integers.

sample_list = list(range(1_000))
sample_set = set(sample_list)

target = 999

print("List lookup:", target in sample_list)
print("Set lookup:", target in sample_set)

Both membership checks return True.

Although the results are identical, the operations used to find the element are different.

For a list, Python may need to examine multiple elements before finding the target.

For a set, Python uses the element's hash to locate it efficiently.

---

Measuring Lookup Performance

We'll use Python's timeit module to measure how long each membership check takes.

def benchmark_lookup(collection, target):
    def lookup():
        return target in collection

    timings = timeit.repeat(
        lookup,
        number=iterations,
        repeat=repeats,
    )

    best_time = min(timings)

    return (best_time / iterations) * 1_000_000

The benchmark runs each membership operation repeatedly and selects the fastest recorded repetition.

The result is converted into microseconds (µs) per lookup, allowing us to compare even very small execution times.

Importantly, collection creation happens outside the timed operation. This ensures we're measuring lookup performance rather than the time required to construct the collections.

---

Benchmarking Existing Elements

Our first experiment searches for the final element in each collection.

for size in collection_sizes:
    numbers_list = list(range(size))
    numbers_set = set(numbers_list)

    target = size - 1

    list_time = benchmark_lookup(numbers_list, target)
    set_time = benchmark_lookup(numbers_set, target)

For a list, finding the final element generally requires checking all preceding elements.

As the collection grows, this operation becomes increasingly expensive.

Sets behave differently. Their hash-based lookup mechanism typically allows membership checks to remain fast regardless of collection size.

The experiment calculates the relative speed difference:

speedup = list_time / set_time

A value greater than 1x indicates that the set lookup was faster in that measurement.

---

What Happens When an Element Is Missing?

The second experiment searches for a value that doesn't exist.

target = -1

list_time = benchmark_lookup(numbers_list, target)
set_time = benchmark_lookup(numbers_set, target)

For a list, Python must examine every element before determining that the target is absent.

For a set, Python can generally determine that the value is missing through its hash-table lookup mechanism.

This makes missing-element searches particularly useful for observing the difference between sequential and hash-based lookup.

The exact benchmark results depend on the Python version, hardware, and execution environment.

---

Understanding the Performance Difference

The primary difference comes from the time complexity of the underlying lookup operations.

List Lookup — O(n)

Lists generally perform sequential membership searches.

In the worst case, Python examines every element before finding the target or determining that it doesn't exist.

As a result, lookup time can increase proportionally with the number of elements.

Set Lookup — O(1) Average

Sets use hash tables to locate elements.

Instead of examining every element sequentially, Python uses the target's hash to determine where to search.

This provides approximately constant-time membership checks on average, although pathological hash collisions can cause slower performance.

Operation	List	Set
Membership lookup (average)	O(n)	O(1)
Membership lookup (worst case)	O(n)	O(n)
Supports duplicates	Yes	No
Supports indexing	Yes	No
Requires hashable elements	No	Yes

While sets generally perform better for repeated membership checks, lists remain useful when indexing, ordering, or duplicate values are important.

---

When Should You Use a Set?

Consider an application that repeatedly checks whether a user ID exists in a collection.

allowed_users = {101, 102, 103, 104, 105}

if 103 in allowed_users:
    print("User is allowed")

When membership checks are frequent and the collection is large, a set can be an appropriate choice.

However, converting a list into a set also requires time and additional memory. For a single lookup against a small collection, conversion may not provide any practical benefit.

The best choice depends on how frequently the collection is searched and which other operations the application needs.

---

Key Takeaways

• Lists generally perform sequential membership searches with O(n) average time complexity.
• Sets use hash tables and provide O(1) average membership lookup.
• The performance difference becomes more noticeable as collection sizes increase.
• Missing-element searches are particularly expensive for large lists.
• Sets are useful for repeated membership checks, while lists remain appropriate when indexing, duplicates, or sequence order are required.
• Benchmark results should be interpreted in the context of the Python runtime and workload being tested.

---

Conclusion

Python sets generally provide faster membership checks than lists, particularly when working with large collections.

However, this doesn't mean sets should replace lists everywhere.

Lists and sets serve different purposes, and lookup performance is only one factor when choosing between them.

The important lesson is to choose data structures based on how your application uses them—and measure performance when the difference matters.

---

# Import timeit for benchmarking execution time
import timeit

# Import matplotlib for visualizing benchmark results
import matplotlib.pyplot as plt


# -----------------------------------------
# Step 1: Configure the experiment
# -----------------------------------------

collection_sizes = [100, 1_000, 10_000, 100_000]

# Number of membership checks per benchmark
iterations = 10_000

# Number of benchmark repetitions
repeats = 5


# -----------------------------------------
# Step 2: Create sample collections
# -----------------------------------------

sample_list = list(range(1_000))
sample_set = set(sample_list)

target = 999

print("List lookup:", target in sample_list)
print("Set lookup:", target in sample_set)

print("\nList size:", len(sample_list))
print("Set size:", len(sample_set))


# -----------------------------------------
# Step 3: Define the benchmark function
# -----------------------------------------

def benchmark_lookup(collection, target):
    """Measure membership-check execution time."""

    # Define the membership operation
    def lookup():
        return target in collection

    # Repeat the benchmark multiple times
    timings = timeit.repeat(
        lookup,
        number=iterations,
        repeat=repeats,
    )

    # Select the fastest observed repetition
    best_time = min(timings)

    # Convert seconds per lookup into microseconds
    return (best_time / iterations) * 1_000_000


# -----------------------------------------
# Step 4: Benchmark existing elements
# -----------------------------------------

existing_results = []

for size in collection_sizes:
    # Create collections containing identical values
    numbers_list = list(range(size))
    numbers_set = set(numbers_list)

    # Search for the final element
    target = size - 1

    list_time = benchmark_lookup(numbers_list, target)
    set_time = benchmark_lookup(numbers_set, target)

    # Calculate the relative speed difference
    speedup = list_time / set_time

    existing_results.append(
        (size, list_time, set_time, speedup)
    )


# -----------------------------------------
# Step 5: Benchmark missing elements
# -----------------------------------------

missing_results = []

for size in collection_sizes:
    # Create collections containing identical values
    numbers_list = list(range(size))
    numbers_set = set(numbers_list)

    # Search for an element that doesn't exist
    target = -1

    list_time = benchmark_lookup(numbers_list, target)
    set_time = benchmark_lookup(numbers_set, target)

    # Calculate the relative speed difference
    speedup = list_time / set_time

    missing_results.append(
        (size, list_time, set_time, speedup)
    )


# -----------------------------------------
# Step 6: Display benchmark results
# -----------------------------------------

print("\nLIST VS SET LOOKUP — BENCHMARK RESULTS\n")

print(
    f"{'Size':>10} "
    f"{'Scenario':>12} "
    f"{'List (µs)':>15} "
    f"{'Set (µs)':>15} "
    f"{'Speedup':>12}"
)

print("-" * 70)

for scenario, results in [
    ("Existing", existing_results),
    ("Missing", missing_results),
]:
    for size, list_time, set_time, speedup in results:
        print(
            f"{size:>10,} "
            f"{scenario:>12} "
            f"{list_time:>15.4f} "
            f"{set_time:>15.4f} "
            f"{speedup:>11.2f}x"
        )


# -----------------------------------------
# Step 7: Visualize lookup performance
# -----------------------------------------

# Extract collection sizes and timings
sizes = [result[0] for result in existing_results]

list_times = [result[1] for result in existing_results]
set_times = [result[2] for result in existing_results]

# Create the performance comparison chart
plt.figure(figsize=(9, 5))

plt.plot(
    sizes,
    list_times,
    marker="o",
    label="List Lookup",
)

plt.plot(
    sizes,
    set_times,
    marker="s",
    label="Set Lookup",
)

# Configure the chart
plt.xscale("log")
plt.yscale("log")

plt.xlabel("Collection Size")
plt.ylabel("Lookup Time (µs)")

plt.title("List vs Set — Existing Element Lookup")

plt.legend()
plt.grid(True, alpha=0.3)

plt.tight_layout()
plt.show()