Выбор процента случайных элементов в карте C ++

Question

У меня есть карта C ++: std::map <std::string, int>

Я бы хотел выбрать p процент случайных элементов на этой карте.Здесь p является динамическим.Например, 10% или 30% всех пар ключ: значение на этой карте, но выбраны случайным образом.Не могу использовать c ++ 11.

Каков наилучший способ сделать это?

Спасибо.

Answer 1

С 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. использование по модулю в pick_below искажает распределение .

Чтобы преодолеть проблему номер 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.

К сожалению, сложность этого решения в среднем составляет O (n) (поскольку pick_below не гарантированно завершится, но при любом значении p < RAND_MAX / 2 вероятность его повторения более K раз экспоненциально уменьшается доменьше, чем 0,5 ^K . Сложность не может быть лучше, чем O (n), поскольку нет способа выбрать элемент * k ^th карты, если не выполнять итерацию всего этого.

Answer 2

• Инициализирует вектор bool того же размера, что и карта.
• compute T = map.size() * percentage
• Инициализирует первые T элементов вектора как "true", остальныеfalse
• случайное перемешивание элементов в векторе
• итератор по карте и вектор вместе - обозначают элемент на карте, когда соответствующая позиция индекса в векторе равна true

Пример кода:

#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++;
    }
}