如何在DataFrame中查找所有类别重叠的Epoch时间范围

我有一个大型DataFrame，包含一个多类别的分类列type，以及每个类别对应的多个epoch时间列number (epoch)。需要找出所有类别都存在重叠的epoch时间范围，但不同类别的epoch测量间隔不统一，无法一一对应。

我之前想过构建一个包含epoch列和各类别列的表格，为每个epoch创建一行，通过合并匹配最近的epoch来查找重叠区域，但这种方法效率极低。

示例DataFrame #

type  number (epoch)
0      0             500
1      0             510
2      0             520
3      0             530
4      0             540
5      0             550
6      0             560
7      0             570
8      0             720
9      0             730
10     0             740
11     0             750
12     0             760
13     0             770
14     0             780
15     0            1000
16     0            1010
17     0            1020
18     0            1030
19     1             450
20     1             470
21     1             490
22     1             510
23     1             530
24     1             550
25     1             570
26     1             590
27     1             610
28     1             630
29     1             650
30     1             670
31     1             690
32     1             710
33     1             730
34     1             750
35     1             770
36     1             790
37     1             810
38     1             830
39     1             850
40     1             870
41     1             890
42     1             910
43     1             930
44     1             950
45     1             970
46     1             990
47     1            1010
48     1            1030
49     1            1050
50     1            1070
51     2             520
52     2             530
53     2             540
54     2             730
55     2             740
56     2             750
57     2             760
58     2            1100
59     2            1110
60     2            1120
61     2            1130
62     2            1140
63     2            1150
64     2            1160
65     2            1170
66     2            1180

期望输出 #

overlap ranges  Time Difference
0        520-540               20
1        730-760               30

解决方案 #

核心思路 #

把每个类别的连续epoch转化为时间区间，再将区间的起点/终点转化为"加入/移除类别"的事件点。通过遍历排序后的事件点，动态跟踪当前覆盖的类别数量，当覆盖数量等于总类别数时，记录这段时间为所有类别重叠的区间。这种方法时间复杂度为O(N log N)，适合处理大型数据集。

代码实现 #

import pandas as pd

# 假设df为已加载的目标DataFrame
# df = pd.read_csv("your_data.csv")

# 1. 为每个类别生成连续epoch的时间区间
def generate_intervals(group):
    sorted_epochs = group['number (epoch)'].sort_values().values
    # 生成[当前epoch, 下一个epoch)的区间
    intervals = pd.DataFrame({
        'start': sorted_epochs[:-1],
        'end': sorted_epochs[1:],
        'type': group.name
    })
    return intervals

intervals_df = df.groupby('type').apply(generate_intervals).reset_index(drop=True)

# 2. 生成事件点：起点标记为+1（添加类别），终点标记为-1（移除类别）
events = []
for _, row in intervals_df.iterrows():
    events.append((row['start'], 1, row['type']))
    events.append((row['end'], -1, row['type']))

# 按时间排序事件点
events.sort(key=lambda x: x[0])

# 3. 遍历事件点，跟踪重叠区间
total_types = df['type'].nunique()
current_covered = set()
prev_time = None
overlap_list = []

for time, delta, typ in events:
    if prev_time is not None and time > prev_time:
        # 检查当前是否覆盖所有类别
        if len(current_covered) == total_types:
            overlap_list.append((prev_time, time))
    # 更新当前覆盖的类别集合
    if delta == 1:
        current_covered.add(typ)
    else:
        current_covered.discard(typ)
    prev_time = time

# 4. 整理为目标格式的结果DataFrame
result = pd.DataFrame([
    {'overlap ranges': f'{start}-{end}', 'Time Difference': end - start}
    for start, end in overlap_list
])

print(result)

代码说明 #

1. 生成区间：对每个类别，将连续的epoch转化为闭开区间[start, end)，代表该类别在这段时间内有数据覆盖。
2. 事件点转换：把区间的起点标记为"添加类别"，终点标记为"移除类别"，方便动态跟踪覆盖状态。
3. 跟踪重叠：排序事件点后，遍历过程中检查当前覆盖的类别数是否等于总类别数，满足条件则记录这段时间为重叠区间。
4. 结果格式化：将重叠区间转为要求的字符串格式，并计算时间差。

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