c – 用于对等值条目进行排序和混洗的快速算法(最好通过STL)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了c – 用于对等值条目进行排序和混洗的快速算法(最好通过STL)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2422字，纯文字阅读大概需要4分钟。

内容图文

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

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,但实际上只需要在“选择边界”(即所有具有相同值的条目的块,两者都快得多)中混合等值条目的块. .也许观察是从哪里开始的……

我非常希望,如果有人可以提供STL算法的解决方案(或者至少在很大程度上),这两者都是因为它们通常非常快,封装良好且OMP并行化.

Thanx提前提出任何想法！

解决方法:

如果你的意思是输出顺序无关紧要,那么你需要std :: nth_element而不是std :: partial_sort,因为它通常会更快一些.请注意,std :: nth_element将第n个元素放在正确的位置,因此您可以执行以下操作,即100％标准算法调用(警告：未经过良好测试; fencepost错误可能性比比皆是)：

template<typename RandomIterator, typename Compare>
void best_n(RandomIterator first,
            RandomIterator nth,
            RandomIterator limit,
            Compare cmp) {
  using ref = typename std::iterator_traits<RandomIterator>::reference;
  std::nth_element(first, nth, limit, cmp);
  auto p = std::partition(first, nth, [&](ref a){return cmp(a, *nth);});
  auto q = std::partition(nth + 1, limit, [&](ref a){return !cmp(*nth, a);});
  std::random_shuffle(p, q);  // See note
}

该函数需要三个迭代器,如nth_element,其中nth是第n个元素的迭代器,这意味着它是begin()(n – 1)).

编辑：请注意,这与大多数STL算法不同,因为它实际上是一个包容性范围.特别是,如果nth == limit,则为UB,因为要求* nth有效.此外,没有办法请求最好的0元素,就像没有办法用std :: nth_element来请求第0个元素一样.您可能更喜欢使用不同的界面;请随意这样做.

或者你可以在要求0< k< = n：

best_n(container.begin(), container.begin()+(k-1), container.end(), cmp);

它首先使用nth_element将“最佳”k元素放在位置0..k-1中,保证第k个元素(或其中一个元素,无论如何)位于位置k-1.然后,它重新分配位置k-1之前的元素,使得相等的元素位于末尾,并且元素位于位置k-1之后,使得相等的元素位于开头.最后,它改变了相同的元素.

nth_element是O(n);两个分区操作总计为O(n);而random_shuffle是O(r),其中r是混洗的相等元素的数量.我认为所有这些都可以达到O(n),因此它具有最佳的可扩展性,但它可能是也可能不是最快的解决方案.

注意：您应该使用std :: shuffle而不是std :: random_shuffle,将统一的随机数生成器传递给best_n.但是我太懒了,不能写所有的样板来测试它.抱歉.

内容总结

以上是互联网集市为您收集整理的c – 用于对等值条目进行排序和混洗的快速算法(最好通过STL)全部内容，希望文章能够帮你解决c – 用于对等值条目进行排序和混洗的快速算法(最好通过STL)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---