帮助实现向量合并算法
我需要一个非常快速的算法来完成以下任务。我已经实现了几种完成它的算法，但它们对于我需要的性能来说太慢了。它应该足够快，以至于算法在现代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中的跨度之间存在大量重叠。
回答 2
Stack Overflow用户
发布于 2019-05-20 13:40:41
我们知道绝对最佳情况运行时是O（m + n），这是因为您至少必须扫描所有数据才能合并列表。鉴于此，您的第二种方法应该给您这种行为。
你有没有想过你的第二种方法来找出瓶颈是什么？根据您所讨论的数据量，很可能实际上无法在指定的时间内完成您想要的操作。验证这一点的一种方法是做一些简单的事情，例如总结循环中每个向量中跨距的所有起始值和结束值，以及时间。基本上，您在向量中为每个元素执行最少量的工作。这将为您提供可获得的最佳性能的基线。
除此之外，您可以避免使用stl swap方法逐个元素地复制矢量，并且可以将临时矢量预分配到特定大小，以避免在合并元素时触发数组的扩展。
您可以考虑在系统中使用2个向量，并且只要需要进行合并，就可以合并到未使用的向量中，然后交换（这类似于图形中使用的双缓冲）。这样，每次进行合并时都不必重新分配矢量。
但是，您最好先进行分析，然后找出您的瓶颈。如果分配与实际合并过程相比是最小的，那么您需要弄清楚如何更快地进行分配。
一些可能的额外加速可能来自直接访问矢量原始数据，这避免了每次访问数据的边界检查。
Stack Overflow用户
发布于 2019-05-20 14:47:25
方法1中提到的排序可以减少到线性时间（从描述它的log-linear），因为两个输入列表已经排序。只需执行merge-sort的合并步骤。通过适当表示输入范围向量（例如单链表），可以就地完成。
https://stackoverflow.com/questions/-100001164
复制相似问题