Подтвердить что ты не робот

Существует ли стандартная структура данных Python, которая хранит вещи в отсортированном порядке?

У меня есть набор диапазонов, которые могут выглядеть примерно так:

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

Затем я бы добавил диапазон, скажем (250, 400), и список будет выглядеть следующим образом:

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

Затем я попытался бы добавить диапазон (399, 450), и он будет ошибочным, потому что это перекрыло (250, 400).

Когда я добавляю новый диапазон, мне нужно выполнить поиск, чтобы убедиться, что новый диапазон не перекрывает существующий диапазон. И ни один диапазон никогда не будет в списке, который перекрывает другой диапазон в списке.

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

Есть ли лучший способ решить эту проблему? Есть ли такая структура данных, которая доступна в Python? Я знаю, что существует модуль bisect, и, вероятно, я буду использовать. Но я надеялся, что есть что-то лучше.

Изменить: Я решил эту проблему с помощью модуля bisect. Вот ссылка на код. Это немного долго, поэтому я не буду публиковать его здесь:

Реализация списка диапазонов байтов

4b9b3361

ОТВЕТЫ

Ответ 1

Используйте SortedDict из SortedCollection.

A SortedDict предоставляет те же методы, что и dict. Кроме того, SortedDict эффективно поддерживает свои ключи в отсортированном порядке. Следовательно, метод ключей возвращает ключи в отсортированном порядке, метод popitem удаляет элемент с наивысшим ключом и т.д.

Я использовал его - он работает. К сожалению, сейчас у меня нет времени для правильного сопоставления производительности, но, по-видимому, она становится быстрее, чем модуль bisect.

Ответ 2

Похоже, вы хотите что-то вроде bisect's 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) overlaps (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

Ответ 3

Дешевый поиск и дешевая вставка, как правило, расходятся. Вы можете использовать связанный список для структуры данных. Затем поиск, чтобы найти точку вставки для нового элемента, является O (n), а последующая вставка нового элемента в правильное местоположение - O (1).

Но вам, вероятно, лучше просто использовать простой список Python. Случайный доступ (т.е. Поиск вашего места) занимает постоянное время. Вставка в правильном месте для сохранения сортировки теоретически более дорога, но это зависит от того, как реализуется динамический массив . Вы действительно не платите большую цену за вставки, пока не произойдет перераспределение основного массива.

Что касается проверки перекрытия диапазонов дат, то в прошлом у меня была такая же проблема. Вот код, который я использую. Я изначально нашел его в блоге, связанном с ответом SO, но этот сайт больше не существует. Я фактически использую datetimes в своих диапазонах, но он будет работать одинаково хорошо с вашими числовыми значениями.

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),
        )

Ответ 4

Чтобы ответить на ваш вопрос:

Is there a data structure like that available in Python?

Нет, нет. Но вы можете легко создать один из них, используя список как базовую структуру и код из модуля bisect, чтобы сохранить список в порядке и проверить на перекрытия.

class RangeList(list):
"""Maintain ordered list of non-overlapping ranges"""
    def add(self, range):
    """Add a range if no overlap else reject it"""
        lo = 0; hi = len(self)
        while lo < hi:
            mid = (lo + hi)//2
            if range < self[mid]: hi = mid
            else: lo = mid + 1
        if overlaps(range, self[lo]):
            print("range overlap, not added")
        else:
            self.insert(lo, range)

Я оставляю функцию overlaps как упражнение. (Этот код не проверен и может потребоваться некоторое подталкивание)

Ответ 5

Может быть, модуль bisect может быть лучше, чем простая следующая функция?

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


def verified_insertion(x,L):
    u,v = x
    if v<L[0][0]:
        return [x] + L
    elif u>L[-1][0]:
        return L + [x]
    else:
        for i,(a,b) in enumerate(L[0:-1]):
            if a<u and v<L[i+1][0]:
                return L[0:i+1] + [x] + L[i+1:]
    return L 


lo = verified_insertion((-10,-2),li)

lu = verified_insertion((102,140),li)

le = verified_insertion((222,230),li)

lee = verified_insertion((234,236),le) # <== le

la = verified_insertion((408,450),li)

ly = verified_insertion((2000,3000),li)

for w in (lo,lu,le,lee,la,ly):
    print li,'\n',w,'\n'

Функция возвращает список без изменения списка, переданного как аргумент.

результат

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

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

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

[(0, 100), (150, 220), (250, 400), (500, 1000)] 
[(0, 100), (150, 220), (222, 230), (234, 236), (250, 400), (500, 1000)] 

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

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