如何高效计算基于车辆进出时间戳的停车场占用量？

问题背景 #

我有一份包含ENTRY DATE（进入时间）、EXIT DATE（离开时间）及TYPE（停车类型）的停车场交易数据集，需要计算每笔交易退出时的停车场实时占用量。当前采用遍历EXIT DATE逐行查询的方案，在数十万行数据规模下因O(n²)的时间复杂度导致运行效率极低。

示例数据集 #

import pandas as pd

# 示例数据
data = {'ENTRY DATE':['10/1/2022 12:00:09 AM',
                      '10/1/2022 12:01:49 AM',
                      '10/1/2022 12:02:54 AM',
                      '10/1/2022 12:12:30 AM',
                      '10/1/2022 12:15:24 AM'],
        'EXIT DATE': ['10/1/2022 12:22:20 AM',
                      '10/1/2022  12:06:13 AM',
                      '10/1/2022  12:22:19 AM',
                      '10/1/2022  12:23:35 AM',
                      '10/1/2022  12:22:32 AM'],
        'TYPE': ['Short term parking',
                 'Short term parking',
                 'Short term parking',
                 'Short term parking',
                 'Short term parking']
       }

# 创建DataFrame并转换时间格式
df = pd.DataFrame(data)
df['ENTRY DATE'] = pd.to_datetime(df['ENTRY DATE'])
df['EXIT DATE'] = pd.to_datetime(df['EXIT DATE'])

原低效实现 #

def get_occ(df):
    count_list = []
    for exit_date in df['EXIT DATE']:
        # 逐行查询，时间复杂度O(n²)
        count = df.query("@exit_date > `ENTRY DATE` & @exit_date <= `EXIT DATE`")['TYPE'].count()
        count_list.append(count)
    df['OCCUPANCY'] = count_list

期望输出 #

高效替代方案 #

核心原理 #

每笔交易退出时的占用量，等于在该退出时间点前进入停车场的车辆总数减去在该退出时间点前已经离开的车辆总数。利用numpy的二分查找功能可以快速完成这两个统计，整体时间复杂度为O(n log n)，适合大规模数据处理。

实现代码 #

import numpy as np

# 提取并排序所有进入、退出时间
sorted_entries = np.sort(df['ENTRY DATE'].values)
sorted_exits = np.sort(df['EXIT DATE'].values)

# 对每个退出时间，统计：
# 1. 进入时间早于该退出时间的车辆数（side='left'返回小于目标值的元素个数）
entry_counts = np.searchsorted(sorted_entries, df['EXIT DATE'], side='left')
# 2. 退出时间早于该退出时间的车辆数
exit_counts = np.searchsorted(sorted_exits, df['EXIT DATE'], side='left')

# 计算占用量
df['OCCUPANCY'] = entry_counts - exit_counts

代码解释 #

• np.sort()：对进入、退出时间数组排序，为二分查找做准备
• np.searchsorted()：通过二分查找快速定位目标时间在排序数组中的插入位置，该位置的数值即为小于目标时间的元素总数
• 最终占用量通过两个统计值的差值得到，完全匹配原查询的逻辑，但效率提升数个数量级

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