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 模块解决了这个问题。因为代码有点长，我有个链接。不过不幸的是，paste.list.org 这个地方现在已经找不到了。

Answer 1

便宜的搜索和便宜的插入通常是相互矛盾的。你可以使用链表作为数据结构。在这种情况下，查找插入新元素的位置需要O(n)的时间，而将新元素插入到正确的位置则只需要O(1)的时间。

不过，使用简单的Python列表可能更好。随机访问（也就是找到你要的位置）是恒定时间的。为了保持排序而在正确的位置插入元素在理论上更贵，但这取决于动态数组的实现方式。实际上，只有在底层数组需要重新分配时，你才会真正感受到插入的高成本。

关于检查日期范围是否重叠，我之前也遇到过同样的问题。这是我使用的代码。我最初是在一个博客帖子中找到的，那个帖子是从一个SO回答链接过来的，但现在那个网站似乎不再存在了。我实际上在我的范围中使用的是日期时间，但它同样适用于你的数字值。

def dt_windows_intersect(dt1start, dt1end, dt2start, dt2end):
    '''Returns true if two ranges intersect. Note that if two
    ranges are adjacent, they do not intersect.

    Code based on:
    http://beautifulisbetterthanugly.com/posts/2009/oct/7/datetime-intersection-python/
    http://stackoverflow.com/questions/143552/comparing-date-ranges  
    '''

    if dt2end <= dt1start or dt2start >= dt1end:
        return False

    return  dt1start <= dt2end and dt1end >= dt2start

这里是一些单元测试来证明它有效：

from nose.tools import eq_, assert_equal, raises

class test_dt_windows_intersect():
    """
    test_dt_windows_intersect
    Code based on: 
    http://beautifulisbetterthanugly.com/posts/2009/oct/7/datetime-intersection-python/
    http://stackoverflow.com/questions/143552/comparing-date-ranges  

               |-------------------|         compare to this one
    1               |---------|              contained within
    2          |----------|                  contained within, equal start
    3                  |-----------|         contained within, equal end
    4          |-------------------|         contained within, equal start+end
    5     |------------|                     overlaps start but not end
    6                      |-----------|     overlaps end but not start
    7     |------------------------|         overlaps start, but equal end
    8          |-----------------------|     overlaps end, but equal start
    9     |------------------------------|   overlaps entire range

    10 |---|                                 not overlap, less than
    11 |-------|                             not overlap, end equal
    12                              |---|    not overlap, bigger than
    13                             |---|     not overlap, start equal
    """


    def test_contained_within(self):
        assert dt_windows_intersect(
            datetime(2009,10,1,6,0),    datetime(2009,10,1,7,0),
            datetime(2009,10,1,6,30),   datetime(2009,10,1,6,40),
        )

    def test_contained_within_equal_start(self):
        assert dt_windows_intersect(
            datetime(2009,10,1,6,0),    datetime(2009,10,1,7,0),
            datetime(2009,10,1,6,0),    datetime(2009,10,1,6,30),
        )

    def test_contained_within_equal_end(self):
        assert dt_windows_intersect(
            datetime(2009,10,1,6,0),    datetime(2009,10,1,7,0),
            datetime(2009,10,1,6,30),   datetime(2009,10,1,7,0),
        )

    def test_contained_within_equal_start_and_end(self):
        assert dt_windows_intersect(
            datetime(2009,10,1,6,0),    datetime(2009,10,1,7,0),
            datetime(2009,10,1,6,0),    datetime(2009,10,1,7,0),
        )

    def test_overlaps_start_but_not_end(self):
        assert dt_windows_intersect(
            datetime(2009,10,1,6,0),    datetime(2009,10,1,7,0),
            datetime(2009,10,1,5,30),   datetime(2009,10,1,6,30),
        )

    def test_overlaps_end_but_not_start(self):
        assert dt_windows_intersect(
            datetime(2009,10,1,6,0),    datetime(2009,10,1,7,0),
            datetime(2009,10,1,6,30),   datetime(2009,10,1,7,30),
        )

    def test_overlaps_start_equal_end(self):
        assert dt_windows_intersect(
            datetime(2009,10,1,6,0),    datetime(2009,10,1,7,0),
            datetime(2009,10,1,5,30),   datetime(2009,10,1,7,0),
        )

    def test_equal_start_overlaps_end(self):
        assert dt_windows_intersect(
            datetime(2009,10,1,6,0),    datetime(2009,10,1,7,0),
            datetime(2009,10,1,6,0),    datetime(2009,10,1,7,30),
        )

    def test_overlaps_entire_range(self):
        assert dt_windows_intersect(
            datetime(2009,10,1,6,0),    datetime(2009,10,1,7,0),
            datetime(2009,10,1,5,0),    datetime(2009,10,1,8,0),
        )

    def test_not_overlap_less_than(self):
        assert not dt_windows_intersect(
            datetime(2009,10,1,6,0),    datetime(2009,10,1,7,0),
            datetime(2009,10,1,5,0),    datetime(2009,10,1,5,30),
        )

    def test_not_overlap_end_equal(self):
        assert not dt_windows_intersect(
            datetime(2009,10,1,6,0),    datetime(2009,10,1,7,0),
            datetime(2009,10,1,5,0),    datetime(2009,10,1,6,0),
        )

    def test_not_overlap_greater_than(self):
        assert not dt_windows_intersect(
            datetime(2009,10,1,6,0),    datetime(2009,10,1,7,0),
            datetime(2009,10,1,7,30),    datetime(2009,10,1,8,0),
        )

    def test_not_overlap_start_equal(self):
        assert not dt_windows_intersect(
            datetime(2009,10,1,6,0),    datetime(2009,10,1,7,0),
            datetime(2009,10,1,7,0),    datetime(2009,10,1,8,0),
        )

Answer 2

看起来你想要的功能类似于 bisect 模块中的 insort_right 和 insort_left。这些功能可以用来处理列表和元组。

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 3

使用来自 SortedDict 的 SortedCollection。

SortedDict 提供了和普通字典（dict）一样的方法。不同的是，SortedDict 会自动把它的键（key）保持在一个有序的状态。所以，当你用键的方法时，它会返回排好序的键；当你用 popitem 方法时，它会移除键值最大的那个项，等等。

我用过这个，效果不错。可惜我现在没时间做详细的性能对比，但主观感觉它比 bisect 模块快了些。