python - 将日期范围与 Python 日期列表中的索引匹配的快速方法

Question

我需要选择不超过interval几天前的最早日期的索引date1（使用 index i1）。我有一个排序列表dates，这是我正在尝试做的片段：

for i1 in mylist:
    date1 = dates[i1]
    i0 = sum(1 for d in dates if date1 - d > timedelta(days = interval))
    # do some other stuff with this

我发现的那条线i0似乎是这个循环的瓶颈，因为如果我把它改成i0 = max(0, i1 - 30)（它只是忽略丢失的日期），它的工作速度大约快 100 倍。

有没有办法加快速度？我觉得应该有一种方法可以使用列表已排序的事实并避免进行所有比较。

PS：我的第一次尝试是：

i0 = len([d for d in dates if date1 - d > timedelta(days = interval)])

这甚至更慢。

score 1 · Accepted Answer

我需要选择不超过intervaldate1 前几天的最早日期的索引（使用 index i1）。我有一个排序列表dates

使用二分查找（O(log n)时间复杂度）：

import bisect

i = bisect.bisect_left(dates, dates[i1]-timedelta(days=interval))

Paraphrasingbisect的文档：返回值i使得切片中的所有日期都早于( )天，并且切片中的所有日期dates[:i]都小于或正好( )天前。>intervaldate[i1]dates[i:]<=intervaldates[i1]

1 回答 1