O（1）中unordered_set的随机元素?
我见过人们提到在O（1）时间内可以从unordered_set中获取随机元素。我试图这样做：
std::unordered_set<TestObject*> test_set;
//fill with data
size_t index = rand() % test_set.size();
const TestObject* test = *(test_set.begin() + index);
但是，unordered_set迭代器不支持带整数的+。 begin可以给出一个size_t参数，但它是一个桶而不是一个元素的索引。随机挑选一个桶然后在其中随机挑选一个元素将导致非常不平衡的随机分布。
适当的O（1）随机访问的秘诀是什么？如果重要，这是在VC ++ 2010中。
回答 2
Stack Overflow用户
发布于 2018-08-23 16:29:46
std::unordered_set不提供随机访问迭代器。我想这是stl设计者的选择，为stl实现者提供更多自由......底层结构必须支持O（1）插入和删除，但不必支持随机访问。例如，unordered_set即使不能为这样的底层容器编写随机访问迭代器代码，也可以将符合stl的代码编码为双向链表。
即使第一个元素是随机的，因此获取一个完全随机的元素是不可能的，因为元素在底层容器中通过散列排序的方式是确定性的......在我正在处理的算法类型中，使用第一个元素会使结果偏差很多。
我可以想到一个“hack”，如果你可以在O（1）中构建一个随机的value_type元素......这就是这个想法：
- 检查无序集合是否为空（如果是，则没有希望）
- 生成随机value_type元素
- 如果已经在无序集中返回它，否则插入它
- 获取
it此元素的迭代器 - 得到随机元素
*(it++)（如果*it是获取第一个元素的最后一个元素） - 删除您插入的元素并返回（5）中的值
所有这些操作都是O（1）。你可以实现我给出的伪代码并很容易地模板化它。
注意：非常奇怪的第五步也很重要...因为例如如果你得到随机元素it++（it--如果it是最后一个迭代器）那么第一个元素可能比其他元素少两倍（不是微不足道的但是考虑一下）它...）。如果你不关心你的分布偏差那么你可以得到前面的元素。
Stack Overflow用户
发布于 2018-08-23 17:23:08
我使用buck_count（）和cbegin（n）方法编写了一个解决方案，随机选择一个存储桶，然后在存储桶中随机选择一个元素。
两个问题： - 这不是恒定的时间（更糟糕的情况是有很多空桶和一个桶中的许多元素） - 概率分布是倾斜的
我认为随机查看元素的唯一方法是维护一个提供随机访问迭代器的单独容器。
#include <random>
#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <cassert>
using namespace std;
ranlux24_base randomEngine(5);
int rand_int(int from, int to)
{
assert(from <= to);
return uniform_int_distribution<int>(from, to)(randomEngine);
}
int random_peek(const unordered_set<int> & container)
{
assert(container.size() > 0);
auto b_count = container.bucket_count();
auto b_idx = rand_int(0, b_count - 1);
size_t b_size = 0;
for (int i = 0; i < b_count; ++i)
{
b_size = container.bucket_size(b_idx);
if (b_size > 0)
break;
b_idx = (b_idx + 1) % b_count;
}
auto idx = rand_int(0, b_size - 1);
auto it = container.cbegin(b_idx);
for (int i = 0; i < idx; ++i)
{
it++;
}
return *it;
}
int main()
{
unordered_set<int> set;
for (int i = 0; i < 1000; ++i)
{
set.insert(rand_int(0, 100000));
}
unordered_map<int,int> distribution;
const int N = 1000000;
for (int i = 0; i < N; ++i)
{
int n = random_peek(set);
distribution[n]++;
}
int min = N;
int max = 0;
for (auto & [n,count]: distribution)
{
if (count > max)
max = count;
if (count < min)
min = count;
}
cout << "Max=" << max << ", Min=" << min << "\n";
return 0;
}
https://stackoverflow.com/questions/-100001398
复制相似问题