4
\$\begingroup\$

I'm working with a pandas dataframe which describes the start and end time of visits. A toy example of the data could be as follows:

import pandas as pd
data = pd.DataFrame({"start": [pd.Timestamp("2020-01-01 01:23:45"), pd.Timestamp("2020-01-01 01:45:12")], "end": [pd.Timestamp("2020-01-01 02:23:00"), pd.Timestamp("2020-01-01 03:12:00")]})

I want to break down these visits into periods: from 01:00 to 02:00, there were two visitors, from 02:00 to 03:00, also two, and from 03:00 to 04:00, only one of the visitors was present. To achieve this, I'm generating bounds for my periods and generate a dataframe with overlaps:

periods = pd.DataFrame({"period_start": pd.date_range(start = "2020-01-01 01:00:00", end = "2020-01-01 03:00:00", freq = "1H"), "period_end": pd.date_range(start = "2020-01-01 02:00:00", end = "2020-01-01 04:00:00", freq = "1H")})

def has_overlap(A_start, A_end, B_start, B_end):
  latest_start = max(A_start, B_start)
  earliest_end = min(A_end, B_end)
  return latest_start <= earliest_end

periods_breakdown = pd.DataFrame()
for i in range(3):
  ps = periods.period_start[i]
  pe = periods.period_end[i]
  periods_breakdown["period" + str(i)] = data.apply(lambda row: has_overlap(row.start, row.end, ps, pe), axis = 1)

On the toy data, this code returns

  period0 period1 period2
0    True    True   False
1    True    True    True

The problem is that the actual data has 1M visits that I want to break down over 6000 periods, and the code runs for roughly 140 hours.

  1. Is there a better way to count visitors from this sort of data?
  2. Are there performance improvements to this code?
\$\endgroup\$
3
\$\begingroup\$

I think it is slow because your periods_breakdown is gigantic, and to fill each cell you have to compute its value. But what you compute is whether each individual visit overlapped with each other visit, which is overkill. If what you want is to know when there is two visits (or more) overlapping, but don't need to know which specific ones, you can simply count how many visits there are during each hour slot and you will know when there was an overlap because the count will be more than one.

Based on the data you provided :

import pandas as pd
data = pd.DataFrame({"start": [pd.Timestamp("2020-01-01 01:23:45"),
                               pd.Timestamp("2020-01-01 01:45:12")],
                     "end": [pd.Timestamp("2020-01-01 02:23:00"),
                             pd.Timestamp("2020-01-01 03:12:00")]})

NUMBER_OF_PERIODS = 6  # FIXME: use an upper bound
visitors_count_per_hour = [0] * NUMBER_OF_PERIODS

year_start = pd.Timestamp(year=2020, month=1, day=1, hour=0, minute=0, second=0, microsecond=0)
for visit_start, visit_end in zip(data["start"], data["end"]):
    print(f"there was a visit between {visit_start} and {visit_end}")
    start_hour = visit_start.floor("H")
    end_hour = visit_end.floor("H")
    print(f"  in hours, it spanned from {start_hour} to {end_hour} included")
    visit_hours = pd.date_range(start=start_hour, end=end_hour, freq="1H")
    offset = len(pd.date_range(start=year_start, end=start_hour))
    print(f"  it started at period n°{offset}")
    for i, visit_hour in enumerate(visit_hours):
        print(f"  - so we count one person at hour {visit_hour}")
        visitors_count_per_hour[i + offset] += 1

print(visitors_count_per_hour)

periods_breakdown = pd.DataFrame()
for hour_index, visitor_count in enumerate(visitors_count_per_hour):
    slot_hour = year_start + pd.Timedelta(hours=hour_index)
    periods_breakdown["period" + str(hour_index)] = [slot_hour] + \
                                                    ([True] if visitor_count > 1 else [False]) + \
                                                    [visitor_count]

print(periods_breakdown)

which outputs

there was a visit between 2020-01-01 01:23:45 and 2020-01-01 02:23:00
  in hours, it spanned from 2020-01-01 01:00:00 to 2020-01-01 02:00:00 included
  it started at period n°1
  - so we count one person at hour 2020-01-01 01:00:00
  - so we count one person at hour 2020-01-01 02:00:00
there was a visit between 2020-01-01 01:45:12 and 2020-01-01 03:12:00
  in hours, it spanned from 2020-01-01 01:00:00 to 2020-01-01 03:00:00 included
  it started at period n°1
  - so we count one person at hour 2020-01-01 01:00:00
  - so we count one person at hour 2020-01-01 02:00:00
  - so we count one person at hour 2020-01-01 03:00:00
[0, 2, 2, 1, 0, 0]
               period0              period1              period2              period3              period4              period5
0  2020-01-01 00:00:00  2020-01-01 01:00:00  2020-01-01 02:00:00  2020-01-01 03:00:00  2020-01-01 04:00:00  2020-01-01 05:00:00
1                False                 True                 True                False                False                False
2                    0                    2                    2                    1                    0                    0

My result is slightly different than yours because my period0 is 2020-01-01 00:00:00 while you started at 01:00:00.

Speaking of performance, your algorithm will fill N*M cells, N being the number of visits, M being the number of slots in your data. With the values you provided (N=1000000 and M=6000), it is not surpising it slow. My solution, by not comparing each visit with each other, only does roughly N+M computes, which is a whole algorithmic complexity class down.

I'm no expert of pandas, so there may a better way to write the code to do essentially the same thing. But if you want to have an even quicker program, maybe you can simplify your problem (find another algorithm) or make better use of pandas than me.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Thanks, I think this is part of the answer I needed. I don't think that performance is problematic only because of the N*M cells: if I would be filling 6 billion cells with zeros, that would be pretty quick, so part of the performance problems is definitely with the value calculations. Still, thanks for guiding me. \$\endgroup\$ – svavil May 29 at 11:33
0
\$\begingroup\$

As I worked more with these data, I realized that two problems were keeping me away from a decent performance:

  1. There is a big overhead with using pandas, and
  2. The data about visits is sparse, and I should make use of it

So, the same data can be calculated by starting with an np.zeros matrix of a corresponding size, and setting 1s within the range of each visit. Since the resulting data is purely numeric, it's better kept in a numpy array, not in a pandas dataframe. I also made use of floor and ceil functions for pd.Timestamp mentioned in Lenormju's answer to produce the following code:

range_start = min(data.start).floor("H")
range_end = max(data.end).ceil("H")
range_n = (range_end - range_start) // pd.Timedelta("1H")

period_breakdown = np.zeros([len(data.index), range_n])
for i, row in data.iterrows():
    start_offset = (row.start.floor("H") - range_start) // pd.Timedelta("1H")
    end_offset = (row.end.ceil("H") - range_start) // pd.Timedelta("1H")
    period_breakdown[i,start_offset:end_offset] = 1

which runs for 15 minutes on the same dataset.

\$\endgroup\$
2
  • \$\begingroup\$ it used to take 140 hours, is getting down to 0,25 hour sufficient ? \$\endgroup\$ – Lenormju May 31 at 6:40
  • \$\begingroup\$ @Lenormju yes, 0,25 hours is quite sufficient. \$\endgroup\$ – svavil May 31 at 7:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.