45

マップからランダムな要素を選択する良い方法は何ですか? C++. マップにはランダム アクセス イテレータがないことを理解しています。キーは long long で、マップはまばらに入力されています。

4

9 に答える 9

47 
map<...> MyMap;
iterator item = MyMap.begin();
std::advance( item, random_0_to_n(MyMap.size()) );
于 2008-10-01T17:51:11.830 に答える
16

マップが小さい場合、またはランダムな値が頻繁に必要ない場合は、ジェームズの答えが好きです。それが大きく、速度を重要にするのに十分な頻度でこれを行う場合、ランダムな値を選択するためにキー値の別のベクトルを保持できる場合があります。

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

もちろん、マップが非常に巨大な場合、このようにすべてのキーのコピーを保存できない場合があります。余裕があれば、対数時間でルックアップの利点を得ることができます。

于 2008-10-01T18:10:33.937 に答える
8

ランダムなキーを作成し、lower_boundを使用して、実際に含まれている最も近いキーを見つけることができます。

于 2008-10-01T18:55:03.593 に答える
5

事前構築されたマップと高速なランダム ルックアップという 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())];
于 2008-10-03T23:11:20.173 に答える
2

マップが静的な場合は、マップの代わりにベクトルを使用してキーと値のペアをキーの順序で格納し、バイナリ検索で値を log(n) 時間で検索し、ベクトル インデックスを使用して一定時間でランダムなペアを取得します. ベクトル/バイナリ検索をラップして、ランダム アクセス機能を備えたマップのように見せることができます。

于 2008-10-04T00:17:34.767 に答える
1

Boost.MultiIndexを検討する必要があるかもしれませんが、少し重みが強すぎることに注意してください。

于 2008-10-01T18:28:42.520 に答える
0

これは、すべてのマップ アイテムにランダムな順序でアクセスする必要がある場合です。

  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;
}
于 2008-10-02T18:39:21.907 に答える