Случайный элемент на карте

Question

Что такое хороший способ выбора случайного элемента с карты? C++. Насколько я понимаю, на картах нет итераторов с произвольным доступом. Ключ длинный, а карта малонаселенная.

Answer 1

map<...> MyMap; 
iterator item = MyMap.begin(); 
std::advance(item, random_0_to_n(MyMap.size())); 

Answer 2

Мне нравится ответ Джеймса, если карта мала или вам не нужно случайное значение очень часто. Если он большой, и вы делаете это достаточно часто, чтобы сделать скорость важной, вы можете сохранить отдельный вектор значений ключа, чтобы выбрать случайное значение.

map<...> MyMap; 
vector<...> MyVecOfKeys; // <-- add keys to this when added to the map. 

map<...>::key_type key = MyVecOfKeys[ random_0_to_n(MyVecOfKeys.size()) ]; 
map<...>::data_type value = MyMap[ key ]; 

Конечно, если карта действительно огромна, возможно, вы не сможете сохранить копию всех ключей, подобных этому. Если вы можете себе это позволить, хотя вы получаете преимущество поиска в логарифмическом времени.

Answer 3

Возможно, вам стоит рассмотреть Boost.MultiIndex, хотя учтите, что он слишком тяжелый.

Answer 4

Возможно, нарисуйте случайный ключ, затем используйте lower_bound, чтобы найти ближайший ключ, фактически содержащийся.

Answer 5

В этом случае все Элементы карты должны быть доступны в случайном порядке.

1. Скопируйте карту в вектор.
2. Shuffle вектор.

В псевдокоде (Это точно отражает следующие C++ реализации):

import random 
import time 

# populate map by some stuff for testing 
m = dict((i*i, i) for i in range(3)) 
# copy map to vector 
v = m.items() 
# seed PRNG 
# NOTE: this part is present only to reflect C++ 
r = random.Random(time.clock()) 
# shuffle vector  
random.shuffle(v, r.random) 
# print randomized map elements 
for e in v: 
    print "%s:%s" % e, 
print 

В C++:

#include <algorithm> 
#include <iostream> 
#include <map> 
#include <vector> 

#include <boost/date_time/posix_time/posix_time_types.hpp> 
#include <boost/foreach.hpp> 
#include <boost/random.hpp> 

int main() 
{ 
    using namespace std; 
    using namespace boost; 
    using namespace boost::posix_time; 

    // populate map by some stuff for testing 
    typedef map<long long, int> Map; 
    Map m; 
    for (int i = 0; i < 3; ++i) 
    m[i * i] = i; 

    // copy map to vector 
#ifndef OPERATE_ON_KEY 
    typedef vector<pair<Map::key_type, Map::mapped_type> > Vector; 
    Vector v(m.begin(), m.end()); 
#else 
    typedef vector<Map::key_type> Vector; 
    Vector v; 
    v.reserve(m.size()); 
    BOOST_FOREACH(Map::value_type p, m) 
    v.push_back(p.first); 
#endif // OPERATE_ON_KEY 

    // make PRNG 
    ptime now(microsec_clock::local_time()); 
    ptime midnight(now.date()); 
    time_duration td = now - midnight; 
    mt19937 gen(td.ticks()); // seed the generator with raw number of ticks 
    random_number_generator<mt19937, 
    Vector::iterator::difference_type> rng(gen); 

    // shuffle vector 
    // rng(n) must return a uniformly distributed integer in the range [0, n) 
    random_shuffle(v.begin(), v.end(), rng); 

    // print randomized map elements 
    BOOST_FOREACH(Vector::value_type e, v) 
#ifndef OPERATE_ON_KEY 
    cout << e.first << ":" << e.second << " "; 
#else 
    cout << e << " "; 
#endif // OPERATE_ON_KEY 
    cout << endl; 
} 

Answer 6

сохраняющейся ryan_s тема preconstructed карты и быстрого случайного поиска: вместо vector мы можем использовать параллельное отображение итераторов, которое должно ускорить случайный поиск.

map<K, V> const original; 
... 

// construct index-keyed lookup map 
map<unsigned, map<K, V>::const_iterator> fast_random_lookup; 
map<K, V>::const_iterator it = original.begin(), itEnd = original.end(); 
for (unsigned i = 0; it != itEnd; ++it, ++i) { 
    fast_random_lookup[i] = it; 
} 

// lookup random value 
V v = *fast_random_lookup[random_0_to_n(original.size())]; 

Answer 7

Если ваша карта является статическим, то вместо карты, использовать вектор для хранения пар ключ/значение в порядке ключа, двоичный поиск для поиска значения в журнале (п), а индекс вектора для получения случайных пар в постоянное время. Вы можете обернуть векторный/бинарный поиск, чтобы он выглядел как карта со случайным доступом.

Answer 8

Кто-нибудь пробовал это? https://github.com/mabdelazim/Random-Access-Map «C++ шаблон класса для отображения произвольного доступа. Это похоже на станде :: карту, но вы можете получить доступ к элементам случайного индекса с синтаксисом my_map.key (I) и my_map.data (I)»