背景:
在艰难的时限内，我需要处理数十万个事件(产生结果)。时钟实际上是滴答滴答，并且当计时器启动时，必须清除此时的所有操作。
到那个时候尚未准备好的东西要么被丢弃(取决于重要性度量)，要么在下一个时间范围内处理(具有“重要性提升”，即在重要性度量中添加常数)。
现在，理想情况下，CPU的速度比所需的要快得多，并且整个设备在时间片结束之前很长时间就可以准备好了。不幸的是，世界很少有理想的，“数十万”变成了“数千万”。
事件进入时将事件添加到队列的后面(实际上是一个 vector )，并在各个下一量子期间从前端进行处理(因此程序始终会处理最后一个量子的输入)。
但是，并非所有事件都同样重要。如果可用时间不足，则最好丢弃不重要的事件，而不是重要的事件(这不是严格的要求，因为重要事件将被复制到下一个量子队列中，但是这样做会进一步增加负担因此它不是一个完美的解决方案)。
当然，要使用的显而易见的事情是优先级队列/堆。不幸的是，堆放10万个元素也不是完全免费的操作(或并行操作)，然后我最终将对象放在了一些非显而易见的且不一定是缓存友好的内存位置，并且从优先级队列中提取元素并没有很好地并行化。
我真正想要的是某种经过排序的 vector ，或者至少是“某种程度近似排序的” vector ，之后可以依次遍历。这将平凡地允许我创建例如12个线程(或任何其他数量，每个CPU一个)处理例如每个范围的1/64(或其他大小)，从前端到末端缓慢前进，最后掉落/推迟剩余的内容-这将是不重要的事件，可以丢弃。
仅使用std::sort对整个范围进行排序将是最简单，最直接的解决方案。但是，排序项目所花费的时间减少了在固定时间预算内可用于实际处理元素的时间，并且排序时间大部分是单CPU时间(并行排序也不是那么好)。
同样，进行完美排序(实际上并不需要)可能会带来最坏的情况，而理想情况下，近似排序应该以最佳状态执行并且成本可预测。
tl; dr
因此，我正在寻找的是一种仅以近似但快速的方式对数组/vector 进行排序的方法，并且具有可预测的(或保证的)运行时间。
排序键是一个通常在10到1000之间的小整数。被推迟到下一次，quantum可能会将该值增加(例如，“priority boost”)一小部分。 100或200。
在有人应该使用“主观比较”(？)进行近似排序的different question中，提出了 shell排序。在各种排序演示小程序上，至少对于这些中的典型“随机随机播放”输入来说，shell排序确实可以执行“近似排序”，在3-4次传递数据的过程中看起来并不算太糟(并且至少读取是严格按顺序进行的)。不幸的是，选择效果良好的间隙值似乎有点荒唐，而运行时估计似乎也涉及到对 Crystal 球的大量考察。
具有相对较大收缩因子(例如2或3？)的comb sort 似乎也很吸引人，因为它严格按顺序(两次轻击)访问内存，并且能够快速地将元素移出很远的距离。再次，从对演示小程序进行排序来看，似乎3-4次通过已经给出了一个相当合理的“近似排序”。
想到了 MSD基数排序，尽管我不确定给定的典型16/32bit整数(其中大多数最高有效位都为零)将如何执行!可能需要进行一次初始遍历才能找到整个集合中的最高有效位，然后再进行2-3次实际排序遍历？
我提到的一种算法是否有更好的算法或众所周知的工作方法？
最佳答案
我想到的是遍历 vector ，如果某个事件不太重要，则不要处理它，而将其放在一边。读取完所有 vector 后，立即查看放置的事件。当然，您可以使用多个具有不同优先级的存储桶。并且仅在其中存储引用，您不想移动兆字节的数据。 (现在已按Damon的要求发布为答案)
关于c++ - 近似排序(数组/vector )，可预测的运行时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21434718/