मानचित्र में यादृच्छिक तत्व

Question

मानचित्र से यादृच्छिक तत्व चुनने का एक अच्छा तरीका क्या है? सी ++। यह मेरी समझ है कि मानचित्र में यादृच्छिक अभिगम इटरेटर नहीं हैं। कुंजी एक लंबी लंबी है और नक्शा कम आबादी है।

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. शफल वेक्टर।

   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

preconstructed नक्शे और तेजी से यादृच्छिक देखने के सतत ryan_s विषय: के बजाय वेक्टर हम iterators के समानांतर मानचित्र का उपयोग कर सकते हैं, जो थोड़ा यादृच्छिक लुकअप को तेज करना चाहिए।

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 "सी ++ रैंडम एक्सेस नक्शे के लिए टेम्पलेट वर्ग। यह std :: मानचित्र की तरह है, लेकिन आप वाक्य रचना my_map.key (i) और my_map.data (i) के साथ सूचकांक द्वारा यादृच्छिक आइटम एक्सेस कर सकते"