una - palabras aleatorias en c++

Elemento aleatorio en un mapa

Question

¿Cuál es una buena forma 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

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

Answer 2

Continuando con el tema de ryan_s de los mapas preconstruidos y la búsqueda aleatoria rápida: en lugar de 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 3

Este es el caso cuando todos los elementos del mapa deben tener acceso en orden aleatorio.

1. Copia el mapa a un vector.
2. Mezclar vector.

En pseudo-código (refleja de cerca la implementación de C ++ siguiente):

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 4

Me gusta la respuesta de James si el mapa es pequeño o si no necesitas un valor aleatorio muy a menudo. Si es grande y lo hace con la frecuencia suficiente para que la velocidad sea importante, es posible que pueda mantener un vector separado de valores clave para seleccionar un valor aleatorio.

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 grande, es posible que no pueda almacenar una copia de todas las claves como esta. Si puede pagarlo, obtendrá la ventaja de las búsquedas en tiempo logarítmico.

Answer 5

Si su mapa es estático, en lugar de un mapa, use un vector para almacenar sus pares clave / valor en orden clave, búsqueda binaria para buscar valores en tiempo log (n) y el índice vectorial 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 6

Tal vez deberías considerar Boost.MultiIndex , aunque ten en cuenta que es un poco demasiado pesado.

Answer 7

Tal vez elabore una clave aleatoria, luego use lower_bound para encontrar la clave más cercana realmente contenida.

Answer 8

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