python - python 列表的子集

Question

我需要找到 python 列表的子集，例如:

a = [[1,2,100],[1,3,2100],[2,3,200],[3,4,1600]]

假设每个元素的第一个元素代表 start_time，第二个元素代表 end_time，我的查询采用 (start, end) 形式。生成的子集应该是这样的，即子集的每个元素的开始时间和结束时间应该在开始和结束之间。

执行此操作的最快方法是什么(或者我应该在其中保存数据以获得更好的运行时间的任何结构)？

Answer 1

您可以使用范围树 来存储点。将 (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]