Эффективно найти перекрытие диапазонов даты и времени от 2-х фреймов данных - PullRequest
Новая
       33

Эффективно найти перекрытие диапазонов даты и времени от 2-х фреймов данных

0 голосов
/ 26 апреля 2018

Есть несколько вопросов относительно нахождения перекрытия в диапазонах дат или времени (, например, ).Я использовал их для решения своей проблемы, но в итоге я нашел чрезвычайно медленное (и вовсе не элегантное) решение моей проблемы.Я был бы очень признателен, если бы кто-то имел представление о том, как сделать это быстрее (и более элегантно):

Проблема:

IУ меня есть 2 кадра данных, df1 и df2, каждый из которых содержит 2 столбца, представляющих время начала и время окончания: 

>>> df1

        datetime_start        datetime_end
0  2016-09-11 06:00:00 2016-09-11 06:30:00
1  2016-09-11 07:00:00 2016-09-11 07:30:00
2  2016-09-11 07:30:00 2016-09-11 08:00:00
3  2016-09-11 08:00:00 2016-09-11 08:30:00
4  2016-09-11 08:30:00 2016-09-11 09:00:00
5  2016-09-11 09:00:00 2016-09-11 09:30:00
6  2016-09-11 09:30:00 2016-09-11 10:00:00
7  2016-09-11 10:30:00 2016-09-11 11:00:00
13 2016-09-11 14:00:00 2016-09-11 14:30:00
14 2016-09-11 14:30:00 2016-09-11 15:00:00
15 2016-09-11 15:00:00 2016-09-11 15:30:00
16 2016-09-11 15:30:00 2016-09-11 16:00:00
17 2016-09-11 16:00:00 2016-09-11 16:30:00
18 2016-09-11 16:30:00 2016-09-11 17:00:00
19 2016-09-11 17:00:00 2016-09-11 17:30:00

>>> df2

        datetime_start        datetime_end catg
4  2016-09-11 08:48:33 2016-09-11 09:41:53    a
6  2016-09-11 09:54:25 2016-09-11 10:00:50    a
8  2016-09-11 10:01:47 2016-09-11 10:04:55    b
10 2016-09-11 10:08:00 2016-09-11 10:08:11    b
12 2016-09-11 10:30:28 2016-09-11 10:30:28    b
14 2016-09-11 10:38:18 2016-09-11 10:38:18    a
18 2016-09-11 13:44:05 2016-09-11 13:44:05    a
20 2016-09-11 13:46:52 2016-09-11 14:11:41    d
23 2016-09-11 14:22:17 2016-09-11 14:33:40    b
25 2016-09-11 15:00:12 2016-09-11 15:02:55    b
27 2016-09-11 15:04:19 2016-09-11 15:06:36    b
29 2016-09-11 15:08:43 2016-09-11 15:31:29    d
31 2016-09-11 15:38:04 2016-09-11 16:09:24    a
33 2016-09-11 16:18:40 2016-09-11 16:44:32    b
35 2016-09-11 16:45:59 2016-09-11 16:59:01    b
37 2016-09-11 17:08:31 2016-09-11 17:12:23    b
39 2016-09-11 17:16:13 2016-09-11 17:16:33    c
41 2016-09-11 17:17:23 2016-09-11 17:20:00    b
45 2016-09-13 12:27:59 2016-09-13 12:34:21    a
47 2016-09-13 12:38:39 2016-09-13 12:38:45    a

Мне нужно найти, где находятся диапазоны в df2имеют перекрытие с диапазонами в df1, как долго это перекрытие (в секундах) и какое значение df2.catg это.Я хочу, чтобы длина этого перекрытия была вставлена ​​в столбец в df1 (этот столбец будет назван для catg, который он представляет).

Желаемый вывод : 

>>> df1
        datetime_start        datetime_end       a       b       d     c
0  2016-09-11 06:00:00 2016-09-11 06:30:00     0.0     0.0     0.0   0.0
1  2016-09-11 07:00:00 2016-09-11 07:30:00     0.0     0.0     0.0   0.0
2  2016-09-11 07:30:00 2016-09-11 08:00:00     0.0     0.0     0.0   0.0
3  2016-09-11 08:00:00 2016-09-11 08:30:00     0.0     0.0     0.0   0.0
4  2016-09-11 08:30:00 2016-09-11 09:00:00   687.0     0.0     0.0   0.0
5  2016-09-11 09:00:00 2016-09-11 09:30:00  1800.0     0.0     0.0   0.0
6  2016-09-11 09:30:00 2016-09-11 10:00:00  1048.0     0.0     0.0   0.0
7  2016-09-11 10:30:00 2016-09-11 11:00:00     0.0     0.0     0.0   0.0
13 2016-09-11 14:00:00 2016-09-11 14:30:00     0.0   463.0   701.0   0.0
14 2016-09-11 14:30:00 2016-09-11 15:00:00     0.0   220.0     0.0   0.0
15 2016-09-11 15:00:00 2016-09-11 15:30:00     0.0   300.0  1277.0   0.0
16 2016-09-11 15:30:00 2016-09-11 16:00:00  1316.0     0.0    89.0   0.0
17 2016-09-11 16:00:00 2016-09-11 16:30:00   564.0   680.0     0.0   0.0
18 2016-09-11 16:30:00 2016-09-11 17:00:00     0.0  1654.0     0.0   0.0
19 2016-09-11 17:00:00 2016-09-11 17:30:00     0.0   389.0     0.0  20.0

Смехотворно медленный способ сделать это:

Основываясь на этом красивом ответе , я достиг целей, которые хочу достичь, используя следующие трудные для пониманияcode: 

from collections import namedtuple
Range = namedtuple('Range', ['start', 'end'])

def overlap(row1, row2):
    r1 = Range(start=row1.datetime_start, end=row1.datetime_end)
    r2 = Range(start=row2.datetime_start, end=row2.datetime_end)
    latest_start = max(r1.start, r2.start)
    earliest_end = min(r1.end, r2.end)
    delta = (earliest_end - latest_start).total_seconds()
    overlap = max(0, delta)
    return overlap

for cat in df2.catg.unique().tolist():
    df1[cat] = 0

for idx1, row1 in df1.iterrows():
    for idx2, row2 in df2.iterrows():
        if overlap(row1, row2) > 0:
            df1.loc[idx1, row2.catg] += overlap(row1, row2)

Это работает, но очень медленно на больших фреймах данных, что в принципе его невозможно использовать.Если у кого-нибудь есть какие-либо идеи по ускорению этого процесса, я буду рад вашему вкладу.

Заранее спасибо, и дайте мне знать, если что-то неясно!

Настройка dataframe: 

import pandas as pd
from pandas import Timestamp

d1 = {'datetime_start': {0: Timestamp('2016-09-11 06:00:00'), 1: Timestamp('2016-09-11 07:00:00'), 2: Timestamp('2016-09-11 07:30:00'), 3: Timestamp('2016-09-11 08:00:00'), 4: Timestamp('2016-09-11 08:30:00'), 5: Timestamp('2016-09-11 09:00:00'), 6: Timestamp('2016-09-11 09:30:00'), 7: Timestamp('2016-09-11 10:30:00'), 13: Timestamp('2016-09-11 14:00:00'), 14: Timestamp('2016-09-11 14:30:00'), 15: Timestamp('2016-09-11 15:00:00'), 16: Timestamp('2016-09-11 15:30:00'), 17: Timestamp('2016-09-11 16:00:00'), 18: Timestamp('2016-09-11 16:30:00'), 19: Timestamp('2016-09-11 17:00:00')}, 'datetime_end': {0: Timestamp('2016-09-11 06:30:00'), 1: Timestamp('2016-09-11 07:30:00'), 2: Timestamp('2016-09-11 08:00:00'), 3: Timestamp('2016-09-11 08:30:00'), 4: Timestamp('2016-09-11 09:00:00'), 5: Timestamp('2016-09-11 09:30:00'), 6: Timestamp('2016-09-11 10:00:00'), 7: Timestamp('2016-09-11 11:00:00'), 13: Timestamp('2016-09-11 14:30:00'), 14: Timestamp('2016-09-11 15:00:00'), 15: Timestamp('2016-09-11 15:30:00'), 16: Timestamp('2016-09-11 16:00:00'), 17: Timestamp('2016-09-11 16:30:00'), 18: Timestamp('2016-09-11 17:00:00'), 19: Timestamp('2016-09-11 17:30:00')}}

d2 = {'datetime_start': {4: Timestamp('2016-09-11 08:48:33'), 6: Timestamp('2016-09-11 09:54:25'), 8: Timestamp('2016-09-11 10:01:47'), 10: Timestamp('2016-09-11 10:08:00'), 12: Timestamp('2016-09-11 10:30:28'), 14: Timestamp('2016-09-11 10:38:18'), 18: Timestamp('2016-09-11 13:44:05'), 20: Timestamp('2016-09-11 13:46:52'), 23: Timestamp('2016-09-11 14:22:17'), 25: Timestamp('2016-09-11 15:00:12'), 27: Timestamp('2016-09-11 15:04:19'), 29: Timestamp('2016-09-11 15:08:43'), 31: Timestamp('2016-09-11 15:38:04'), 33: Timestamp('2016-09-11 16:18:40'), 35: Timestamp('2016-09-11 16:45:59'), 37: Timestamp('2016-09-11 17:08:31'), 39: Timestamp('2016-09-11 17:16:13'), 41: Timestamp('2016-09-11 17:17:23'), 45: Timestamp('2016-09-13 12:27:59'), 47: Timestamp('2016-09-13 12:38:39')}, 'datetime_end': {4: Timestamp('2016-09-11 09:41:53'), 6: Timestamp('2016-09-11 10:00:50'), 8: Timestamp('2016-09-11 10:04:55'), 10: Timestamp('2016-09-11 10:08:11'), 12: Timestamp('2016-09-11 10:30:28'), 14: Timestamp('2016-09-11 10:38:18'), 18: Timestamp('2016-09-11 13:44:05'), 20: Timestamp('2016-09-11 14:11:41'), 23: Timestamp('2016-09-11 14:33:40'), 25: Timestamp('2016-09-11 15:02:55'), 27: Timestamp('2016-09-11 15:06:36'), 29: Timestamp('2016-09-11 15:31:29'), 31: Timestamp('2016-09-11 16:09:24'), 33: Timestamp('2016-09-11 16:44:32'), 35: Timestamp('2016-09-11 16:59:01'), 37: Timestamp('2016-09-11 17:12:23'), 39: Timestamp('2016-09-11 17:16:33'), 41: Timestamp('2016-09-11 17:20:00'), 45: Timestamp('2016-09-13 12:34:21'), 47: Timestamp('2016-09-13 12:38:45')}, 'catg': {4: 'a', 6: 'a', 8: 'b', 10: 'b', 12: 'b', 14: 'a', 18: 'a', 20: 'd', 23: 'b', 25: 'b', 27: 'b', 29: 'd', 31: 'a', 33: 'b', 35: 'b', 37: 'b', 39: 'c', 41: 'b', 45: 'a', 47: 'a'}}

df1 = pd.DataFrame(d1)
df2 = pd.DataFrame(d2)

Ответы [ 3 ]

0 голосов
/ 26 апреля 2018

На основании timeit тестов, по 100 выполнений в каждом, подход namedtuple в вопросе в среднем составлял 15.7314 секунд на моей машине, в среднем 1.4794 секунд при таком подходе: 

# determine the duration of the events in df2, in seconds
duration = (df2.datetime_end - df2.datetime_start).dt.seconds.values

# create a numpy array with one timestamp for each second 
# in which an event occurred
seconds_range = np.repeat(df2.datetime_start.values, duration) + \
                np.concatenate(map(np.arange, duration)) * pd.Timedelta('1S')

df1.merge(pd.DataFrame({'datetime_start':seconds_range,
                        'catg':np.repeat(df2.catg, duration)}). \
              groupby(['catg', pd.Grouper(key='datetime_start', freq='30min')]). \
              size(). \
              unstack(level=0). \
              reset_index(), 
          how="left")

#           datetime_end      datetime_start       a       b     c       d
# 0  2016-09-11 06:30:00 2016-09-11 06:00:00     NaN     NaN   NaN     NaN
# 1  2016-09-11 07:30:00 2016-09-11 07:00:00     NaN     NaN   NaN     NaN
# 2  2016-09-11 08:00:00 2016-09-11 07:30:00     NaN     NaN   NaN     NaN
# 3  2016-09-11 08:30:00 2016-09-11 08:00:00     NaN     NaN   NaN     NaN
# 4  2016-09-11 09:00:00 2016-09-11 08:30:00   687.0     NaN   NaN     NaN
# 5  2016-09-11 09:30:00 2016-09-11 09:00:00  1800.0     NaN   NaN     NaN
# 6  2016-09-11 10:00:00 2016-09-11 09:30:00  1048.0     NaN   NaN     NaN
# 7  2016-09-11 11:00:00 2016-09-11 10:30:00     NaN     NaN   NaN     NaN
# 8  2016-09-11 14:30:00 2016-09-11 14:00:00     NaN   463.0   NaN   701.0
# 9  2016-09-11 15:00:00 2016-09-11 14:30:00     NaN   220.0   NaN     NaN
# 10 2016-09-11 15:30:00 2016-09-11 15:00:00     NaN   300.0   NaN  1277.0
# 11 2016-09-11 16:00:00 2016-09-11 15:30:00  1316.0     NaN   NaN    89.0
# 12 2016-09-11 16:30:00 2016-09-11 16:00:00   564.0   680.0   NaN     NaN
# 13 2016-09-11 17:00:00 2016-09-11 16:30:00     NaN  1654.0   NaN     NaN
# 14 2016-09-11 17:30:00 2016-09-11 17:00:00     NaN   389.0  20.0     NaN
0 голосов
/ 26 апреля 2018

Вы должны увидеть значительное (~ 8x в моем тестировании) улучшение производительности через несколько изменений.Структура вашего кода остается прежней: 

def overlap(row1, row2):
    return max(0, (min(row1[0], row2[0]) - max(row1[1], row2[1])) / np.timedelta64(1, 's'))

df1 = df1.join(pd.DataFrame(dict.fromkeys(df2.catg.unique(), 0), index=df1.index))

for idx1, row1 in enumerate(df1.iloc[:, :2].values):
    for catg, row2 in zip(df2['catg'], df2.iloc[:, 1:3].values):
        df1.iat[idx1, df1.columns.get_loc(catg)] += overlap(row1, row2)

Вы можете получить дальнейшее объяснение с помощью numba или с помощью некоторого умного pandas материала, который скрывает всю вашу логику.

Объяснение

  1. Использовать df.itertuples вместо df.iterrows
  2. Использовать df.iat вместо df.loc
  3. Использовать numpy вместоиз pandas объектов времени
  4. Удалить создание именованного кортежа
  5. Удалить повторяющиеся вычисления перекрытия
  6. Улучшить алгоритм перекрытия

Результат 

          datetime_end      datetime_start     a     b   c     d
0  2016-09-11 06:30:00 2016-09-11 06:00:00     0     0   0     0
1  2016-09-11 07:30:00 2016-09-11 07:00:00     0     0   0     0
2  2016-09-11 08:00:00 2016-09-11 07:30:00     0     0   0     0
3  2016-09-11 08:30:00 2016-09-11 08:00:00     0     0   0     0
4  2016-09-11 09:00:00 2016-09-11 08:30:00   687     0   0     0
5  2016-09-11 09:30:00 2016-09-11 09:00:00  1800     0   0     0
6  2016-09-11 10:00:00 2016-09-11 09:30:00  1048     0   0     0
7  2016-09-11 11:00:00 2016-09-11 10:30:00     0     0   0     0
13 2016-09-11 14:30:00 2016-09-11 14:00:00     0   463   0   701
14 2016-09-11 15:00:00 2016-09-11 14:30:00     0   220   0     0
15 2016-09-11 15:30:00 2016-09-11 15:00:00     0   300   0  1277
16 2016-09-11 16:00:00 2016-09-11 15:30:00  1316     0   0    89
17 2016-09-11 16:30:00 2016-09-11 16:00:00   564   680   0     0
18 2016-09-11 17:00:00 2016-09-11 16:30:00     0  1654   0     0
19 2016-09-11 17:30:00 2016-09-11 17:00:00     0   389  20     0
0 голосов
/ 26 апреля 2018

Если предположить, что и df1, и df2 отсортированы в порядке возрастания по столбцу datetime_start (это выглядит так), то вам просто нужно пройти по каждой строке двух фреймов данных один раз, в результате чего O(n)время выполнения, а не текущее O(n^2) из-за парного сравнения строк.

Следующий код иллюстрирует идею.Ключевым моментом является использование итераторов it1 и it2 для указания текущей строки.Поскольку кадры данных отсортированы, если row1 уже позже, чем row2, мы уверены, что следующая строка в df1 позже, чем row2.Труднее объяснить словами, чем код: 

def main(df1, df2):
    for cat in df2.catg.unique().tolist():
        df1[cat] = 0
    it1 = df1.iterrows()
    it2 = df2.iterrows()
    idx1, row1 = next(it1)
    idx2, row2 = next(it2)
    while True:
        try:
            r1 = Range(start=row1.datetime_start, end=row1.datetime_end)
            r2 = Range(start=row2.datetime_start, end=row2.datetime_end)
            if r2.end < r1.start:
                # no overlap. r2 before r1. advance it2
                idx2, row2 = next(it2)
            elif r1.end < r2.start:
                # no overlap. r1 before r2. advance it1
                idx1, row1 = next(it1)
            else:
                # overlap. overlap(row1, row2) must > 0 
                df1.loc[idx1, row2.catg] += overlap(row1, row2)
                # determine whether to advance it1 or it2
                if r1.end < r2.end:
                    # advance it1
                    idx1, row1 = next(it1)
                else:
                    # advance it2
                    idx2, row2 = next(it2)
        except StopIteration:
            break

main(df1, df2)
...