一组不重叠整数范围的 Python 表示

Question

我想使用 Python 表示一组整数范围，其中可以动态修改该集合并测试包含情况。具体来说，我想将其应用于文件中的地址范围或行号。

我可以定义我关心的地址范围：

200 - 400  
450 - 470  
700 - 900  

然后我希望能够向集合添加一个可能重叠的范围，这样当我添加

460 - 490

时，集合就变成：

200 - 400  
450 - 490  
700 - 900  

但是然后能够从集合中删除，我可以排除范围

300 - 350

并且集合变成：

200 - 300
350 - 400  
450 - 490  
700 - 900  

最后，我希望能够迭代集合中包含的所有整数，或者测试集合是否包含特定值。

我想知道执行此操作的最佳方法是什么（特别是如果 Python 中内置了某些东西）。

Answer 1

您正在描述一个区间树。

pip install intervaltree

用途：

from intervaltree import IntervalTree, Interval
tree = IntervalTree()
tree[200:400] = True  # or you can use ranges as the "values"
tree[450:470] = True
tree[700:900] = True

查询：

>>> tree
IntervalTree([Interval(200, 400, True), Interval(450, 470, True), Interval(700, 900, True)])
>>> tree[250]
{Interval(200, 400, True)}
>>> tree[150]
set()

添加重叠范围：

>>> tree[450:490] = True
>>> tree
IntervalTree([Interval(200, 400, True), Interval(450, 470, True), Interval(450, 490, True), Interval(700, 900, True)])
>>> tree.merge_overlaps()
>>> tree
IntervalTree([Interval(200, 400, True), Interval(450, 490), Interval(700, 900, True)])

丢弃：

>>> tree.chop(300, 350)
>>> tree
IntervalTree([Interval(200, 300, True), Interval(350, 400, True), Interval(450, 490), Interval(700, 900, True)])

Answer 2

我用不同的语言实现了类似的东西。

基本思路：

• 保持按左边界排序的范围树。您可以保留一个 Python 列表，而不是真正的树，并使用

  bisect

  在日志时间内搜索它。这为您提供了查找/包含测试。
• 将所有操作表示为子范围操作。单元素操作仅适用于内部长度为 1 的子范围。
• 实现基本的子范围操作：加法（很简单）和减法（如果排除中间值，最终可能会得到两个子范围），或者一个子范围（可能为空）。
• 添加后，检查直接相邻的子范围，如果子范围相交，则可能与其中一个或两个子范围合并。继续双向操作，直到不再发生合并操作。

这应该可以帮助您开始。

Answer 3

使用 python 内置函数，您可以使用以下内容：

range_1 = range(450, 470)
range_temp = range(460, 490)

if any(num in range_1 for num in range_temp):
    start = min(range_1.start, range_temp.start)
    stop = max(range_1.stop, range_temp.stop)
    range_1 = range(start, stop)

当然需要进一步的逻辑来检查多个范围间隔的重叠。