是否存在标准的Python数据结构,使事物按排序顺序排列？

Question

我有一组范围可能看起来像这样:

[(0, 100), (150, 220), (500, 1000)]

然后我会添加一个范围,比如说(250, 400),列表看起来像这样:

[(0, 100), (150, 220), (250, 400), (500, 1000)]

然后我会尝试添加范围(399, 450),它会因为重叠而出错(250, 400).

当我添加新范围时,我需要搜索以确保新范围不与现有范围重叠.并且列表中的任何范围都不会与列表中的另一个范围重叠.

为此,我想要一个以排序顺序廉价维护其元素的数据结构,并且很快允许我在给定元素之前或之后找到该元素.

有没有更好的方法来解决这个问题？是否有像Python中可用的数据结构？我知道该bisect模块存在,这可能是我将使用的.但我希望有更好的东西.

编辑:我使用bisect模块解决了这个问题.这是代码的链接.这有点长,所以我不会在这里发布:

字节范围列表的实现

Answer 1

看起来你想要像bisect的 insort_right/insort_left 这样的东西.bisect模块使用列表和元组.

import bisect

l = [(0, 100), (150, 300), (500, 1000)]
bisect.insort_right(l, (250, 400))
print l # [(0, 100), (150, 300), (250, 400), (500, 1000)]
bisect.insort_right(l, (399, 450))
print l # [(0, 100), (150, 300), (250, 400), (399, 450), (500, 1000)]

您可以编写自己的overlaps函数,在使用之前可以使用它来检查insort.

我假设你的数字是(250, 400)重叠的错误(150, 300). overlaps()可以像这样写:

def overlaps(inlist, inrange):
    for min, max in inlist:
        if min < inrange[0] < max and max < inrange[1]:
            return True
    return False

Answer 2

使用SortedDict从SortedCollection.

SortedDict提供与dict相同的方法.此外,SortedDict有效地按排序顺序维护其键.因此,keys方法将按排序顺序返回键,popitem方法将删除具有最高键的项目等.

我用过它 - 它有效.不幸的是,我现在没有时间进行适当的性能比较,但主观上似乎比bisect模块更快.