用于将小重叠块合并为更大的连续块的高效算法？

Question

我面临着一个相当有趣的问题.我有一个(相当大)的块数.块只是从偏移开始并具有长度和颜色的东西.偏移和长度是有限的 - 这些块存在的空间是<0-N>,其中N的范围从几十万到几百万.无效块是偏移量大于N或偏移量和长度之和大于N的任何块.块可能有大约16种不同的颜色(只有其中一种).

可能有数千个块,总有这样的情况:

block_X: off:100,len:50,颜色:blue
block_Y: off:148,len:50,颜色:blue
block_Z: off:200,len:30,颜色:红色

如您所见,X和Y块可以连接成一个更大的块,从而产生:

block_XY: off:100,len 98,颜色:蓝色
block_Z:关闭200,len 30,颜色:红色

我想创建一个算法,它将遍历所有块并连接那些重叠并具有相同颜色的块.实际上,如果块之间的间隙相当小(我可以选择一个常数,比如大约16左右,但可能是任何数字......)那么我还是想连接这些块.请注意,在上面的示例中,只有两个块连接.实际上,可以连接的块序列大部分时间都要长得多.

还有一个有趣的转折,考虑一下:

block_A: off:100,len:200,颜色:blue
block_B: off:200,len:200,颜色:blue
block_C: off:300,len:150,颜色:red
block_D: off:400,len:200,颜色:blue
block_E: off:500,len:200,颜色:蓝色

如您所见,我们有一个很好的蓝色块序列,可以合并为一个大的蓝色块.但是,中间还有一个小红块.这不应该欺骗算法,正确的结果是:

block_ABDE: off:100,len:600,颜色:blue
block_C: off:300,len:150,颜色:红色

数据存储在std :: multimap中,其中键是偏移量,值是包含块的长度和颜色的结构,如:multimap<uint32_t,pair<uint32_t, uint8_t> >.请注意,可能存在从相同偏移量开始的块.但是,保证,如果发生这种情况,从相同偏移开始的块具有不同的颜色和不同的长度.

任何人都可以想出如何有效地解决这个问题吗？该算法的目标是减少我们拥有的块数,但不要求将其减少到可能的最小量.

Answer 1

我建议如下:

1. 为每种颜色创建单独的列表
2. 对于每种特定颜色,计算所有块的开始(偏移)和结束(偏移+长度)
3. 按开始值对每个特定于颜色的列表进行排序
4. 现在,遍历每个列表,合并项目:如果下一个项目的开头小于或等于前一个项目的结束(加上允许的间隙),则删除下一个项目并扩展前一个项目.

Answer 2

将块列表分成每种颜色的列表,并按块的起始偏移量对所有列表进行排序.(实际上,您可能希望在基于颜色过滤时进行插入排序,或者按偏移排序,然后按颜色进行稳定排序并使用数组的分区.)

一旦你有了每个颜色列表,你将遍历每个颜色:从第一个块开始,检查下一个块的偏移量是否足够接近当前块的末尾,如果是,则合并它们.然后继续到列表的末尾.

现在,您已经组合了每种颜色的所有块,因此您可以连接列表以获得所有颜色的所有块的最终列表.最昂贵的步骤(渐近)将是排序,所以这可能足够有效.您可能能够使用比阵列和链接列表更高级的数据结构来提供平均速度更快的东西,但在衡量这种更简单方法的性能之前,这样做是不值得的.

请注意,因为可以合并两个块的规则仅取决于一个块的终点和另一个块的起点,并且不依赖于块的大小,任何可以识别任何潜在合并的解决方案都将可能识别所有合并,并且合并的顺序无关紧要(也就是说,合并是一种关联操作).