17

我定义一个unordered_map这样的：

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

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

4

5 回答 5

21

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函数。

于 2014-11-19T18:35:25.093 回答
11

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

如果效率是指 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));

Wherernd(n)返回 [0,n) 范围内的随机数。

在实践中，如果你有一个像样的散列，大多数桶将只包含一个元素，否则这个函数将略微特权在他们的桶中单独的元素。

于 2014-11-19T21:42:03.950 回答
6

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

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

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

于 2016-10-27T14:25:12.980 回答
5

这是从地图中获取随机元素的方法：

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()) );
于 2014-11-19T18:35:07.000 回答
1

的解决方案

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

非常慢....

一个更快的解决方案将是：

  • 分配边时，同时将其键放置到 std::vector<std::string> vec
  • 随机一个int index范围从0到vec.size() - 1
  • 然后得到edges[vec[index]]
于 2019-10-12T13:40:31.810 回答