Losowy element mapie

Question

co jest dobrym sposobem, aby zaznaczyć element losowy z mapy? C++. Rozumiem, że mapy nie mają iteratorów z dostępem swobodnym. Klucz jest długi, a mapa słabo zaludniona.

Answer 1

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

Answer 2

Podoba mi się odpowiedź Jamesa, jeśli mapa jest mała lub jeśli nie trzeba często wybierać losowej wartości. Jeśli jest duży i robisz to wystarczająco często, aby prędkość była ważna, możesz zachować oddzielny wektor kluczowych wartości, aby wybrać losową wartość.

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

Oczywiście, jeśli mapa jest naprawdę duża, możesz nie być w stanie przechowywać kopii wszystkich kluczy w tym stylu. Jeśli możesz sobie na to pozwolić, choć masz przewagę wyszukiwania w logarytmicznym czasie.

Answer 3

Może należy rozważyć Boost.MultiIndex, choć pamiętać, że jest to trochę zbyt ciężki ważony.

Answer 4

Może sporządzić losowy klucz, a następnie użyć lower_bound aby znaleźć najbliższy klucz rzeczywiście zawarty.

Answer 5

Oto przypadek, gdy elementy mapy muszą być dostępne w kolejności losowej.

1. Skopiuj mapę do wektora.
2. wektor Shuffle.

W pseudo-kod (Jest ściśle odzwierciedla następujące C++ realizacji):

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 

w 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

Kontynuując ryan_s tematem preconstructed map i szybkiego losowego odnośnika: zamiast wektor możemy użyć równoległej mapy iteratorów, co powinno przyspieszyć losowe wyszukiwanie.

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

Jeśli mapa jest statyczna, a następnie zamiast mapy, użyj wektor do przechowywania par klucz/wartość, aby klucz, wyszukiwania binarnego zajrzeć do wartości log (n) oraz indeks wektor aby uzyskać losowe pary w stałym czasie. Możesz zawęzić wyszukiwanie wektorowe/binarne, aby wyglądało jak mapa z funkcją dostępu losowego.

Answer 8

Czy ktoś próbował tego? https://github.com/mabdelazim/Random-Access-Map „C++ klasa szablon dla dostępie swobodnym mapie. To jest jak std :: map, ale można uzyskać dostęp do elementów losowych przez indeks z my_map.key składni (i) i my_map.data (I)”