start_position、stop position のような数値範囲の 20 万行のリストがあります。リストには、重複しないものだけでなく、あらゆる種類の重複が含まれます。
リストは次のようになります
特定の数値が収まる範囲を見つける必要があります。そして、100k の数値に対してそれを繰り返します。たとえば、上記のリストで 18 が指定された数値である場合、関数は [10,30] [15,25] を返す必要があります。
私は bisect を使用して非常に複雑な方法でそれを行っています。より高速な方法でそれを行う方法の手がかりを誰でも与えることができますか?
ありがとう
範囲カバレッジの問題のようです。処理するクエリが大量にあるため、できるだけ早く結果を返す必要があります。この問題に関連するアルゴリズムがあります。Segment Treeを参照してください。
アイデアは、最初に指定された間隔に基づいてセグメント ツリーを構築することです。次に、クエリごとに、できるだけ速く実行できます。log(N)ここNで、 は間隔の数です。
すべての可能なk間隔を取得するには、最初に ですべてのサブ間隔をカバーする親ノードを見つけ、log(n)次にその子をトラバースして k 個の間隔をすべて取得します。したがって、特定の数値のすべての間隔を取得する時間の複雑さは、 によって制限されlog(N) + O(k)ますk << n。
O(N)このアルゴリズムは、すべての間隔に指定された数値が含まれる場合と同じくらい遅くなる可能性があります。この場合、出力のサイズが であるため、Nこれ以上の解決策はありません。アルゴリズムの複雑さは、少なくとも出力サイズと同じかそれ以上でなければならないためです。
それが役に立てば幸い。
これを解決する最善の方法は、間隔ツリーを構築することです。(sza によって与えられた範囲ツリーは静的です。つまり、それを構築した後は、ノードを追加/削除することはできません。それでよろしければ、彼の答えで十分です。)
ここでインターバルツリーについて学ぶことができます：
ユーチューブ: https://www.youtube.com/watch?v=q0QOYtSsTg4
ウィキ: https://en.wikipedia.org/wiki/Interval_tree
インターバル ツリーは、基本的に、範囲タプルの左の値に基づくバイナリ ツリーです。([左、右]) 特別なのは、ツリーの各ノードに max という名前の値があることです。最大値は、ノード自体を含む、このノードの下にあるノードの最大の右の値を保持します。つまり、現在のノードの最大値は、現在のノードがルートであるサブツリーの最大値に設定されます。
問題に対してこれを拡張するために、最小値も追加できます。最小値は、このノードがルートであるすべてのサブツリーの左の最小値を保持します。
ビデオから編集されたスクリーン キャップ: (品質について申し訳ありません)
つまり、数値をクエリすると、次のようになります。
1) add current node to set of answers if number is inside range
2) go left if number is less than max value of left child.
3) go right if number is greater than min value of right child.
わかりました、ここにツリーの実装があります:
import itertools
class treeNode:
def __init__(self, segments):
self.value = None
self.overlapping = None
self.below = None
self.above = None
if len(segments) > 0:
self.value = sum(itertools.chain.from_iterable(segments))/(2*len(segments))
self.overlapping = set()
belowSegs = set()
aboveSegs = set()
for segment in segments:
if segment[0] <= self.value:
if segment[1] < self.value:
belowSegs.add(segment)
else:
self.overlapping.add(segment)
else:
aboveSegs.add(segment)
self.below = treeNode(belowSegs)
self.above = treeNode(aboveSegs)
else:
self.overlapping = None
def getOverlaps(self, item):
if self.overlapping is None:
return set()
if item < self.value:
return {x for x in self.overlapping if x[0]<=item and item<=x[1]} | self.below.getOverlaps(item)
elif item > self.value:
return {x for x in self.overlapping if x[0]<=item and item<=x[1]} | self.above.getOverlaps(item)
else:
return self.overlapping
デモ:
import random as r
maxInt = 100
numSegments = 200000
rng = range(maxInt-1)
lefts = [r.choice(rng) for x in range(0, numSegments)]
segments = [(x, r.choice(range(x+1, maxInt))) for x in lefts] # Construct a list of 200,000 random segments from integers between 0 and 100
tree = treeNode(segments) # Builds the tree structure based on a list of segments/ranges
def testReturnSegments():
for item in range(0,100000):
item = item % maxInt
overlaps = tree.getOverlaps(item)
import cProfile
cProfile.run('testReturnSegments()')
これは 200k のセグメントを使用し、100k の数字の重複するセグメントを見つけ、私の 2.3 GHz Intel i5 で 94 秒で実行されます。cProfile の出力は次のとおりです。
出力:
1060004 function calls (580004 primitive calls) in 95.700 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 95.700 95.700 <string>:1(<module>)
580000/100000 11.716 0.000 93.908 0.001 stackoverflow.py:27(getOverlaps)
239000 43.461 0.000 43.461 0.000 stackoverflow.py:31(<setcomp>)
241000 38.731 0.000 38.731 0.000 stackoverflow.py:33(<setcomp>)
1 1.788 1.788 95.700 95.700 stackoverflow.py:46(testReturnSegments)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.004 0.004 0.004 0.004 {range}
import random as r
rng = range(99)
lefts = [r.choice(rng) for x in range(0, 200000)]
segments = [(x, r.choice(range(x+1, 100))) for x in lefts]
leftList = sorted(segments, key=lambda x:x[0])
rightList = sorted(segments, key=lambda x:x[1])
def returnSegments(item, segments, leftList, rightList):
for leftN in range(len(leftList)):
if leftList[leftN][0] > item:
break
for rightN in range(len(rightList)):
if rightList[rightN][1] > item:
break
return list(set(leftList[:leftN]) & set(rightList[rightN:]))
def testReturnSegments():
for item in range(0,100):
item = item % 100
returnSegments(item, segments, leftList, rightList)
このコードは、200k のセグメントと 100 個の数字を使用します。私の 2.3 GHz i5 macbook で 9.3 秒で実行されました。つまり、200k x 100k を完全に実行するには、2.5 時間必要です。おそらく十分ではありませんが、このアプローチを高速化する方法があるかもしれません-私はそれについて考えます.
どうですか、
最初の列で並べ替え O(n log n)
範囲外のインデックスを見つける二分探索 O(log n)
範囲外の値を捨てる
2 番目の列で並べ替え O(n log n)
範囲外のインデックスを見つける二分探索 O(log n)
範囲外の値を捨てる
範囲内の値が残っています
これは O(n log n) である必要があります
np.sort を使用して行と列を並べ替えることができ、バイナリ検索は数行のコードで済みます。
多数のクエリがある場合、最初の並べ替えられたコピーを後続の呼び出し用に保存できますが、2 番目のコピーは保存できません。クエリの数によっては、並べ替えてから検索するよりも線形検索を実行した方がよい場合があります。
def get_containing_intervals(x):
for start, end in intervals:
if start <= x <= end:
yield x
ここでの使用<=は、間隔が包括的である (クローズエンド) という仮定に基づいています。
この関数を何度も呼び出すつもりなら、@sza が提案するような前処理をしたいと思うでしょう。