选择在C随机元素的百分比++地图

Question

我有一个C ++地图：std::map <std::string, int>

我想挑选从这个图随机元素的对比率。这里P是动态的。例如，10％或所有键的30％：从该映射值对但随机挑选的。不能使用C ++ 11。

做这个的最好方式是什么？

谢谢。

Answer 1

• 初始化的bool的向量是大小作为地图相同
• 计算T = map.size() * percentage
• Initiale向量的前T个元素为“真”，其余的假
• 随机洗牌的矢量元素
• 迭代器中的地图和矢量超过一起 - 指定在地图中的项目时在矢量中的对应索引位置是真实的

示例代码：

#include <iostream>
#include <map>
#include <vector>
#include <string>

using namespace std;

void getRandomMapElements(map<string, int>& items, double percentage)
{
    const size_t count = items.size();
    vector<bool> vec;
    vec.resize(count); // all items in vec are "false"

    if (percentage < 0)
    {
        percentage = 0;
    }
    else if (percentage > 1.0)
    {
        percentage = 1.0;
    }

    size_t target = (size_t)(count * percentage); // actual number of items extracted

    // fill up the first TARGET count elements of the vector with true, the rest are kept at false
    for (size_t i = 0; i < target; i++)
    {
        vec[i] = true;
    }

    // shuffle the boolean vector
    for (size_t i = 0; i < count; i++)
    {
        bool val = vec[i];
        size_t swap = rand() % count;
        vec[i] = vec[swap];
        vec[swap] = val;
    }

    // iterate over the vector and map together
    map<string, int>::iterator itor = items.begin();
    for (size_t i = 0; i < count; i++)
    {
        if (vec[i])
        {
            cout << itor->first << " : " << itor->second << endl;
        }
        itor++;
    }
}

Answer 2

随着C ++ 17 std::sample不正是你所需要的，但对于C ++ 98它是稍微复杂一些。

即用C ++ 98是兼容的最短代码：

unsigned pick_below(unsigned n)
{
     // poor distribution:
     return std::rand() % n;
}
std::vector<std::pair<std::string, int> >
sample(const std::map<std::string, int> & data_in,
       unsigned p)
{
 std::vector<std::pair<std::string, int> > shuffled(data_in.begin(), data_in.end());
 for (unsigned i=shuffled.size()  ; i > 1 ; --i)
   std::swap(shuffled[i-1], shuffled[pick_below(i)]);
 shuffled.erase(shuffled.begin() +p, shuffled.end());
}

此代码是在两个层面上有问题的：

1. std::random质量没有保证。
2. 使用modulo in pick_below distorts the distribution。

为了解决问题，2号，要么使用boost::random::uniform_int_distribution或根据pick_below改写this功能：

unsigned pick_below(unsigned n)
{
    unsigned x;
    do {
       x = rand();
    } while (x >= (RAND_MAX - RAND_MAX % n));
    return x % n;
}

修复问题1可以通过使用第三方随机生成如boost::random::mt19937来克服。

不幸的是，这种解决方案的复杂性平均为（因为pick_below不能保证终止为O（n），但任何值p < RAND_MAX / 2概率迭代它超过K次呈指数减小到小于0.5K，其复杂不能比为O（n）更好，因为没有办法来接地图的第k个元素，短迭代的全部。