Phần tử ngẫu nhiên trong bản đồ

Question

cách tốt nhất để chọn yếu tố ngẫu nhiên từ bản đồ là gì? C++. Đó là sự hiểu biết của tôi rằng các bản đồ không có các trình vòng lặp truy cập ngẫu nhiên. Chìa khóa dài và bản đồ có dân cư thưa thớt.

Answer 1

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

Answer 2

Tôi thích câu trả lời của James nếu bản đồ nhỏ hoặc nếu bạn không cần giá trị ngẫu nhiên rất thường xuyên. Nếu nó lớn và bạn làm điều này thường đủ để làm cho tốc độ quan trọng bạn có thể giữ một vectơ riêng biệt của các giá trị khóa để chọn một giá trị ngẫu nhiên.

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

Tất nhiên nếu bản đồ thực sự rất lớn, bạn không thể lưu bản sao tất cả các khóa như thế này. Nếu bạn có thể đủ khả năng nó mặc dù bạn có được lợi thế của tra cứu trong thời gian logarit.

Answer 3

Có thể bạn nên xem xét Boost.MultiIndex, mặc dù lưu ý rằng đó là một chút quá nặng.

Answer 4

Có thể tạo một khóa ngẫu nhiên, sau đó sử dụng lower_bound để tìm khóa gần nhất thực sự chứa.

Answer 5

Đây là trường hợp khi tất cả các mục bản đồ phải được truy cập theo thứ tự ngẫu nhiên.

1. Sao chép bản đồ vào vectơ.
2. Xáo trộn vectơ.

Trong pseudo-code (Nó phản ánh chặt chẽ C sau ++ thực hiện):

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 

Trong 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

Tiếp tục ryan_s chủ đề của bản đồ preconstructed và tra cứu ngẫu nhiên nhanh: thay vì vector chúng ta có thể sử dụng một bản đồ song song của các trình vòng lặp, điều này sẽ giúp tăng tốc độ tra cứu ngẫu nhiên một chút.

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

Nếu bản đồ của bạn tĩnh, thay vì bản đồ, tìm kiếm nhị phân để tra cứu giá trị trong log (n) và chỉ số vectơ để có được các cặp ngẫu nhiên trong thời gian không đổi. Bạn có thể bọc tìm kiếm vectơ/nhị phân để trông giống như một bản đồ có tính năng truy cập ngẫu nhiên.

Answer 8

Có ai đã thử điều này không? https://github.com/mabdelazim/Random-Access-Map "C++ template lớp cho bản đồ truy cập ngẫu nhiên. Đây là giống như std :: bản đồ nhưng bạn có thể truy cập vào mục ngẫu nhiên bởi chỉ số với my_map.key cú pháp (i) và my_map.data (i)"