Случайный элемент на карте

c++ random map

23704 просмотра

9 ответа

757 Репутация автора

Что такое хороший способ выбрать случайный элемент на карте? C ++. Насколько я понимаю, карты не имеют итераторов произвольного доступа. Ключ длинный, а карта малонаселенная.

Автор: Deathbob Источник Размещён: 01.10.2008 05:45

Ответы (9)


41 плюса

87870 Репутация автора

map<...> MyMap;
iterator item = MyMap.begin();
std::advance( item, random_0_to_n(MyMap.size()) );
Автор: James Curran Размещён: 01.10.2008 05:51

12 плюса

5731 Репутация автора

Мне нравится ответ Джеймса, если карта маленькая или вам не нужно случайное значение очень часто. Если он большой и вы делаете это достаточно часто, чтобы повысить скорость, вы можете сохранить отдельный вектор ключевых значений для выбора случайного значения.

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

Конечно, если карта действительно огромная, вы не сможете сохранить копию всех ключей, как эта. Если вы можете себе это позволить, вы получаете преимущество поиска в логарифмическом времени.

Автор: ryan_s Размещён: 01.10.2008 06:10

1 плюс

1253 Репутация автора

Может быть, вы должны рассмотреть Boost.MultiIndex , хотя обратите внимание, что он слишком тяжелый.

Автор: Weipeng L Размещён: 01.10.2008 06:28

6 плюса

46255 Репутация автора

Возможно, нарисуйте случайный ключ, затем используйте lower_bound, чтобы найти ближайший ключ, который фактически содержится.

Автор: Assaf Lavie Размещён: 01.10.2008 06:55

0 плюса

285602 Репутация автора

Вот случай, когда все элементы карты должны быть доступны в случайном порядке.

  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;
}
Автор: jfs Размещён: 02.10.2008 06:39

4 плюса

22004 Репутация автора

Продолжая тему предварительно построенных карт 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())];
Автор: Constantin Размещён: 03.10.2008 11:11

2 плюса

2616 Репутация автора

Если ваша карта статична, то вместо карты используйте вектор для хранения пар ключ / значение в порядке ключей, двоичный поиск для поиска значений во время log (n) и индекс вектора для получения случайных пар в постоянное время , Вы можете обернуть вектор / двоичный поиск, чтобы он выглядел как карта с функцией произвольного доступа.

Автор: ejgottl Размещён: 04.10.2008 12:17

0 плюса

104 Репутация автора

Кто-нибудь пробовал это? https://github.com/mabdelazim/Random-Access-Map "Шаблонный класс C ++ для карты произвольного доступа. Это похоже на std :: map, но вы можете получить доступ к элементам случайным образом по индексу с помощью синтаксиса my_map.key (i) и my_map .data (я)»

Автор: user3259383 Размещён: 02.12.2016 02:46

0 плюса

28 Репутация автора

std::random_device dev;
std::mt19937_64 rng(dev());

std::uniform_int_distribution<size_t> idDist(0, elements.size() - 1);
auto elementId= elements.begin();
std::advance(elementId, idDist(rng));

Теперь elementId является случайным :)

Автор: Matheus Toniolli Размещён: 01.09.2019 12:48
Вопросы из категории :
32x32