帮助合并向量的算法

我需要一个非常快速的算法来完成以下任务.我已经实现了几种完成它的算法,但它们对于我需要的性能来说太慢了.它应该足够快,以至于算法可以在现代CPU上每秒运行至少100,000次.它将在C++中实现.

我正在使用跨度/范围,一个在一条线上有一个开始和一个结束坐标的结构.

我有两个跨度向量(动态数组),我需要合并它们.一个向量是src而另一个是dst.矢量按跨度起始坐标排序,并且跨度不在一个矢量内重叠.

src向量中的跨距必须与dst向量中的跨距合并,这样得到的向量仍然是有序的并且没有重叠.IE浏览器.如果在合并期间检测到重叠,则将两个跨度合并为一个.(合并两个跨度只是改变结构中的坐标.)

现在,还有一个问题,src向量中的跨度必须在合并期间"加宽".这意味着常量将添加到开始,另一个(更大)常量添加到src中每个跨度的结束坐标.这意味着在src spans加宽后它们可能会重叠.

到目前为止我所得到的是它不能完全就地完成,需要某种临时存储.我认为它应该在线性时间内超过src和dst求和的元素数量.

任何临时存储都可以在算法的多次运行之间共享.

我尝试过的两种主要方法是:

将src的所有元素追加到dst,在追加它之前加宽每个元素.然后运行就地排序.最后使用"读"和"写"指针迭代结果向量,读指针在写指针之前运行,合并跨越.当所有元素已合并(读指针到达结尾)时,dst被截断.

创建一个临时工作向量.通过重复从src或dst中选择下一个元素并合并到工作向量中,如上所述进行简单的合并.完成后,将工作向量复制到dst,替换它.

第一种方法的问题是排序是O((m + n)*log(m + n))而不是O(m + n)并且有一些开销.这也意味着dst向量必须比实际需要的大得多.

第二个主要问题是大量复制和再次分配/释放内存.

如果您认为需要,可以更改用于存储/管理跨度/向量的数据结构.

更新:忘记说数据集有多大.最常见的情况是两个向量中的4到30个元素,并且dst为空或者src和dst中的跨度之间存在大量重叠.

我们知道绝对最佳情况运行时是O(m + n),这是因为您至少必须扫描所有数据才能合并列表.鉴于此,您的第二种方法应该为您提供这种行为.

你有没有想过你的第二种方法来找出瓶颈是什么？根据您所讨论的数据量,很可能实际上无法在指定的时间内完成您想要的操作.验证这一点的一种方法是做一些简单的事情,例如总结循环中每个向量中跨距的所有起始值和结束值,以及时间.基本上,您在向量中为每个元素执行最少量的工作.这将为您提供可获得的最佳性能的基线.

除此之外,您可以避免使用stl swap方法逐个元素地复制矢量,并且可以将临时矢量预分配到特定大小,以避免在合并元素时触发数组的扩展.

您可以考虑在系统中使用2个向量,并且只要需要进行合并,就可以合并到未使用的向量中,然后交换(这类似于图形中使用的双缓冲).这样,每次进行合并时都不必重新分配矢量.

但是,您最好先进行分析,然后找出您的瓶颈.如果分配与实际合并过程相比最小,那么您需要弄清楚如何更快地进行分配.

一些可能的额外加速可能来自直接访问矢量原始数据,这避免了每次访问数据的边界检查.