2

我正在使用优先级队列（heapq）datetime.datetime作为优先级。

如果我有要搜索的 startTime 和 endTime ，那么从这个列表中提取元素子集的最 Pythonic 方法是什么。（我无法更改原始列表，所以我必须创建一个新列表并返回，或者返回一个迭代器）

以下是我所拥有的示例：

>>> import heapq
>>> timeLine = []
>>> from datetime import datetime
>>> heapq.heappush(timeLine, (datetime.now(),'A'))
>>> heapq.heappush(timeLine, (datetime.now(),'B'))
>>> heapq.heappush(timeLine, (datetime.now(),'C'))
>>> timeLine
[(datetime.datetime(2013, 2, 8, 15, 25, 14, 720000), 'A'), (datetime.datetime(2013, 2, 8, 15, 25, 30, 575000), 'B'), (datetime.datetime(2013, 2, 8, 15, 25, 36, 959000), 'C')]

真正的应用程序列表是巨大的。

4

2 回答 2

1

堆不是执行此操作的理想结构；如果您坚持使用heapq的公共 API，堆将被更改并且对进一步的操作无用。@Anonymous 的解决方案可能有效，但（恕我直言）过于依赖实施细节。虽然这些是公开记录的，但我不确定您是否真的应该使用它们。

简单地对列表进行排序并进行两次二进制搜索是一种简单的方法来做你想做的事：

from bisect import bisect_left, bisect_right

def find_range(timeline, start, end):
    l = bisect_left(timeline, start)
    r = bisect_right(timeline, end)
    for i in xrange(l, r):
        yield timeline[i]

这种方法的唯一问题是，在最坏的情况下排序需要 O( n lg n ) 时间，但是你构建堆的方式也是如此（heapq.heapify需要线性时间）。

于 2013-02-08T16:26:06.027 回答
0

Every node in a heap is larger than all its children. Also, if the node is at index i, its immediate children are at indices 2 * i + 1 and 2 * i + 2.

Viewing the heap as a binary tree, you can recurse down the heap, stopping if an entry is bigger than the maxkey you've got (since all its children will be larger), and outputting the node if its key is between minkey and maxkey.

Putting this together gives this:

def extract_range(h, i, minkey, maxkey):
    if i >= len(h) or h[i][0] >= maxkey:
        return
    if h[i][0] >= minkey:
        yield h[i]
    for k in 1, 2:
        for r in extract_range(h, 2 * i + k, minkey, maxkey):
            yield r
于 2013-02-08T15:51:16.720 回答