Python：按元组首元素分组其余元素的最快实现方法

Great question! Let's start with a quick example to make sure we're on the same page. Suppose you have an input list like this:

original_list = [(1, 'a'), (1, 'b'), (2, 'c'), (3, 'x', 'y'), (3, 'z')]

You want to turn it into:

[(1, ('a', 'b')), (2, ('c',)), (3, ('x', 'y', 'z'))]

The Fastest Approach: collections.defaultdict #

For most cases (especially when your input list isn't pre-sorted), using defaultdict from the collections module is the fastest method. It runs in O(n) linear time, and its underlying implementation is optimized in C, making it way more efficient than manual Python loops for grouping.

Here's the code:

from collections import defaultdict

def merge_matching_tuples(input_list):
    # Initialize a defaultdict to group values by the first tuple element
    group_dict = defaultdict(list)
    
    # Iterate through each tuple, splitting the first element (key) from the rest
    for key, *remaining_elements in input_list:
        group_dict[key].extend(remaining_elements)
    
    # Convert the grouped lists back into tuples and format the final result
    return [(key, tuple(values)) for key, values in group_dict.items()]

Why This Works So Well:

• defaultdict automatically handles key initialization (no need to check if a key exists before adding values).
• Extending lists and converting to tuples are fast operations.
• In Python 3.7+, defaultdict preserves the order of first occurrence of each key, which is usually what you want.

Alternative: itertools.groupby (Only if Pre-Sorted) #

If your input list is already sorted by the first element of the tuples, itertools.groupby can be a good option. However, if you need to sort the list first, this adds an O(n log n) overhead, making it slower than the defaultdict approach for unsorted data.

Here's how you'd use it:

from itertools import groupby

def merge_sorted_tuples(input_list):
    # Sort the list by the first tuple element (only needed if not already sorted)
    sorted_list = sorted(input_list, key=lambda x: x[0])
    
    result = []
    # Group tuples by their first element
    for key, group in groupby(sorted_list, key=lambda x: x[0]):
        merged_values = []
        for item in group:
            merged_values.extend(item[1:])
        result.append((key, tuple(merged_values)))
    return result

Performance Comparison #

• Unsorted input: defaultdict is faster (O(n) vs O(n log n) for groupby + sort).
• Sorted input: Both methods are roughly comparable in speed, but defaultdict still tends to have a slight edge in practice due to lower constant factors.

Test It Out! #

Let's run the defaultdict version with our example input:

original_list = [(1, 'a'), (1, 'b'), (2, 'c'), (3, 'x', 'y'), (3, 'z')]
print(merge_matching_tuples(original_list))
# Output: [(1, ('a', 'b')), (2, ('c',)), (3, ('x', 'y', 'z'))]

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