Я пытаюсь вычислить область горизонта (перекрывающиеся прямоугольники с одинаковой базой)
Проблема - эффективность памяти, когда есть много значений, script просто бросает MemoryError. У кого-нибудь есть идеи для оптимизации использования памяти?
Ответ 2
Вы выделяете отдельную пару "ключ-значение" для каждого отдельного целочисленного значения в вашем диапазоне. Представьте себе случай, когда R = 1 и L = 100000. Ваш словарь items будет заполнен 1000000 элементами. Основная идея обработки/удаления перекрытий - это звук, но способ, которым вы это делаете, - это массовый перебор.
Как и многое другое в жизни, это проблема с графикой в маскировке. Отображение вершин, представляющих собой прямоугольники, которые вы пытаетесь обработать, и (взвешенные) ребра являются перекрытиями. Усложнение состоит в том, что вы не можете просто добавить области вершин и вычесть области перекрытий, потому что многие перекрытия перекрывают друг друга. Проблема перекрытия может быть решена путем применения преобразования, которое преобразует два перекрывающихся прямоугольника в неперекрывающиеся прямоугольники, эффективно разрезая кромку, которая их соединяет. Преобразование показано на изображении ниже. Обратите внимание, что в некоторых случаях одна из вершин также будет удалена, упрощая график, а в другом случае добавляется новая вершина:
![введите описание изображения здесь]()
Зеленый: перекрытие для измельчения.
Обычно, если мы имеем прямоугольники m и n перекрываем между ними, построение графика было бы операцией O(m2), потому что нам пришлось бы проверять все вершины для перекрытия друг с другом. Тем не менее, мы можем полностью обойти конструкцию входного графика, чтобы получить алгоритм обхода O(m + n), который будет оптимальным, поскольку мы будем анализировать только каждый прямоугольник один раз и построить график вывода без перекрытий максимально эффективно. O(m + n) предполагает, что ваши входные прямоугольники сортируются в соответствии с их левыми краями в порядке возрастания. Если это не так, алгоритм будет O(mlog(m) + n) для учета начального этапа сортировки. Обратите внимание, что по мере увеличения плотности графика n будет идти от ~m до ~m2. Это подтверждает интуитивную идею о том, что чем меньше перекрытий есть, тем больше вы ожидаете, что процесс будет работать в O(m) времени, тогда как чем больше перекрытий будет, тем ближе вы будете работать до O(m2) времени.
Сложность пространства предлагаемого алгоритма будет O(m): каждый прямоугольник на входе приведет к не более чем двум прямоугольникам на выходе и 2m = O(m).
Достаточно об анализе сложности и о самом алгоритме. Вход будет представлять собой последовательность прямоугольников, определяемую L, R, H, как вы сейчас. Я предполагаю, что вход сортируется по левому краю L. Выходной график будет связанным списком прямоугольников, определяемых теми же параметрами, отсортированными в порядке убывания крайним правым краем. Глава списка будет самым правым прямоугольником. Выходные данные не будут перекрываться между любыми прямоугольниками, поэтому общая площадь горизонта будет просто суммой H * (R - L) для каждого из выходных прямоугольников ~m.
Причиной выбора связанного списка является то, что нам нужны только две операции: итерация из головы node и самая дешевая вставка для сохранения списка в отсортированном порядке. Сортировка будет выполняться как часть проверки перекрытия, поэтому нам не нужно делать какие-либо бинарные запросы через список или что-то в этом роде.
Поскольку список ввода упорядочивается путем увеличения левого края, а список результатов упорядочивается путем уменьшения правого края, мы можем гарантировать, что каждый добавленный прямоугольник будет проверяться только против прямоугольников, которые он фактически перекрывает 1. Мы выполним проверку и удаление совпадений, как показано на диаграмме выше, до тех пор, пока мы не достигнем прямоугольника, левый край которого меньше или равен левому краю нового прямоугольника. Все дальнейшие прямоугольники в выходном списке гарантированно не перекрываются с новым прямоугольником. Эта операция check-and-chop гарантирует, что каждое перекрытие посещается не более одного раза и что не перекрывающиеся прямоугольники обрабатываются без необходимости, что делает алгоритм оптимальным.
Прежде чем я покажу код, вот диаграмма алгоритма в действии. Красные прямоугольники - это новые прямоугольники; обратите внимание, что их левые края идут вправо. Синие прямоугольники - это те, которые уже добавлены и перекрываются с новым прямоугольником. Черные прямоугольники уже добавлены и не перекрываются с новым. Нумерация представляет собой порядок выходного списка. Это всегда делается справа. Связанный список - идеальная структура для поддержания этой прогрессии, поскольку она позволяет дешевые вставки и замены:
![введите описание изображения здесь]()
Ниже приведена реализация алгоритма, предполагающего, что входные координаты передаются в виде итерации объектов, имеющих атрибуты L, R и H. Предполагается, что порядок итерации будет отсортирован по левому краю. Если это не так, примените sorted или list.sort на первый вход:
from collections import namedtuple
# Defined in this order so you can sort a list by left edge without a custom key
Rect = namedtuple('Rect', ['l', 'r', 'h'])
class LinkedList:
__slots__ = ['value', 'next']
"""
Implements a singly-linked list with mutable nodes and an iterator.
"""
def __init__(self, value=None, next=None):
self.value = value
self.next = next
def __iter__(self):
"""
Iterate over the *nodes* in the list, starting with this one.
The `value` and `next` attribute of any node may be modified
during iteration.
"""
while self:
yield self
self = self.next
def __str__(self):
"""
Provided for inspection purposes.
Works well with `namedtuple` values.
"""
return ' -> '.join(repr(x.value) for x in self)
def process_skyline(skyline):
"""
Turns an iterable of rectangles sharing a common baseline into a
`LinkedList` of rectangles containing no overlaps.
The input is assumed to be sorted in ascending order by left edge.
Each element of the input must have the attributes `l`, r`, `h`.
The output will be sorted in descending order by right edge.
Return `None` if the input is empty.
"""
def intersect(r1, r2, default=None):
"""
Return (1) a flag indicating the order of `r1` and `r2`,
(2) a linked list of between one and three non-overlapping
rectangles covering the exact same area as `r1` and `r2`,
and (3) a pointer to the last nodes (4) a pointer to the
second-to-last node, or `default` if there is only one node.
The flag is set to True if the left edge of `r2` is strictly less
than the left edge of `r1`. That would indicate that the left-most
(last) chunk of the tuple came from `r2` instead of `r1`. For the
algorithm as a whole, that means that we need to keep checking for
overlaps.
The resulting list is always returned sorted descending by the
right edge. The input rectangles will not be modified. If they are
not returned as-is, a `Rect` object will be used instead.
"""
# Swap so left edge of r1 < left edge of r2
if r1.l > r2.l:
r1, r2 = r2, r1
swapped = True
else:
swapped = False
if r2.l >= r1.r:
# case 0: no overlap at all
last = LinkedList(r1)
s2l = result = LinkedList(r2, last)
elif r1.r < r2.r:
# case 1: simple overlap
if r1.h > r2.h:
# Chop r2
r2 = Rect(r1.r, r2.r, r2.h)
else:
r1 = Rect(r1.l, r2.l, r1.h)
last = LinkedList(r1)
s2l = result = LinkedList(r2, last)
elif r1.h < r2.h:
# case 2: split into 3
r1a = Rect(r1.l, r2.l, r1.h)
r1b = Rect(r2.r, r1.r, r1.h)
last = LinkedList(r1a)
s2l = LinkedList(r2, last)
result = LinkedList(r1b, s2l)
else:
# case 3: complete containment
result = LinkedList(r1)
last = result
s2l = default
return swapped, result, last, s2l
root = LinkedList()
skyline = iter(skyline)
try:
# Add the first node as-is
root.next = LinkedList(next(skyline))
except StopIteration:
# Empty input iterator
return None
for new_rect in skyline:
prev = root
for rect in root.next:
need_to_continue, replacement, last, second2last = \
intersect(rect.value, new_rect, prev)
# Replace the rectangle with the de-overlapped regions
prev.next = replacement
if not need_to_continue:
# Retain the remainder of the list
last.next = rect.next
break
# Force the iterator to move on to the last node
new_rect = last.value
prev = second2last
return root.next
Вычисление общей площади теперь тривиально:
skyline = [
Rect(-3, 0, 3), Rect(-1, 1, 2), Rect(2, 4, 4),
Rect(3, 7, 2), Rect(6, 8, 3),
]
processed = process_skyline(skyline)
area = sum((x.value.r - x.value.l) * x.value.h for x in processed) if processed else None
Обратите внимание, что измененный порядок входных параметров (H перемещен в конец). Результат area равен 29. Это соответствует тому, что я получаю, выполняя вычисления вручную. Вы также можете сделать
>>> print(processed)
Rect(l=6, r=8, h=3) -> Rect(l=4, r=6, h=2) -> Rect(l=2, r=4, h=4) ->
Rect(l=0, r=1, h=2) -> Rect(l=-3, r=0, h=3)
Это следует ожидать на диаграмме входов/выходов, показанной ниже:
![введите описание изображения здесь]()
В качестве дополнительной проверки я добавил новое здание Rect(-4, 9, 1) в начало списка. Он перекрывает все остальные и добавляет три единицы к area или конечный результат 32. processed выводится как:
Rect(l=8, r=9, h=1) -> Rect(l=6, r=8, h=3) -> Rect(l=4, r=6, h=2) ->
Rect(l=2, r=4, h=4) -> Rect(l=1, r=2, h=1) -> Rect(l=0, r=1, h=2) ->
Rect(l=-3, r=0, h=3) -> Rect(l=-4, r=-3, h=1)
Примечание:
Хотя я уверен, что эта проблема была решена много раз, решение, которое я здесь представляю, - это полностью моя собственная работа, сделанная без каких-либо других ссылок. Идея использования неявного представления графа и полученного анализа вдохновлена недавним чтением Руководства по дизайну алгоритма Стивена Скиена, второе издание. Это одна из лучших книг, которые я когда-либо встречал.
1 Технически, если новый прямоугольник не перекрывает никаких других прямоугольников, он будет проверяться на один прямоугольник, который он не перекрывает. Если бы эта дополнительная проверка была всегда, алгоритм имел бы дополнительные сравнения m - 1. К счастью, m + m + n - 1 = O(m + n), даже если нам всегда приходилось проверять один дополнительный прямоугольник (которого мы не делаем).
