Pandas实现最高值优先的无重叠datetime区间拆分优化方案

数据场景 #

现有pandas DataFrame，每行存储一组带起始时间、结束时间、关联值的datetime区间，典型输入样例如下：

id   start          end            value
1    08:00:00.000   12:00:00.000   5
2    09:00:00.000   10:00:00.000   6
2    10:00:00.000   14:00:00.000   4
1    12:00:00.000   15:00:00.000   3

期望输出 #

生成连续无重叠的时间区间序列，重叠时段优先保留关联值最高的区间记录，结果样例如下：

id   start          end            value 
1    08:00:00.000   09:00:00.000   5
2    09:00:00.000   10:00:00.000   6
1    10:00:00.000   12:00:00.000   5
2    12:00:00.000   14:00:00.000   4
1    14:00:00.000   15:00:00.000   3

优化方向 #

当前嵌套循环逐行识别重叠、切分区间的方案性能较差，计划替换为向量化逻辑：

• 提取所有区间的首尾时间点作为全局切分边界
• 基于边界将全量时间轴切分为无重叠的原子小区间
• 逐段匹配覆盖该小区间的原始区间，筛选关联值最高的记录作为最终输出

现有循环实现代码 #

done = True

while done:
    done = False
    df_copy = df
    for i, row in df.iterrows():
        row_interval = pd.Interval(row.start, row.end)
        if done:
            break
        for j, row_copy in row_copy.iterrows():
            row_copy_interval = pd.Interval(row_copy.start, row_copy.end)
            if i is not j and row_interval.overlaps(row_copy_interval):
                earliest_start = np.minimum(row.start, row_copy.start)
                latest_start = np.maximum(row.start, row_copy.start)
                earliest_end = np.minimum(row.end, row_copy.end)
                latest_end = np.maximum(row.end, row_copy.end)

                if row.value > row_copy.value:
                    value = row.value
                else:
                    value = row_copy.value

                if row_interval == pd.Interval(earliest_start, earliest_end):
                    df = df.append('value': row.value, 'start': earliest_start,'end': latest_start}, ignore_index=True)
                    df = df.append('value': value, 'start': latest_start,'end': earliest_end}, ignore_index=True)
                    df = df.append('value': row_copy.value, 'start': earliest_end,'end': latest_end}, ignore_index=True)
                elif row_interval == pd.Interval(earliest_start, latest_end):
                    # 其他重叠分支处理逻辑
                    ...
                elif row_interval == pd.Interval(latest_start, latest_end):
                    # 其他重叠分支处理逻辑
                    ...
                elif row_interval == pd.Interval(latest_start, earliest_end):
                    # 其他重叠分支处理逻辑
                    ...

                df = df.drop([i, j]).drop_duplicates()
                done = True
                break

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