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

Question

这个问题增加了一个限制条件。

只要不过于偏向某一侧，我愿意允许非均匀选择。

由于"集合通常是实现为二叉搜索树的"，而且我预计它们会包含一些深度或大小信息来进行平衡，因此我认为您可以对树进行加权随机游走。 但是，我不知道任何适用于多种平台的方法。

编辑：限制条件不是分摊时间。

- BCS

---

那是一个有趣的问题，但是 我 会将其实现为平衡树的一个特性，这在库实现中很难做到。 - dmckee --- ex-moderator kitten

std::set没有被定义为二叉搜索树。其复杂度要求基本上意味着它不能是其他任何类型的数据结构，但是树结构不是标准的一部分，因此也不包含在接口中。（如果你有一个真正平衡的树，你可以通过随机选择左或右孩子直到到达底部，在O(log n)时间内选择一个随机元素）。也许下一个标准应该提出一个“random()”接口；毕竟，已经有一个“random_shuffle”算法了，并且这并没有什么不同。（顺便说一下，在“std::unordered_set”中可以在O(1)时间内完成。） - Kerrek SB

@KerrekSB：也许选择左、右或停止，这样每个元素至少有机会。 - GManNickG

@GMan：是的，当然，谢谢！相应的概率必须进行调整。 - Kerrek SB

看起来我得等到C++2x版本中的random()接口。 - BCS

Answer 1

介绍一个大小与集合相等的数组。使数组元素保持集合中每个元素的地址。生成随机整数 R，其范围在数组/集合大小内，选择数组中由索引为 R 的元素标记的地址，并对其进行取消引用以获取集合的元素。

- Victor Sorokin

---

每次集合发生变化时，重新生成该数组。 - Violet Giraffe

没错，在 OP 的帖子中从未提到过集合会发生变化。而且，也没有说有任何内存限制 :) - Victor Sorokin

这也是真的 :) 你的解决方案看起来像是通过集合的公共接口唯一可能的。 - Violet Giraffe

嗯，这种感觉有点像作弊……“将集合复制到另一个数据结构中，然后做一些其他的东西”……我的意思是，它能够工作，但感觉好像失去了重点。 - Kerrek SB

我正在寻找一种解决方案，无论集合被修改的频率如何，该解决方案都保持有效。 - BCS

Answer 2

我不认为只用std::set就可以做到，所以你可能需要一个不同的数据结构。像Victor Sorokin所说的那样，你可以将一个set与一个vector组合使用。不要使用set<T>，而是使用map<T, size_t>，再加上vector< map<T, size_t>::iterator >。每个键的值都是向量中的一个索引，向量的每个元素指向地图元素。向量元素没有特定的顺序。当你添加一个元素时，把它放在向量的末尾。当你删除一个元素并且它不是向量中的最后一个元素时，将最后一个元素移动到删除的元素位置。

- Derek Ledbetter

Answer 3

如果你知道集合中元素的分布，你可以随机选择键（具有相同分布）并使用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;
}

- Mooing Duck

---

@BCS：除非你自己动手，否则我认为除了这个标准集之外，它无法在logN中完成。 - Mooing Duck

Answer 4

通过使用这个构造函数，您可以制作一个随机顺序的地图副本。

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

...并传入一个比较器，该比较器比较键的哈希值（或其他确定性扩展函数）。

然后根据这个新映射获取“最小”的键。

您可以一次构建映射，并在多个请求“随机”元素中分摊成本。

- phs

---

那是一个严格的弱序吗？ - Kerrek SB

但那是O(n)，不是吗？所以它相当优雅地解决了另一个问题，但并没有解决这个问题。 - dmckee --- ex-moderator kitten

通过在多次调用中摊销构造成本，可以将隐藏常量变得任意小。 - phs

@KerrekSB 不，不是这样的。可以相互比较键的哈希值，然后进行更新。 - phs

除非std::set是一个哈希表，否则这比O(n)更糟糕。 - Andres Jaan Tack

如果采用 O(N log(N)) 生成副本，然后在重新生成之前将其耗尽，则每个项目的成本为 O(log(N))。 - phs

Answer 5

针对 std::unordered_set<int> s：

1）在 min(s)..max(s) 中随机取一个数 R 2）如果 R 在 s 中：返回 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），概率取决于元素之间的距离。无序集合则通过哈希进行随机化。

希望这可以帮到您。

PS：将std::set<V>转换为std::set<std::pair<int，V>>（其中对第二个元素进行哈希的第一个元素是哈希）使得此方法适用于任何可哈希的V。

- Aleksandr Pakhomov