3

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

给定一个大小为 n 的容器和一个比较器，这样条目的值可能相等。返回最好的 k 个条目，但如果值相等，则应该（几乎）同样有可能收到其中的任何一个。

（输出顺序与我无关，即最好的 k 中完全相等的值不需要被打乱。然而，即使将所有相等的值打乱也是一个相关的、有趣的问题，就足够了！）

一种非常（！）低效的方法是使用shuffle_randomlythen partial_sort，但实际上只需要在“选择边界”处打乱等值条目块（分别是所有等值条目块，两者都快得多）。也许观察是从哪里开始......

如果有人可以提供带有 STL 算法（或至少大部分）的解决方案，我会非常喜欢，因为它们通常非常快、封装良好且 OMP 并行化。

提前感谢任何想法！

4

4 回答 4

3

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

于 2012-11-10T16:26:09.077 回答
2

不完全理解你的问题，但如果你是我解决这个问题（如果我没看错的话）......

由于看起来您无论如何都必须遍历给定的对象，因此您不妨为结果构建它的副本，在插入时对其进行排序，并在插入时随机化您的“相等”项目。

换句话说，将给定容器中的项目复制到 STL 列表中，但重载比较运算符以创建 B-Tree，如果插入时两个项目相等，则随机选择在当前项目之前或之后插入它。

通过这种方式，它被最优地遍历（因为它是一棵树），并且每次构建列表时，您都会获得相等的项目的随机顺序。

这是内存的两倍，但我正在阅读此内容，因为您不想更改原始列表。如果您不在乎丢失原件，请在插入新列表时从原件中删除每个项目。最糟糕的遍历将是您第一次调用函数，因为传入的列表可能未排序。但是，由于您正在用排序后的副本替换列表，因此未来的运行应该会更快，并且您可以通过将根节点分配为 length() / 2 处的元素来为树选择更好的枢轴点。

希望这是有帮助的，听起来像一个整洁的项目。:)

于 2012-11-10T16:45:59.733 回答
1

如果您真的是说输出顺序无关紧要，那么您需要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 算法不同，因为它实际上是一个包含范围。特别是 UB if nth == limit，因为它必须*nth是有效的。此外，没有办法请求best 0元素，就像没有办法请求第 0个元素一样std::nth_element。您可能更喜欢使用不同的界面；随意这样做。

或者你可以这样称呼它，在要求之后0 < k <= n：

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

它首先用于nth_element将“最佳”k元素放在 position0..k-1中，以保证第 k个元素（或其中一个）位于 position k-1。然后它重新划分 position 前面的元素k-1，使相等的元素位于末尾，并重新划分 position 后面的元素k-1，使相等的元素位于开头。最后，它打乱相等的元素。

nth_element是O(n)；这两个partition操作的总和为O(n); 并且random_shuffle是O(r)其中r是混洗的相等元素的数量。我认为所有的总结都是O(n)如此，它具有最佳的可扩展性，但它可能是也可能不是最快的解决方案。

注意：您应该使用std::shuffle而不是std::random_shuffle，将统一随机数生成器传递给best_n。但是我懒得写所有的样板来做这件事并测试它。对不起。

于 2012-11-10T23:56:22.343 回答
0

如果您不介意对整个列表进行排序，那么有一个简单的答案。随机化比较器中等效元素的结果。

        std::sort(validLocations.begin(), validLocations.end(),
        [&](const Point& i_point1, const Point& i_point2)
          {
              if (i_point1.mX == i_point2.mX)
              {
                  return Rand(1.0f) < 0.5;
              }
              else
              {
                  return i_point1.mX < i_point2.mX;
              }
          });
于 2020-07-22T19:46:07.473 回答