帮助实现向量合并算法

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (17)

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

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

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

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

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

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

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

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

  1. 将src的所有元素追加到dst,在追加它之前加宽每个元素。然后运行就地排序。最后使用“读”和“写”指针迭代结果向量,读指针在写指针之前运行,合并跨越。当所有元素已合并(读指针到达结尾)时,dst被截断。
  2. 创建一个临时工作向量。通过重复从src或dst中选择下一个元素并合并到工作向量中,如上所述进行简单的合并。完成后,将工作向量复制到dst,替换它。

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

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

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

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

提问于
用户回答回答于

方法1中提到的排序可以减少到线性时间(从描述它的log-linear),因为两个输入列表已经排序。只需执行merge-sort的合并步骤。通过适当表示输入范围向量(例如单链表),可以就地完成。

http://en.wikipedia.org/wiki/Merge_sort

用户回答回答于

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

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

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

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

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

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

扫码关注云+社区

领取腾讯云代金券