python - 找到一个数字所在的一组范围

Question

我有一个 200k 行的数字范围列表，例如 start_position、stop 位置。除了不重叠的重叠之外，该列表还包括所有类型的重叠。

列表看起来像这样

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

我需要找到给定数字所在的范围。并将重复 100k 数字。例如，如果 18 是上面列表的给定数字，则函数应返回 [10,30] [15,25]

我正在使用 bisect 以一种过于复杂的方式进行操作，任何人都可以提供有关如何以更快的方式进行操作的线索。

谢谢

Answer 1

这似乎是一个范围覆盖问题。由于您要处理大量查询，因此您需要尽快给出结果。有一个与这个问题相关的算法，你可以看看Segment Tree。

这个想法是首先根据给定的间隔构建一个 Segment Tree，然后对于每个查询，您可以尽可能快地完成log(N)，其中N是间隔数。

要获取所有可能的k区间，首先找到覆盖所有子区间的父节点log(n)，然后遍历其子节点以检索所有 k 区间。因此，检索给定数字的所有区间的时间复杂度为log(N) + O(k)，其中k << n。

O(N)当所有间隔都包含给定数字时，该算法可能会恶化到一样慢。在这种情况下，由于输出的大小为N，因此不存在任何更好的解决方案。因为算法的复杂度必须至少与输出大小相同或更高。

希望能帮助到你。

Answer 2

解决这个问题的最好方法是构建一个区间树。（由 sza 给出的范围树是静态的。这意味着在你构建它之后你不能添加/删除节点。如果你没问题，那么他的回答就足够了。）

你可以在这里了解区间树：

优酷：https : //www.youtube.com/watch?v=q0QOYtSsTg4

维基：https ://en.wikipedia.org/wiki/Interval_tree

区间树基本上是基于范围元组的左值的二叉树。([left, right]) 它的特别之处在于树中的每个节点都有一个名为 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.

Answer 3

好的，这是一个树实现：

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}

Answer 4

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 小时。可能不够快，但可能有办法加快这种方法 - 我会考虑的。

Answer 5

怎么样，

1. 按第一列 O(n log n) 排序

2. 二进制搜索以查找超出范围 O(log n) 的索引

3. 抛出超出范围的值

4. 按第二列 O(n log n) 排序

5. 二进制搜索以查找超出范围 O(log n) 的索引

6. 抛出超出范围的值

7. 你只剩下范围内的值

这应该是 O(n log n)

您可以使用 np.sort 对行和列进行排序，二进制搜索应该只需要几行代码。

如果您有很多查询，您可以保存第一个排序副本以供后续调用，但不能保存第二个。根据查询的数量，执行线性搜索可能比先排序再搜索更好。

Answer 6

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

在这里使用<=是基于间隔是包容性的（封闭式）的假设。

如果您打算多次调用此函数，您可能想要进行某种预处理，例如@sza 所建议的。