2

優先度付きの優先キュー（heapq）を使用しdatetime.datetimeています。

検索するstartTimeとendTimeがある場合、このリストから要素のサブセットを抽出するための最もPython的な方法は何ですか。（元のリストを変更できないため、新しいリストを作成して返すか、イテレータを返す必要があります）

以下は私が持っているものの例です：

>>> 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

ヒープは、この操作を実行するための理想的な構造ではありません。のパブリックAPIに固執するheapqと、ヒープが変更され、以降の操作で使用できなくなります。@ Anonymousのソリューションは機能する可能性がありますが、（IMHO）は実装の詳細に依存しすぎています。これらは公に文書化されていますが、実際に使用すべきかどうかはわかりません。

リストを並べ替えて2つのバイナリ検索を実行するだけで、必要な操作を簡単に実行できます。

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 nheapq.heapify ）時間がかかることですが、ヒープを構築する方法も同様です（線形時間がかかります）。

于 2013-02-08T16:26:06.027 に答える
0

ヒープ内のすべてのノードは、そのすべての子よりも大きくなります。また、ノードがインデックスiにある場合、その直接の子はインデックス2 * i+1および2*i+2にあります。

ヒープをバイナリツリーとして表示すると、ヒープを再帰的に処理し、エントリが取得したmaxkeyよりも大きい場合は停止し（すべての子が大きくなるため）、キーがminkeyとmaxkeyの間にある場合はノードを出力できます。 。

これをまとめると、次のようになります。

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 に答える