Эффективный алгоритм объединения небольших перекрывающихся блоков в более крупные смежные блоки

Question

Я столкнулся с довольно интересной проблемой. У меня есть (довольно большое) количество блоков. Блок - это просто что-то, начинающееся со смещения и имеющее длину и цвет. Смещение и длина ограничены - пространство, в котором существуют эти блоки, составляет <0-N>, где N варьируется от сотен тысяч до нескольких миллионов. Недопустимый блок - это любой блок со смещением больше N или суммой смещения и длины больше N. Блок может иметь около 16 различных цветов (только один из них).

Может быть тысячи блоков, и всегда есть ситуации, подобные этой:

block_X: off: 100, len: 50, цвет: синий
block_Y: off: 148, len: 50, цвет: синий
block_Z: off: 200, len: 30, цвет: красный

Как видите, блоки X и Y могут быть соединены в один больший блок, в результате чего:

block_XY: off: 100, len 98, цвет: синий
block_Z: off 200, len 30, цвет: красный

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

Есть также интересный поворот, учтите это:

block_A: off: 100, len: 200, цвет: синий
block_B: off: 200, len: 200, цвет: синий
block_C: off: 300, len: 150, цвет: red
block_D: off: 400, len: 200, цвет: синий
block_E: off: 500, len: 200, цвет: синий

Как видите, у нас есть хорошая последовательность синих блоков, которые можно объединить в один большой синий блок. Тем не менее, есть также маленький красный блок в середине этого. Это не должно обманывать алгоритм, правильный результат:

block_ABDE: off: 100, len: 600, цвет: синий
block_C: off: 300, len: 150, цвет: красный

Данные хранятся в std :: multimap, где ключом является смещение, а значением является структура, содержащая длину и цвет блока, что-то вроде: multimap<uint32_t,pair<uint32_t, uint8_t> >. Обратите внимание, что могут быть блоки, начинающиеся с одинакового смещения. Однако гарантируется, что если это произойдет, блоки, начинающиеся с одного и того же смещения, будут иметь разные цвета и разную длину.

Может кто-нибудь придумать хорошую идею, как эффективно решить эту проблему? Цель алгоритма - уменьшить количество имеющихся у нас блоков, но НЕ обязательно уменьшать его до минимально возможного количества.

Answer 1

Я бы предложил следующее:

1. Создайте отдельный список для каждого из цветов
2. Для каждого конкретного цвета вычислить начало (смещение) и конец (смещение + длина) всех блоков
3. Сортировка каждого цветоспецифичного списка по значению начала
4. Теперь пройдитесь по каждому списку, объединяя элементы: если начало следующего элемента меньше или равно концу предыдущего элемента (плюс допустимый разрыв), удалите следующий элемент и расширьте предыдущий.

Answer 2

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

Как только у вас есть списки для каждого цвета, вы будете выполнять итерацию по каждому из них: начиная с первого блока, проверьте, достаточно ли близок смещение следующего блока к концу текущего блока, и, если это так, объедините их. Затем продолжите до конца списка.

Теперь вы объединили все блоки каждого цвета, поэтому вы можете просто объединить свои списки, чтобы получить окончательный список всех блоков всех цветов. Самым дорогим (асимптотически) шагом будет сортировка, так что это, вероятно, достаточно эффективно. Возможно, вам удастся придумать что-то более быстрое в среднем, используя более сложные структуры данных, чем массивы и связанные списки, но это не окупится, пока вы не измерите производительность этого более простого подхода.

Обратите внимание: поскольку правила объединения двух блоков зависят только от конечной точки одного блока и начальной точки другого, и не зависят от размера блоков, любое решение, которое может идентифицировать любое потенциальные слияния, вероятно, идентифицируют все слияния, и не имеет значения, в каком порядке выполняются слияния (то есть слияние является ассоциативной операцией).

Answer 3

Вам не нужно разбивать блоки на один список для каждого цвета.Вы можете отсортировать весь список по начальному адресу блока, а затем обработать его за один проход, сохранив отдельную пару {start, length} для каждого цвета.

Answer 4

Это довольно просто, так как для каждого цвета это просто номерной диапазон, например,

синий: 100-299, 200-400, 500-670, 671-702

, в который вы сливаетесь:

синий: 100-400, 500-702

Просто отсортируйте по первому значению в диапазоне и посмотрите на конечное значение (на самом деле одно за последним элементом). Если оно больше или равно началу следующего, они объединяются.

В приведенных выше 300> 200, так что они объединяются, 401 <500, поэтому они не объединяются, 671 == 671, поэтому они объединяются. </p>

Сделайте то же самое для каждого цвета.