12

如何有效地从 a 中选择一个随机元素std::set？

Astd::set::iterator不是随机访问迭代器。所以我不能直接索引一个随机选择的元素，就像我可以为 a std::dequeorstd::vector

我可以获取从返回的迭代器并在 [ , )std::set::begin()范围内随机增加它的次数，但这似乎做了很多不必要的工作。对于接近集合大小的“索引”，我最终会遍历内部树结构的整个前半部分，即使已经知道该元素不会在那里找到。0std::set::size()

有更好的方法吗？

以效率的名义，我愿意将“随机”定义为比我可能用来在向量中选择随机索引的任何方法更不随机。称之为“合理随机”。

编辑...

下面有很多有见地的答案。

简短的版本是，即使您可以在log(n)时间内找到特定元素，您也无法通过接口在该时间内找到任意元素。std::set

4

6 回答 6

8

改用boost::container::flat_set：

boost::container::flat_set<int> set;
// ...
auto it = set.begin() + rand() % set.size();

虽然插入和删除变成了 O(N)，但我不知道这是否是个问题。您仍然有 O(log N) 查找，并且容器是连续的这一事实提供了整体改进，通常超过 O(log N) 插入和删除的损失。

于 2012-09-05T19:50:59.127 回答
4

导致随机树遍历的find(or )谓词怎么样？lower_bound您必须告诉它集合的大小，以便它可以估计树的高度，有时会在叶节点之前终止。

编辑：我意识到这个问题是std::lower_bound需要一个谓词但没有任何树状行为（在内部它使用std::advance在另一个答案的评论中讨论）。 std::set<>::lower_bound使用集合的谓词，它不能是随机的并且仍然具有类似集合的行为。

啊哈，您不能使用不同的谓词，但可以使用可变谓词。由于std::set通过值传递谓词对象，因此您必须使用 apredicate &作为谓词，以便您可以访问并修改它（将其设置为“随机化”模式）。

这是一个准工作示例。不幸的是，我无法将我的大脑包裹在正确的随机谓词上，所以我的随机性不是很好，但我相信有人可以解决这个问题：

#include <iostream>
#include <set>
#include <stdlib.h>
#include <time.h>

using namespace std;

template <typename T>
struct RandomPredicate {
    RandomPredicate() : size(0), randomize(false) { }
    bool operator () (const T& a, const T& b) {
        if (!randomize)
            return a < b;

        int r = rand();
        if (size == 0)
            return false;
        else if (r % size == 0) {
            size = 0;
            return false;
        } else {
            size /= 2;
            return r & 1;
        }
    }

    size_t size;
    bool randomize;
};

int main()
{
    srand(time(0));

    RandomPredicate<int> pred;
    set<int, RandomPredicate<int> & > s(pred);
    for (int i = 0; i < 100; ++i)
        s.insert(i);

    pred.randomize = true;
    for (int i = 0; i < 100; ++i) {
        pred.size = s.size();
        set<int, RandomPredicate<int> >::iterator it = s.lower_bound(0);
        cout << *it << endl;
    }
}

我半生不熟的随机性测试是./demo | sort -u | wc -l看看我得到了多少个唯一整数。使用更大的样本集尝试./demo | sort | uniq -c | sort -n寻找不需要的模式。

于 2012-09-05T19:41:21.177 回答
2

如果您可以访问底层的红黑树（假设存在一个），那么您可以访问 O(log n) 中的随机节点，选择 L/R 作为ceil(log2(n))-bit 随机整数的连续位。但是，您不能，因为标准没有公开底层数据结构。

Xeo 将迭代器放置在向量中的解决方案是 O(n) 时间和空间来设置，但总体上摊销常数。std::next这与O(n) 时间相比是有利的。

于 2012-09-05T19:50:11.990 回答
1

您可以使用以下std::advance方法：

set <int> myset;
//insert some elements into myset
int rnd = rand() % myset.size();
set <int> :: const_iterator it(myset.begin());
advance(it, rnd);
//now 'it' points to your random element

另一种方法，可能不太随机：

int mini = *myset().begin(), maxi = *myset().rbegin();
int rnd = rand() % (maxi - mini + 1) + mini;
int rndresult = *myset.lower_bound(rnd);
于 2012-09-05T19:44:56.107 回答
1

如果集合不经常更新或者您不需要经常运行此算法，请将数据的镜像副本保存在 a 中vector（或仅根据需要将集合复制到向量）并从中随机选择。

如评论中所见，另一种方法是将迭代器向量保留在集合中（它们仅在删除sets 的元素时无效）并随机选择一个迭代器。

最后，如果您不需要基于树的集合，您可以使用vectorordeque作为您的底层容器并在需要时进行排序/唯一化。

于 2012-09-05T19:52:06.273 回答
1

您可以通过维护一个正常的值数组来做到这一点；当您插入到集合中时，您将元素附加到数组的末尾（O(1)），然后当您想要生成一个随机数时，您也可以从O(1)中的数组中获取它。

当您想从数组中删除元素时，问题就来了。最天真的方法将采用O(n)，这可能足以满足您的需求。但是，可以使用以下方法将其改进为O(log n) ；

保留，对于i数组中的每个索引，prfx[i]，它表示数组中范围内未删除元素的数量0...i。保留一个分段树，您可以在其中保留prfx[i]每个范围中包含的最大值。

Updating the segment tree can be done in O(log n) per deletion. Now, when you want to access the random number, you query the segment tree to find the "real" index of the number (by finding the earliest range in which the maximum prfx is equal to the random index). This makes the random-number generation of complexity O(log n).

于 2012-09-05T20:10:42.853 回答