У меня есть набор диапазонов, которые могут выглядеть примерно так:
[(0, 100), (150, 220), (500, 1000)]
Затем я бы добавил диапазон, скажем (250, 400), и список будет выглядеть следующим образом:
[(0, 100), (150, 220), (250, 400), (500, 1000)]
Затем я попытался бы добавить диапазон (399, 450), и он будет ошибочным, потому что это перекрыло (250, 400).
Когда я добавляю новый диапазон, мне нужно выполнить поиск, чтобы убедиться, что новый диапазон не перекрывает существующий диапазон. И ни один диапазон никогда не будет в списке, который перекрывает другой диапазон в списке.
С этой целью я хотел бы, чтобы структура данных дешево поддерживала свои элементы в отсортированном порядке и быстро позволяла мне находить элемент до или после определенного элемента.
Есть ли лучший способ решить эту проблему? Есть ли такая структура данных, которая доступна в Python? Я знаю, что существует модуль bisect, и, вероятно, я буду использовать. Но я надеялся, что есть что-то лучше.
Изменить: Я решил эту проблему с помощью модуля bisect. Вот ссылка на код. Это немного долго, поэтому я не буду публиковать его здесь:
Реализация списка диапазонов байтов
Используйте SortedDict из SortedCollection.
A SortedDict предоставляет те же методы, что и dict. Кроме того, SortedDict эффективно поддерживает свои ключи в отсортированном порядке. Следовательно, метод ключей возвращает ключи в отсортированном порядке, метод popitem удаляет элемент с наивысшим ключом и т.д.
Я использовал его - он работает. К сожалению, сейчас у меня нет времени для правильного сопоставления производительности, но, по-видимому, она становится быстрее, чем модуль bisect.
Похоже, вы хотите что-то вроде 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
Дешевый поиск и дешевая вставка, как правило, расходятся. Вы можете использовать связанный список для структуры данных. Затем поиск, чтобы найти точку вставки для нового элемента, является 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),
)
Чтобы ответить на ваш вопрос:
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 как упражнение.
(Этот код не проверен и может потребоваться некоторое подталкивание)
Может быть, модуль 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)]