数字が

Question

に入る範囲のセットを見つける私は、start_position、stop positionのような番号範囲の200k行のリストを持っています。 このリストには、重複していないものに加えて、すべての種類の重複が含まれています。

リストは、この

• [3,5]
• [10,30]
• [15,25]
• [5,15]
• 【25のように見えます35]
• ...

私は範囲を見つける必要があること与えられた数字が入ります。そして、100kの数字に対してそれを繰り返します。例えば 18は、上記のリストで指定した数であるならば、関数は誰でも与えることができ、私は二分使用して過度に複雑な方法でそれをやっている [10,30] [15,25]

を返す必要がありますどのようにしてより速くそれを行うかについての手掛かり。

ありがとうございました

Answer 1

範囲のカバレッジの問題です。処理するクエリが大量であるため、できるだけ早く結果を返す必要があります。この問題に関連するアルゴリズムがあります。Segment Treeをご覧ください。

考えられるのは、与えられた間隔に基づいて最初にセグメントツリーを構築し、次に各クエリに対して、log(N)という速さで実行できます。ここで、Nは間隔の数です。

すべての可能なk間隔を取得するには、まず、すべてのサブ間隔をカバーする親ノードがlog(n)であることがわかります。その子ノードをトラバースしてすべてのk間隔を取得します。したがって、与えられた数のすべての間隔を取得する時間の複雑さは、log(N) + O(k)（k << n）で囲まれます。

このアルゴリズムは、すべての間隔に所定の数が含まれている場合、O(N)の速度に低下する可能性があります。この場合、出力のサイズはNなので、より良い解決策はありません。アルゴリズムの複雑さは少なくとも出力サイズと同じかそれ以上でなければならないからです。

希望します。ここ<=を使用して

Answer 2

def get_containing_intervals(x): 
    for start, end in intervals: 
     if start <= x <= end: 
      yield x 

は間隔が（クローズエンド型）含まれています仮定に基づいています。

この関数を何度も呼び出す予定がある場合は、何らかの前処理をしたいと思うかもしれません。 @szaが示唆するもの

Answer 3

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個の数字が使用されます。それは9.3秒で私の2.3 GHzのi5のMacBookで走った。つまり、200k×100kのフルランでは、2.5時間が必要だった。恐らく十分速くないかもしれませんが、このアプローチをスピードアップする方法があるかもしれません - 私はそれについて考えるでしょう。バイナリ検索は範囲O外のインデックスを見つけるため

Answer 4

方法について、最初の列のOによって

1. ソート（NログN）（ログn）の

2. 投げますアウト値が範囲外である

3. 第2列でソートO（n log n）

4. 範囲O外のインデックス（n個のログを記録）

5. はあなたが範囲内の値で残っている範囲外の値

これを捨てる見つけるためのバイナリ検索O（n log n）

np.sortを使用して行と列を並べ替えることができます。バイナリ検索はコードの数行に過ぎません。

多くのクエリがある場合は、最初のソートされたコピーを後続のコールに保存できますが、2番目のコールは保存できません。クエリの数に応じて、並べ替えと検索よりも線形検索を行うほうがよい場合があります。

Answer 5

これを解決する最善の方法は、インターバルツリーを構築することです。あなたがそれを作った後、ノードを追加/削除することができないことを意味します。

ここでは、区間木について学ぶことができます：

YouTubeの：https://www.youtube.com/watch?v=q0QOYtSsTg4

ウィキ：https://en.wikipedia.org/wiki/Interval_tree

区間木は基本的範囲タプルの左側の値に基づいて、二分木です。 （[left、right]）特有の点は、ツリー内の各ノードにmaxという値があることです。最大値は、ノード自体を含め、このノードの下にあるノードの最も大きな右の値を保持します。言い換えれば、現在のノードはその最大値を現在のノードがルートであるサブツリーの最も大きな右の値に設定します。

この問題を拡大するために、最小値を追加することもできます。ここで、min値は、このノードがルートであるすべてのサブツリーの最小の左の値を保持します。ビデオから

編集SCREENCAP：（品質申し訳ありません）

私たちは数あなたのためのクエリを実行するときを意味します

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. 

Answer 6

[OK]を、ここでは木の実装は次のとおりです。

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 

DEMO：

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出力があります：

OUTPUT：

  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}