如何在Pandas DataFrame中高效迭代满足条件的行子集？

Hey David, great question—scaling this kind of subset detection to hundreds of thousands of rows definitely requires ditching slow brute-force logic and leaning into optimized pandas operations or compiled code. Let’s walk through some practical, faster approaches tailored to your problem:

The biggest speed killer is usually brute-forcing all possible subsets (which has an O(2ⁿ) time complexity per group). Instead, target the most common scenarios first:

a. Pairwise Complementary Values (Most Common Case) #

If your zero-sum subsets are mostly pairs of values like a and -a, use a hash map to quickly match complements. This runs in O(n) time per group:

import pandas as pd
from collections import defaultdict

def process_pair_group(group):
    value_indices = defaultdict(list)
    new_ids = [None] * len(group)
    suffix = 1

    for idx, val in enumerate(group['value']):
        if new_ids[idx] is not None:
            continue  # Skip already tagged rows
        complement = -val
        if complement in value_indices:
            # Tag all matching indices with the same new ID
            new_id = f"{group.name}_{suffix}"
            for match_idx in value_indices[complement]:
                new_ids[match_idx] = new_id
            new_ids[idx] = new_id
            suffix += 1
        value_indices[val].append(idx)
    
    group['new_id'] = new_ids
    return group

# Apply to groups with optimized groupby logic
df = df.groupby('ID', group_keys=False).apply(process_pair_group)

b. Larger Subsets (3+ Values) #

If you need to detect subsets of 3+ values that sum to zero, use a sorted two-pointer approach instead of brute force. This drops the complexity to O(n²) per group:

def process_large_subset_group(group):
    # Sort values while preserving original indices
    sorted_vals = sorted(zip(group['value'], group.index), key=lambda x: x[0])
    n = len(sorted_vals)
    new_ids = {idx: None for idx in group.index}
    suffix = 1

    for i in range(n):
        val_i, idx_i = sorted_vals[i]
        if new_ids[idx_i] is not None:
            continue
        target = -val_i
        left, right = i + 1, n - 1
        
        while left < right:
            val_left, idx_left = sorted_vals[left]
            val_right, idx_right = sorted_vals[right]
            current_sum = val_left + val_right
            
            if current_sum == target:
                # Tag all three (or more) matching rows
                new_id = f"{group.name}_{suffix}"
                new_ids[idx_i] = new_id
                new_ids[idx_left] = new_id
                new_ids[idx_right] = new_id
                # Move pointers to find additional matches for the same target
                left += 1
                right -= 1
            elif current_sum < target:
                left += 1
            else:
                right -= 1
        if new_ids[idx_i] is not None:
            suffix += 1
    
    group['new_id'] = group.index.map(new_ids)
    return group

df = df.groupby('ID', group_keys=False).apply(process_large_subset_group)

For pairwise cases, you can eliminate Python loops entirely using pandas built-in vectorized functions—this is usually the fastest option for large datasets:

def vectorized_pair_marking(df):
    # Flag rows where a complement exists in the same ID group
    df['has_complement'] = df.groupby('ID')['value'].transform(lambda x: x.isin(-x))
    
    # Create a temporary group ID for each (ID, absolute value) pair
    df['temp_group'] = df.groupby(['ID', df['value'].abs()]).ngroup()
    
    # Generate the final new_id
    df['new_id'] = df['ID'].astype(str) + "_" + (df['temp_group'] + 1).astype(str)
    
    # Clear new_id for rows without a complement
    df.loc[~df['has_complement'], 'new_id'] = None
    
    return df.drop(['has_complement', 'temp_group'], axis=1)

df = vectorized_pair_marking(df)

If you must use loops (for complex subset logic), compile your function with Numba to convert Python loops to machine code—this can speed up loops by 10-100x:

from numba import jit

@jit(nopython=True)
def numba_find_zero_sum_pairs(values):
    n = len(values)
    new_id_nums = [-1] * n  # -1 = unmarked
    suffix = 1
    
    for i in range(n):
        if new_id_nums[i] != -1:
            continue
        target = -values[i]
        for j in range(i + 1, n):
            if new_id_nums[j] == -1 and values[j] == target:
                new_id_nums[i] = suffix
                new_id_nums[j] = suffix
        if new_id_nums[i] != -1:
            suffix += 1
    return new_id_nums

def process_group_numba(group):
    values = group['value'].to_numpy()
    new_id_nums = numba_find_zero_sum_pairs(values)
    # Map numeric suffixes to the final new_id format
    group['new_id'] = [f"{group.name}_{num}" if num != -1 else None for num in new_id_nums]
    return group

df = df.groupby('ID', group_keys=False).apply(process_group_numba)

Pre-filter groups that can’t possibly have zero-sum subsets to avoid wasting processing time:

# Calculate min/max per ID to check if zero-sum is possible
group_stats = df.groupby('ID')['value'].agg(['min', 'max'])
# Only keep IDs with both positive and negative values
valid_ids = group_stats[(group_stats['min'] < 0) & (group_stats['max'] > 0)].index

# Initialize new_id to None for all rows
df['new_id'] = None
# Only process valid IDs
df.loc[df['ID'].isin(valid_ids), 'new_id'] = (
    df.loc[df['ID'].isin(valid_ids)]
    .groupby('ID', group_keys=False)
    .apply(process_pair_group)['new_id']
)

Which approach you pick depends on your specific subset requirements (pairwise vs larger subsets) and data distribution. For most real-world cases, the vectorized pandas method or Numba-accelerated loops will give you the biggest speedup on hundreds of thousands of rows.

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