Optimizing Code: Algorithms and Data Structures

The Practical Impact of Algorithmic Complexity

Before optimizing, you must understand how an algorithm's performance scales with the size of its input. This is described by Big O notation. You don't need a formal computer science degree to use this concept effectively. Think of it simply as "how your code slows as your data grows."

Let's make this tangible. If your input data suddenly becomes 1,000 times larger:

• O(1) (Constant time): No change in execution time. (e.g., dictionary lookup by key)
• O(log n) (Logarithmic time): About 10 times slower. (e.g., binary search on a sorted list)
• O(n) (Linear time): About 1,000 times slower. (e.g., iterating through a list once)
• O(n log n) (Linearithmic time): About 10,000 times slower. (e.g., efficient sorting algorithms)
• O(n²) (Quadratic time): A staggering 1,000,000 times slower! (e.g., a loop inside another loop over the same data)

The takeaway is clear: moving an algorithm from O(n²) to O(n) is not a minor tweak; it's a fundamental change that determines whether your application can handle real-world data loads.

Choosing the Right Data Structure

The most common way to achieve these algorithmic improvements is by choosing the correct data structure for the job. Let's explore the performance trade-offs of Python's built-in containers.

The Classic Mistake: list vs. set for Membership Testing

In the previous lesson's exercise, you profiled a function that used a list to find unique items. The profiler likely showed that the line if item not in my_list: was the bottleneck. This is because checking for an item's existence in a list is an O(n) operation. Python has to scan the list from the beginning until it finds a match. When you do this inside a loop that also runs N times, you get O(n²) complexity.

A set, however, is implemented as a hash table. Membership testing (item in my_set) is an O(1) operation on average. The difference is dramatic.

Here is a practical example of refactoring the kind of code you saw in the last exercise:

# Assume `all_records` is a list of 10,000 dictionaries like {'email': '...', ...}




# ❌ BAD: O(n²) complexity
def find_unique_emails_list(records):
    unique_emails = []
    for record in records:



        # This 'in' check is O(k), where k is the current size of unique_emails.
        # Over the whole loop, this averages to O(n), leading to O(n²) overall.
        if record['email'] not in unique_emails:
            unique_emails.append(record['email'])
    return unique_emails




# ✅ GOOD: O(n) complexity
def find_unique_emails_set(records):



    # A set comprehension iterates through records once.
    # Adding to a set is O(1) on average.
    return {record['email'] for record in records}




# Or, if you need a list as the final output:
def find_unique_emails_set_to_list(records):
    return list({record['email'] for record in records})

For 10,000 records, the set-based version will be thousands of times faster than the list-based version. This is the single most common and impactful optimization for developers coming from languages where this distinction is less pronounced.

Queues: list vs. collections.deque

Another common bottleneck is using a list as a queue, where you frequently add or remove items from the beginning.

• my_list.pop(0) is O(n) because all subsequent elements must be shifted left.
• my_list.insert(0, item) is also O(n) for the same reason.

If you find yourself doing this in a performance-critical loop, you should use collections.deque (double-ended queue).

from collections import deque




# `deque` is designed for fast appends and pops from both ends.
queue = deque([1, 2, 3, 4])




# O(1) operation
queue.popleft()  # Returns 1, queue is now deque([2, 3, 4])




# O(1) operation
queue.appendleft(0) # queue is now deque([0, 2, 3, 4])

Refer back to the time complexity cheat sheet (LINK) and compare the List and Double-Ended Queue sections to see the performance differences for these operations.

Algorithmic Improvements in Practice

Choosing the right data structure is a form of algorithmic improvement. Let's look at other common patterns where changing the approach yields huge gains.

Avoiding Nested Loops with Lookups

This pattern is a direct extension of the list vs. set problem. If you find yourself writing nested loops to find common elements between two collections, you can almost always replace the inner loop with a fast lookup in a set or dict.

Let's review this pattern from the "Python Performance Optimization" guide.

Here’s the core idea:

list1 = [...] # 1,000 items
list2 = [...] # 1,000 items




# ❌ BAD: O(n*m) complexity. For 1000 items each, this is 1,000,000 comparisons.
def find_common_bad(list1, list2):
    common = []
    for item1 in list1:
        for item2 in list2:
            if item1 == item2:
                common.append(item1)
    return common




# ✅ GOOD: O(n+m) complexity. For 1000 items each, this is ~2000 operations.
def find_common_good(list1, list2):
    set2 = set(list2) # O(m) operation



    # O(n) operations, each with an O(1) lookup
    return [item1 for item1 in list1 if item1 in set2]




# ✅ EVEN BETTER & more Pythonic: O(n+m)
def find_common_best(list1, list2):



    # This does the same thing but is more declarative
    return list(set(list1) & set(list2))

String Concatenation in a Loop

A less obvious O(n²) trap is building a string using the += operator in a loop. Strings in Python are immutable, so each += operation creates a new string and copies the contents of the old string and the new suffix.

The correct, O(n) approach is to append the parts to a list and then use "".join() at the end. The join method calculates the final size, allocates memory once, and copies each part into it.

words = ["Python", "is", "fast", "if", "you", "use", "it", "right"]




# ❌ BAD: O(n²)
def join_words_bad(word_list):
    sentence = ""
    for word in word_list:
        sentence += word + " "
    return sentence




# ✅ GOOD: O(n)
def join_words_good(word_list):
    parts = [word + " " for word in word_list]
    return "".join(parts)

For a large number of words, the join method will be orders of magnitude faster.

Exercise: Refactor for Performance

You are given a script that analyzes a log file. The log is provided as a list of strings, where each line contains a timestamp, an IP address, and a message. The script's goal is to find all IP addresses that appear more than N times.

The current implementation is naive and slow. Your task is to refactor it using the principles you've learned.

Original Slow Script:

# performance_exercise.py

def find_frequent_ips_slow(log_lines, min_count):
    """
    Finds IPs that appear more than min_count times.
    This version is deliberately slow.
    """



    # 1. Get unique IPs (inefficiently)
    ips = [line.split()[1] for line in log_lines]
    unique_ips = []
    for ip in ips:
        if ip not in unique_ips:
            unique_ips.append(ip)




    # 2. Count each unique IP (inefficiently)
    frequent_ips = []
    for ip in unique_ips:
        count = 0
        for line in log_lines:
            if line.split()[1] == ip:
                count += 1
        
        if count > min_count:
            frequent_ips.append(ip)
    
    return frequent_ips




# ---- Setup ----
import random

def generate_log_data(num_lines):
    """Generates fake log data."""
    ips = [f"192.168.1.{random.randint(1, 20)}" for _ in range(num_lines)]
    lines = []
    for i, ip in enumerate(ips):
        lines.append(f"2023-10-27T10:00:{i:02d} {ip} User logged in")
    return lines

if __name__ == "__main__":
    import timeit
    
    log_data = generate_log_data(1000)
    



    # Measure the slow version
    slow_time = timeit.timeit(
        "find_frequent_ips_slow(log_data, 50)",
        globals=globals(),
        number=10
    )
    print(f"Slow version took: {slow_time:.4f} seconds")




    # Your new function will be tested here

Your Task:

1. Identify the bottlenecks. Look at the find_frequent_ips_slow function. Where are the O(n²) or otherwise inefficient operations?
2. Write find_frequent_ips_fast: Create a new, optimized version of the function.
   • Hint: How can you count all IP addresses in a single pass? What data structure is designed for counting things? (Look ahead to collections.Counter or implement it with a defaultdict).
3. Measure the improvement: Add code to your script to time your new find_frequent_ips_fast function using timeit and print the result. Compare it to the slow version.

A good solution will replace both inefficient loops with a single pass over the data, likely using a dictionary-like object to store counts.

Conclusion

You have now moved from simply finding performance issues to understanding the most powerful way to fix them. Algorithmic and data structure optimizations are the bedrock of high-performance Python.

Key Takeaways:

• Complexity Matters: An algorithm's Big O complexity is the primary determinant of its performance on large datasets. Your goal is to avoid O(n²) and favor O(n) or better.
• Use the Right Tool for the Job:
  • Use set for fast O(1) membership testing.
  • Use dict for fast O(1) key-based lookups and mappings.
  • Use collections.deque for fast O(1) appends and pops from both ends of a sequence.
• Refactor Inefficient Patterns: Actively look for and eliminate anti-patterns like membership testing in a list inside a loop, or building strings with += in a loop.

What's Next?

While algorithmic changes give the biggest wins, sometimes you can't change the algorithm. The work it does might be inherently expensive. In the next lesson, we will cover what to do in these situations. You'll learn how to use caching and memoization with functools.lru_cache to avoid re-computing expensive, pure function calls, providing another powerful tool for your optimization toolkit.