python - 创建多个区间数据并集的快速算法

Question

我有一个非常简单的问题和数据结构，但数量如此之大，我需要找到一种有效的方法。

假设我有一个对象，它有一个间隔属性。 例如:

        `start      stop`
obj1      5          10
obj2      8          12
obj3      11         14
obj4      13         20
obj5      22         25
obj6      24         30
obj7      33         37
obj8      36         40

我想把它合并，让重叠的区间成为一个对象。所以，这个例子的结果会变成

         start        stop
objA        5          20
objB       22          30
objC       33          40

我正在为此使用 python。请注意，我有数千条此类数据。

Answer 1

df['Startpoint'] = df['stop`'].shift() < df['`start'] # Begin of interval
df['Endpoint'] = df['Startpoint'].shift(-1) # End of interval
df.loc['obj1', 'Startpoint'] = True # First line is startpoint
df['Endpoint'].fillna(True, inplace=True) # Last line is endpoint

df2 = df[df[['Startpoint', 'Endpoint']].any(axis=1)]
df2['`start'] = df2['`start'].shift() 
df2.loc[df2['Endpoint'], ['`start', 'stop`']]

  #            `start  stop`
  #  obj4     5.0     20
  #  obj6    22.0     30
  #  obj8    33.0     40

找到区间的所有开始和结束，只保留这些行，然后将起始值移动一行，以便每个区间的值都在同一行。

这都是 Pandas ，所以我相信它应该相当快。