在unordered_map中选择随机元素

Question

我这样定义unordered_map:

std::unordered_map<std::string, Edge> edges;

有没有一种从unordered_map边缘中选择随机Edge的有效方法？

Answer 1

Pre-C++ 11解决方案:

std::tr1::unordered_map<std::string, Edge> edges;
std::tr1::unordered_map<std::string, Edge>::iterator random_it = edges.begin();
std::advance(random_it, rand_between(0, edges.size()));

C++ 11以后的解决方案:

std::unordered_map<std::string, Edge> edges;
auto random_it = std::next(std::begin(edges), rand_between(0, edges.size()));

选择有效随机数的功能取决于您的选择,但请确保它在非空[0 ; edges.size() - 1]时返回范围内的数字edges.

该std::next函数只是std::advance以允许直接赋值的方式包装函数.

Answer 2

有没有一种从unordered_map边缘中选择随机Edge的有效方法？

如果有效你的意思是O(1),那么不,这是不可能的.

由于返回的迭代器unordered_map::begin / end是ForwardIterators,所以简单使用的方法是std::advance元素数量为O(n).

如果您的特定用途允许,您可以交换一些随机性以提高效率:

您可以选择随机存储桶(可以在O(1)中访问),然后选择该存储桶中的随机元素.

int bucket, bucket_size;
do
{ 
    bucket = rnd(edges.bucket_count());
}
while ( (bucket_size = edges.bucket_size(bucket)) == 0 );

auto element = std::next(edges.begin(bucket), rnd(bucket_size));

其中rnd(n)返回[0,n]范围内的随机数.

实际上,如果你有一个像样的哈希,大多数桶将只包含一个元素,否则这个函数将略微授予他们的桶中单独的元素.

Answer 3

这是你如何从地图中获取随机元素:

std::unordered_map<std::string, Edge> edges;
iterator item = edges.begin();
int random_index = rand() % edges.size();
std::advance(item, random_index);

或者看看这个答案,它提供了以下解决方案:

std::unordered_map<std::string, Edge> edges;
iterator item = edges.begin();
std::advance( item, random_0_to_n(edges.size()) );

Answer 4

没有桶的严格 O(1) 解决方案：

1. 保留一个键向量，当您需要从地图中获取随机元素时，从向量中选择一个随机键并从地图中返回相应的值 - 需要恒定时间
2. 如果您在地图中插入键值对，请检查此类键是否已存在，如果不是，则将该键添加到您的键向量中 - 需要恒定时间
3. 如果要在选择后从地图中删除元素，请将您选择的键与键向量的 back() 元素交换并调用 pop_back()，然后从地图中删除该元素并返回值 - 需要恒定时间

但是，有一个限制：如果你想从地图中删除元素而不是随机选择，你需要修复你的关键向量，这需要 O(n) 天真的方法。但是仍然有一种方法可以获得 O(1) 性能：保留一个映射，告诉您键在键向量中的位置并使用交换更新它:)