O（1）中unordered_set的随机元素?
O（1）中unordered_set的随机元素?
提问于 2018-08-23 08:01:14
我见过人们提到在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中。
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;
}
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/-100001398
复制相关文章
相似问题