我需要找到一个 python 列表的子集,例如:
a = [[1,2,100],[1,3,2100],[2,3,200],[3,4,1600]]
假设每个元素的第一个元素代表 start_time,第二个元素是 end_time,我的查询格式为(开始,结束)。结果子集应该使得子集的每个元素的 start_time 和 end_time 应该在 start 和 end 之间。
最快的方法是什么(或者我应该保存数据以获得更好的运行时间的任何结构)?
我需要找到一个 python 列表的子集,例如:
a = [[1,2,100],[1,3,2100],[2,3,200],[3,4,1600]]
假设每个元素的第一个元素代表 start_time,第二个元素是 end_time,我的查询格式为(开始,结束)。结果子集应该使得子集的每个元素的 start_time 和 end_time 应该在 start 和 end 之间。
最快的方法是什么(或者我应该保存数据以获得更好的运行时间的任何结构)?
您可以使用范围树来存储点。将 (start_time, end_time) 对视为 (x, y) 坐标。然后查询 (start, end) 变成了在正方形 [start,end] x [start,end] 中找到点的问题。
二维范围树可以在 O(n log n) 时间内计算出来,对它们的查询在 O(log n) 时间内执行。
不幸的是,我不知道任何好的 Python 实现(可能Python Quadtree除外),所以你可能不得不自己动手。但是,它肯定会比任何线性搜索解决方案都快。
如果您不想使用或编写范围树,请考虑使用 NumPy 来进行更快的线性搜索:
arr = np.array(a)
xa, ya, val = arr.T
pts = (xa >= start) & (ya <= end)
print arr[pts]
>>> start, end = 0, 5
>>> result = [i for i in a if start <= i[0] and end >= i[1]]
>>> print result
... [[1, 2, 100], [1, 3, 2100], [2, 3, 200], [3, 4, 1600]]
>>> start, end = 2, 3
>>> result = [i for i in a if start <= i[0] and end >= i[1]]
>>> print result
... [[2, 3, 200]]
列表理解。=
如果您希望它不包含,请 删除。
使用bisect
模块演示的算法将为您提供最快的搜索时间,但我们必须创建一些排序索引。
您必须将开始时间和结束时间都存储在列表中,并带有列表中条目的索引a
:
starttimes = [(l[0], i) for i,l in enumerate(a)]
starttimes.sort()
endtimes = [(l[1], i) for i, l in enumerate(a)]
endtimes.sort()
bisect
然后基于bisect.bisect_left
and函数创建专门的bisect.bisect_right
函数:
def bisect_timeseries_start(starttimes, start):
while lo < hi:
mid = (lo+hi)//2
if starttimes[mid][0] < start: lo = mid+1
else: hi = mid
return starttimes[lo][1]
def bisect_timeseries_end(endtimes, end):
while lo < hi:
mid = (lo+hi)//2
if end < endtimes[mid][0]: hi = mid
else: lo = mid+1
return endtimes[lo][1]
现在您可以使用这些函数找到开始和结束索引:
startindex = bisect.bisect_timeseries_start(starttimes, start)
endindex = bisect.bisect_timeseries_end(endtimes, end)
返回匹配范围现在很容易:
startendrange = a[startindex:endindex]
每个搜索都有一个O(lg n)
成本,其中n
是列表的长度。a
将这些操作组合成一个封装时间序列列表和索引的类很容易。