c++ - 一种用于对等值条目进行排序和改组的快速算法(最好使用 STL)

Question

我目前正在开发随机优化算法并遇到了以下问题(我想它也出现在其他地方):它可以称为完全不稳定的部分排序:

Given a container of size n and a comparator, such that entries may be equally valued. Return the best k entries, but if values are equal, it should be (nearly) equally probable to receive any of them.

(输出顺序与我无关，即最好的 k 中完全相等的值不需要打乱。然而，甚至打乱所有相等的值是一个相关的、有趣的问题，并且会够了!)

一种非常(!)低效的方法是使用 shuffle_randomly，然后使用 partial_sort，但实际上只需要在“选择时”对等值条目 block 进行洗牌border"(resp. 所有等值条目的 block ，两者都快得多)。也许观察是开始的地方......

如果有人可以提供带有 STL 算法的解决方案(或至少提供大部分)，我非常希望这样做，因为它们通常速度非常快、封装良好且 OMP 并行化。

提前感谢任何想法!

Answer 1

您想partial_sort首先。然后，当元素不相等时，返回它们。如果遇到大于剩余 k 的相等元素序列，则打乱并返回第 k 个。否则全部返回并继续。