Существует ли стандартная структура данных Python, которая поддерживает порядок в порядке? - PullRequest
Новая
       0

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

25 голосов
/ 03 апреля 2011

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

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

Я бы добавил диапазон, скажем (250, 400), и список выглядел бы так: 

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

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

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

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

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

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

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

Ответы [ 5 ]

13 голосов
/ 03 апреля 2011

Похоже, вы хотите что-то вроде 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) перекрывается (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
11 голосов
/ 24 октября 2016

Использовать SortedDict из SortedCollection .

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

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

4 голосов
/ 03 апреля 2011

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

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

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

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/
    /97563/sravnenie-diapazonov-dat  
    '''

    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/
    /97563/sravnenie-diapazonov-dat  

               |-------------------|         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),
        )
1 голос
/ 03 апреля 2011

Может быть, модуль 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)]
0 голосов
/ 03 апреля 2011

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

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 в качестве упражнения,(Этот код не проверен и может нуждаться в настройке)

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...