1

Python リストのサブセットを見つける必要があります。

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

各要素の最初の要素が start_time を表し、2 番目の要素が end_time であり、クエリの形式が (start, end) であるとします。結果のサブセットは、サブセットの各要素の start_time と end_time が start と end の間にあるようにする必要があります。

これを行うための最速の方法は何ですか (または実行時間を短縮するためにデータを保存する必要がある構造)?

4

3 に答える 3

2

範囲ツリーを使用してポイントを保存できます。（start_time、end_time）ペアを（x、y）座標と見なします。次に、（start、end）のクエリは、正方形[start、end] x [start、end]内のポイントを見つけることの問題になります。

2次元の範囲ツリーはO（n log n）時間で計算でき、それらに対するクエリはO（log n）時間で実行されます。

残念ながら、私は（おそらくPython Quadtreeを除いて）優れたPython実装を知らないので、自分で実装する必要があるかもしれません。ただし、線形検索ソリューションよりも確実に高速になります。

範囲ツリーを使用したり作成したりしたくない場合は、代わりにNumPyを使用して線形検索を高速化することを検討してください。

arr = np.array(a)
xa, ya, val = arr.T
pts = (xa >= start) & (ya <= end)
print arr[pts]
于 2012-10-05T17:26:35.667 に答える
1 
>>> 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]]

リスト内包。=包括的でない場合は 削除します。

于 2012-10-05T16:37:37.270 に答える
1

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

次に、 and関数bisectに基づいて特殊な関数を作成します。bisect.bisect_leftbisect.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これらの操作を組み合わせて、時系列リストとインデックスの両方をカプセル化するクラスにするのは簡単です。

于 2012-10-05T16:38:08.237 に答える