найти набор диапазонов, число которых падает в

Question

У меня есть список строк в 200 тыс. Строк, таких как start_position, stop position. Список включает все виды перекрытий в дополнение к неперекрывающимся.

список выглядит следующим образом

• [3,5]
• [10,30]
• [15,25]
• [5,15]
• [25, 35]
• ...

Мне нужно найти диапазоны, данное число падает. И повторит его для 100 тыс. чисел. Например, если 18 является данное число со списком выше, то функция должна возвращать [10,30] [15,25]

Я делаю это в чрезмерно сложным способом с использованием Bisect, кто может дать подскажите, как это сделать быстрее.

Thanks

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) 

Этот код использует 200 тыс. Сегментов и 100 номеров. Он работал на моем 2,3 ГГц i5 macbook за 9,3 секунды, то есть для полного запуска 200k x 100k вам понадобилось бы 2,5 часа. Наверное, не достаточно быстро, но могут быть способы ускорить этот подход - я подумаю об этом.

Answer 4

Как насчет

1. сортировать по первой колонке О (п журнал п)

2. бинарный поиск, чтобы найти индексы, которые находятся вне диапазона O (журнал N)

3. бросок out вне диапазона

4. сортировать по второй колонке O (n log n)

5. бинарный поиск, чтобы найти индексы, которые находятся вне диапазона O (журнал N)

6. выбрасывают значения из диапазона

7. вы остались со значениями в диапазоне

Этот должен быть O (n log n)

Вы можете сортировать строки и столбцы с помощью np.sort, а бинарный поиск должен состоять только из нескольких строк кода.

Если у вас есть много запросов, вы можете сохранить первую отсортированную копию для последующих вызовов, но не вторую. В зависимости от количества запросов может оказаться лучше выполнять линейный поиск, чем сортировать, а затем искать.

Answer 5

Лучший способ решить это - построить дерево интервалов. (Дерево диапазона, заданное sza, является статическим, что означает, что после его создания вы не можете добавлять/удалять узлы. Если это нормально, то его ответа будет достаточно.)

Здесь вы можете узнать о дереве интервалов:

Youtube: https://www.youtube.com/watch?v=q0QOYtSsTg4

Wiki: https://en.wikipedia.org/wiki/Interval_tree

интервал дерево в основном бинарное дерево на основе левого значения диапазона кортежа. ([влево, вправо]) Что особенного в том, что каждый узел в дереве имеет значение с именем max. Максимальное значение имеет наибольшее правое значение узлов, которые находятся ниже этого узла, включая сам узел. Другими словами, текущий узел будет иметь максимальное значение, установленное в самое большое правое значение поддерева, которым текущий узел является корнем.

Чтобы развернуть это для вашей проблемы, мы можем добавить и минимальное значение. Если значение min будет содержать наименьшее левое значение всего поддерева, где этот узел является корнем.

Edited 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 чисел, и работает в 94 секунд на моем 2,3 ГГц Intel i5. Вот вывод 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}