Python嵌套循环替代方案：大规模用户组重叠时间计算

问题背景 #

我开发了如下Python代码用于检测三人组的同时在线重叠时间，但当需要计算约10人规模的用户组重叠时间时，嵌套循环的实现方式已不实用。请提供无需循环、具备可扩展性的替代方案。原代码如下：

import pandas as pd
from itertools import combinations

data = {
    'User': ['Esther','Jonh', 'Ann', 'Alex', 'Jonh', 'Alex', 'Ann', 'Beatrix'],
    'InitialTime': ['01/01/2023  00:00:00','01/01/2023  00:00:00', '01/01/2023  00:00:05', '01/01/2023  00:00:07', '01/01/2023  00:00:12', '01/01/2023  00:00:14', '01/01/2023  00:00:15', '01/01/2023  00:00:16'],
    'FinalTime': ['01/01/2023  00:10:00','01/01/2023  00:00:10', '01/01/2023  00:00:12', '01/01/2023  00:00:12','01/01/2023  00:00:16', '01/01/2023  00:00:16', '01/01/2023  00:00:17', '01/01/2023  00:00:17']
}
df=pd.DataFrame(data)

def calculate_overlapped_time(df):
    df['InitialTime'] = pd.to_datetime(df['InitialTime'], format='%d/%m/%Y %H:%M:%S')
    df['FinalTime'] = pd.to_datetime(df['FinalTime'], format='%d/%m/%Y %H:%M:%S')

    overlapped_time = {}

    for i, row_i in df.iterrows():
        for j, row_j in df.iterrows():
            for k, row_k in df.iterrows():
                if i != j and i != k and j != k:
                    initial_time = max(row_i['InitialTime'], row_j['InitialTime'], row_k['InitialTime'])
                    final_time = min(row_i['FinalTime'], row_j['FinalTime'], row_k['FinalTime'])
                    superposicion = max(0, (final_time - initial_time).total_seconds())

                    clave = f"{row_i['User']}-{row_j['User']}-{row_k['User']}"
                    if clave not in overlapped_time:
                        overlapped_time[clave] = 0
                    overlapped_time[clave] += superposicion

    results = pd.DataFrame(list(overlapped_time.items()), columns=['Group', 'OverlappingTime'])
    results['OverlappingTime'] = results['OverlappingTime'].astype(int)

    return results

results_df = calculate_overlapped_time(df)

原代码的问题 #

• 效率极低：三重嵌套循环的时间复杂度为O(n³)（n为记录条数），用户数和记录数增加时计算量会爆炸式增长。
• 重复计算：同一组用户的不同排列（如Esther-Jonh-Ann和Jonh-Esther-Ann）会被当成不同组重复统计，结果冗余且错误。
• 扩展性差：计算4人组、5人组重叠时间时需增加嵌套循环，代码维护成本极高。

可扩展的解决方案：事件驱动法 #

核心思路是通过时间事件点追踪在线用户变化，在每个时间区间内统计当前在线用户的所有k人组合（k为目标组规模），并累加区间时长到对应组的总重叠时间。该方法时间复杂度远低于嵌套循环，支持任意规模用户组计算。

实现代码 #

import pandas as pd
from itertools import combinations
from collections import defaultdict

def calculate_group_overlap(df, group_size=3):
    # 转换时间格式
    df['InitialTime'] = pd.to_datetime(df['InitialTime'], format='%d/%m/%Y %H:%M:%S')
    df['FinalTime'] = pd.to_datetime(df['FinalTime'], format='%d/%m/%Y %H:%M:%S')
    
    # 生成事件列表：(时间, 类型, 用户)，1为上线，-1为下线
    events = []
    for _, row in df.iterrows():
        events.append((row['InitialTime'], 1, row['User']))
        events.append((row['FinalTime'], -1, row['User']))
    
    # 排序事件：时间升序，下线事件优先于同时间的上线事件（避免重复统计）
    events.sort(key=lambda x: (x[0], x[1]))
    
    current_online = set()
    prev_time = None
    overlap_counts = defaultdict(int)
    
    for event_time, event_type, user in events:
        if prev_time is not None and event_time > prev_time:
            # 计算当前时间区间的时长（秒）
            duration = (event_time - prev_time).total_seconds()
            if duration <= 0:
                prev_time = event_time
                continue
            
            # 在线用户数达标时，生成所有组合并累加时长
            if len(current_online) >= group_size:
                for group in combinations(sorted(current_online), group_size):
                    group_key = '-'.join(group)
                    overlap_counts[group_key] += duration
        
        # 更新当前在线用户集合
        if event_type == 1:
            current_online.add(user)
        else:
            if user in current_online:
                current_online.remove(user)
        
        prev_time = event_time
    
    # 格式化结果
    results_df = pd.DataFrame(
        overlap_counts.items(),
        columns=['Group', 'OverlappingTime']
    )
    results_df['OverlappingTime'] = results_df['OverlappingTime'].astype(int)
    return results_df

# 测试使用
data = {
    'User': ['Esther','Jonh', 'Ann', 'Alex', 'Jonh', 'Alex', 'Ann', 'Beatrix'],
    'InitialTime': ['01/01/2023  00:00:00','01/01/2023  00:00:00', '01/01/2023  00:00:05', '01/01/2023  00:00:07', '01/01/2023  00:00:12', '01/01/2023  00:00:14', '01/01/2023  00:00:15', '01/01/2023  00:00:16'],
    'FinalTime': ['01/01/2023  00:10:00','01/01/2023  00:00:10', '01/01/2023  00:00:12', '01/01/2023  00:00:12','01/01/2023  00:00:16', '01/01/2023  00:00:16', '01/01/2023  00:00:17', '01/01/2023  00:00:17']
}
df = pd.DataFrame(data)

# 计算三人组重叠时间
results_3group = calculate_group_overlap(df, group_size=3)
print(results_3group)

# 计算四人组只需修改参数
# results_4group = calculate_group_overlap(df, group_size=4)

方案优势 #

• 高效可扩展：时间复杂度为O(n log n + m*C(g, k))（n为记录数，m为事件区间数，g为目标组规模），10人组计算量仍可控。
• 无重复统计：通过sorted(current_online)生成有序组键，同一用户组的不同排列只会被统计一次。
• 灵活适配：仅需修改group_size参数，即可计算任意规模的用户组重叠时间，无需改动核心逻辑。

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