elemento aleatorio en un mapa

Question

lo que es una buena manera de seleccionar un elemento aleatorio de un mapa? C++. Tengo entendido que los mapas no tienen iteradores de acceso aleatorio. La clave es larga y el mapa está escasamente poblado.

Answer 1

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

Answer 2

me gusta la respuesta de James si el mapa es pequeño o si no se necesita un valor aleatorio muy a menudo. Si es grande y hacer esto a menudo suficiente para hacer que la velocidad importante que podría ser capaz de mantener un vector separado de los valores clave para seleccionar un valor aleatorio a partir.

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 ]; 

Por supuesto, si el mapa es realmente enorme que podría no ser capaz de almacenar una copia de todas las claves de este tipo. Si puede pagarlo, obtendrá la ventaja de las búsquedas en tiempo logarítmico.

Answer 3

Tal vez usted debería considerar Boost.MultiIndex, aunque nota que es un poco demasiado pesada ponderado.

Answer 4

Tal elaborar una clave aleatoria, a continuación, utilizar lower_bound para encontrar la clave más cercana realidad contenida.

Answer 5

Aquí está el caso cuando todos los elementos del mapa deben tener acceso en orden aleatorio.

1. Copie el mapa en un vector.
2. vector aleatoria.

En pseudo-código (Se refleja estrechamente la siguiente implementación en 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 

En 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

tema Continua ryan_s de mapas preconstruidos y las operaciones de búsqueda aleatorio rápido: en lugar de En el vector podemos usar un mapa paralelo de iteradores, lo que debería acelerar un poco la búsqueda aleatoria.

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

Si el mapa es estático, entonces en vez de un mapa, usar un vector para almacenar sus pares clave/valor en un orden clave, búsqueda binaria para buscar valores en log (n) el tiempo, y el índice del vector para obtener pares aleatorios en tiempo constante. Puede ajustar la búsqueda vectorial/binaria para que parezca un mapa con una función de acceso aleatorio.

Answer 8

Alguien ha probado esto? https://github.com/mabdelazim/Random-Access-Map "++ clase de plantilla C para obtener un mapa de acceso aleatorio. Esto es como el std :: mapa, pero se puede acceder a los elementos al azar por el índice con my_map.key sintaxis (i) y my_map.data (i)"