Python嵌套for循环性能优化求助：大字典匹配耗时过长

Hey there! Let's work through optimizing that slow nested loop code of yours. First, a quick heads-up: your original dictionary has string values (like ('jade') is just a string, not a set), so calling .union() would throw an error. I’ll assume you intended to use sets for the values since you’re merging them—fixing that first is critical.

The Core Problem with Your Original Code #

Your nested loops create an O(n²) time complexity, meaning if you have 1000 keys, you’re doing 1,000,000 comparisons. On top of that, you’re comparing every pair twice (e.g., key A vs B and B vs A) and running the relatively heavy SequenceMatcher on every single pair, which adds up fast for large datasets.

Let’s break down actionable optimizations:

1. Eliminate Redundant Pair Comparisons #

Instead of looping through all keys for every key, only compare each pair once (i < j). This cuts your total comparisons in half immediately.

from difflib import SequenceMatcher

# Fixed dictionary with set values
my_dict = {'110': {'jade'}, '2': {'amber'}, '111': {'harry'}}
key_list = list(my_dict.keys())
total_keys = len(key_list)

for i in range(total_keys):
    key1 = key_list[i]
    for j in range(i + 1, total_keys):
        key2 = key_list[j]
        if SequenceMatcher(None, key1, key2).ratio() > 0.5:
            # Merge sets for both keys (matches your original logic)
            my_dict[key1].update(my_dict[key2])
            my_dict[key2].update(my_dict[key1])

2. Add Fast Pre-Filters to Skip Impossible Matches #

SequenceMatcher does a lot of work under the hood. We can pre-check key properties to skip pairs that could never hit the 0.5 ratio threshold, avoiding the expensive similarity check entirely.

For example, if the length difference between two keys is more than half the length of the shorter key, their similarity ratio can’t exceed 0.5. We can use this to filter out pairs early:

from difflib import SequenceMatcher

my_dict = {'110': {'jade'}, '2': {'amber'}, '111': {'harry'}}
key_list = list(my_dict.keys())
# Precompute key lengths to avoid recalculating in loops
key_lengths = {key: len(key) for key in key_list}
total_keys = len(key_list)

for i in range(total_keys):
    key1 = key_list[i]
    len1 = key_lengths[key1]
    for j in range(i + 1, total_keys):
        key2 = key_list[j]
        len2 = key_lengths[key2]
        
        # Fast filter: skip if length difference is too large
        min_length = min(len1, len2)
        if abs(len1 - len2) > min_length * 0.5:
            continue
        
        # Only run SequenceMatcher on plausible pairs
        if SequenceMatcher(None, key1, key2).ratio() > 0.5:
            my_dict[key1].update(my_dict[key2])
            my_dict[key2].update(my_dict[key1])

3. Replace SequenceMatcher with a Faster Similarity Check #

If you don’t need the full sophistication of SequenceMatcher, a custom lightweight similarity function can speed things up. For example, checking the ratio of overlapping characters:

def fast_similarity(a: str, b: str) -> float:
    set_a = set(a)
    set_b = set(b)
    intersection = len(set_a & set_b)
    union = len(set_a | set_b)
    return intersection / union if union != 0 else 0.0

my_dict = {'110': {'jade'}, '2': {'amber'}, '111': {'harry'}}
key_list = list(my_dict.keys())
key_lengths = {key: len(key) for key in key_list}
total_keys = len(key_list)

for i in range(total_keys):
    key1 = key_list[i]
    len1 = key_lengths[key1]
    for j in range(i + 1, total_keys):
        key2 = key_list[j]
        len2 = key_lengths[key2]
        
        min_length = min(len1, len2)
        if abs(len1 - len2) > min_length * 0.5:
            continue
        
        if fast_similarity(key1, key2) > 0.5:
            my_dict[key1].update(my_dict[key2])
            my_dict[key2].update(my_dict[key1])

4. Parallelize for Large Datasets #

If you’re dealing with tens of thousands of keys, splitting the work across multiple CPU cores can help. Use Python’s multiprocessing module to process pairs in parallel:

from multiprocessing import Pool
from difflib import SequenceMatcher

def process_pair(pair):
    key1, key2, dict_copy = pair
    if SequenceMatcher(None, key1, key2).ratio() > 0.5:
        return (key1, dict_copy[key2]), (key2, dict_copy[key1])
    return None

# Prepare data
my_dict = {'110': {'jade'}, '2': {'amber'}, '111': {'harry'}}
key_list = list(my_dict.keys())
total_keys = len(key_list)
pairs = []
for i in range(total_keys):
    for j in range(i + 1, total_keys):
        pairs.append((key_list[i], key_list[j], my_dict.copy()))

# Run in parallel
with Pool() as pool:
    results = pool.map(process_pair, pairs)

# Apply results to the original dict
for result in results:
    if result:
        (k1, val1), (k2, val2) = result
        my_dict[k1].update(val1)
        my_dict[k2].update(val2)

Note: Parallelization has overhead, so it’s only worth it for very large datasets.

内容的提问来源于stack exchange，提问作者l0n3_w01f