地圖中的隨機元素

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. 洗牌矢量。

在僞代碼（它直接反映了其下面的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預先構建的地圖和快速隨機查找的主題：代替向量我們可以使用迭代器的並行映射，這應該加快隨機查找的速度。

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

如果您的地圖是靜態的，則不是地圖，使用矢量來存儲關鍵爲了您的鍵/值對，二進制搜索來查找值的log（n）時間，以及向量索引以恆定的時間獲得隨機對。您可以將矢量/二進制搜索包裝爲具有隨機訪問功能的地圖。

Answer 8

有沒有人試過嗎？ https://github.com/mabdelazim/Random-Access-Map 「隨機訪問地圖C++模板類。這就好比的std ::地圖，但你可以通過索引語法my_map.key（i）和my_map.data（我）訪問隨機物品」