Dam*_*mon 6 c++ sorting algorithm
考虑到时间限制,我需要处理数十万个事件(产生结果).时钟实际上正在滴答作响,当计时器触发时,必须刷新在该点完成的任何操作.
那个时间没准备好的东西要么被丢弃(取决于重要性度量),要么在下一个时间量程期间处理(具有"重要性提升",即向重要性度量添加常量).
理想情况下,CPU比需要的速度快得多,并且整个集合在时间片结束之前已经准备好了很长时间.不幸的是,世界很少是理想的,在您知道之前,"数十万"变成"数千万".
事件在它们进入时被添加到队列的后面(实际上是一个向量),并且在相应的下一个量程期间从前面处理(因此程序总是处理最后一个量子的输入).
但是,并非所有事件都同样重要.如果可用时间不够,最好放弃不重要的事件而不是重要的事件(这不是一个严格的要求,因为重要的事件将被复制到下一个时间量子的队列,但这样做会进一步增加负载所以它不是一个完美的解决方案).
当然,使用的显而易见的事情是优先级队列/堆.不幸的是,堆积100k元素并不是一个自由操作(或并行),然后我最终将对象放在一些非显而易见且不一定是缓存友好的内存位置,并且从优先级队列中提取元素不会很好地并行化.
我真正喜欢的有点像一个被排序或至少"稍微近似排序"的矢量,之后可以顺序遍历.这将简单地允许我创建例如12个线程(或任何其他数字,每个CPU一个),每个线程处理例如1/64的范围(或另一个大小),从前端到末端缓慢前进,并最终丢弃/推迟遗留下来的东西 - 这将是可以丢弃的重要事件.
简单地使用整个范围进行排序std::sort将是最简单,最直接的解决方案.但是,对项目进行排序所需的时间减少了在固定时间预算内实际处理元素的可用时间,并且排序时间大部分是单CPU时间(并行排序也不是那么好).
此外,进行完美排序(实际上并不需要)可能会带来最坏的情况复杂性,而理想情况下,近似排序应该在最佳状态下执行,并且具有非常可预测的成本.
所以,我正在寻找的是一种仅对数组/向量进行近似排序,但速度快,并且具有可预测(或保证)运行时的方法.
排序键是一个通常在10到1000之间的小整数.被推迟到下一次量子可能会增加("优先级提升")该值的少量,例如100或200.
在一个不同的问题,其中人都应该使用"主观比较"做一个大致的排序(？)希尔排序中提出的.在各种排序演示applet上,似乎至少对于那些典型的"随机随机"输入,shell排序确实可以进行"近似排序",对于数据的3-4次传递看起来并不太糟糕(和至少读取抽头是严格顺序的).不幸的是,选择能够很好地工作的间隙值似乎是一种黑色艺术,而运行时估计似乎也涉及大量调查水晶球.
具有相对大的收缩因子(例如2或3？)的梳子排序看起来也很诱人,因为它严格按顺序访问内存(在两个水龙头上)并且能够快速远离元素远距离.再次,从排序演示小程序判断,似乎3-4遍已经给出了相当合理的"近似排序".
考虑到MSD基数排序,虽然我不确定它如何在典型的16/32位整数中执行,其中大多数最重要的位都是零!人们可能不得不做一个初始传递来找到整个集合中最重要的位,然后是2-3个实际的排序传递？
有没有更好的算法或着名的工作方法与我提到的算法之一？
我想到的是迭代向量，如果某个事件不太重要，则不处理它而是将其放在一边。读取整个向量后，立即查看搁置的事件。当然，您可以使用多个具有不同优先级的存储桶。并且只在那里存储引用，您不想移动兆字节的数据。（现在根据达蒙的要求作为答案发布）