如何在小于O(n)的时间内选择std::集合中的一个随机元素

Question

这个问题有一个附加的约束。

我愿意允许不统一的选择，只要它不是倾斜的。

考虑到"集合通常被实现为二叉搜索树"，并且我期望它们将包含某种深度或大小信息来平衡，我希望你可以对树进行某种加权随机漫步。然而，我不知道有任何远程便携的方法来做到这一点。

编辑:约束不是针对平摊时间的

Answer 1

引入大小等于set的数组。使数组元素保存set中每个元素的地址。生成以数组/集合大小为界的随机整数R，在R索引的数组元素中选取地址解引用，得到集合的元素

Answer 2

我不知道如何用std::set做，所以你可能需要一个不同的数据结构。就像维克多·索罗金说的，你可以把一个集合和一个向量结合起来。用map<T, size_t> + vector< map<T, size_t>::iterator >代替set<T>。每个键的值都是指向vector的索引，vector的每个元素都指向映射元素。向量元素没有特定的顺序。当你添加一个元素时，把它放在vector的末尾。当你删除一个元素并且它不是vector中的最后一个元素时，将最后一个元素移动到被删除元素的位置。

Answer 3

如果您知道集合中元素的分布，则可以随机选择key(具有相同的分布)并使用std::set::lower_bound。这可是太多了。

int main() {
    std::set<float> container;
    for(float i=0; i<100; i += .01)  
        container.insert(i);
    //evenish distribution of 10000 floats between 0 and 100.
    float key = std::rand() *10000f / RAND_MAX; //not random, sue me
    std::set<float>::iterator iter = container.lower_bound(key); //log(n)
    std::cout << *iter;
    return 0;
}

Answer 4

您可以使用这个构造函数创建一个随机顺序的map副本

template <class InputIterator>
set(InputIterator f, InputIterator l,
    const key_compare& comp)

. .并传递一个比较器来比较键的哈希值(或其他确定性扩散函数)。然后根据这张新地图取"最小"的键。

您可以构造一次映射，然后在对"随机"元素的多次请求中分摊成本。

Answer 5

For std::unordered_set<int> s:

1)在min(s)..max(s)中随机取R

2)如果R in s: return R

3)

newIter = s.insert(R).first;
newIter++;
if (newIter == s.end()) {
    newIter = s.begin();
}
auto result = *newIter;
s.erase(R);
return result;

对于有序集合(std::set)，概率取决于元素之间的距离。Unordered_set是随机化的。

我希望这对你有帮助。

PS将std::set<V>转换为std::set<std::pair<int, V>>(其中pair中的第一个元素是第二个元素的哈希值)使得该方法适用于任何可哈希v。