Как выбрать случайный элемент в std :: set? - PullRequest
Новая
       34

Как выбрать случайный элемент в std :: set?

29 голосов
/ 16 июня 2010

Как я могу выбрать случайный элемент в std::set?

Я наивно пробовал это: 

int GetSample(const std::set<int>& s) {
  double r = rand() % s.size();
  return *(s.begin() + r); // compile error
}

Но operator+ таким образом не допускается.

Ответы [ 5 ]

44 голосов
/ 16 июня 2010

Вы можете использовать метод std::advance. 

#include <set>
#include <algorithm>

int main() {
  using namespace std;
  // generate a set...
  set<int> s;
  for( int i = 0; i != 10; ++i ) s.insert(i);
  auto r = rand() % s.size(); // not _really_ random
  auto n = *select_random(s, r);
}

Где 

template<typename S>
auto select_random(const S &s, size_t n) {
  auto it = std::begin(s);
  // 'advance' the iterator n times
  std::advance(it,n);
  return it;
}
2 голосов
/ 20 июля 2015

Первое решение: O (log n) во времени / O (1) в пространстве (не равномерно!)

Предположительно в комментарии выше,это можно сделать в O (log (n)) (против O (n) для std::advance) без вектора (используя O (n) больше места) используя описанный мною метод здесь .

По сути, вы:

  • проверяете, является ли набор пустым (если он есть, то нетнадеюсь)
  • сгенерировать случайное значение
  • если уже есть, вернуть его, иначе вставить его
  • получить один итератор it на нем
  • получить случайный элементкак *(it++) или *(set.begin()), если it в конце
  • вернуть его не раньше, чем удалить вставленный элемент

nb: Как указано Аарон элемент не выбран равномерно случайным образом.Вам нужно построить случайный элемент с тем же распределением, что и элементы в наборе, чтобы приблизиться к равномерному опросу.

Второе решение: O (1) во времени / O (n) в пространстве (равномерное)

davidhigh уже дали решение с вектором, но есть проблема, потому что, когда вы pop элемент вашего стека, вам придется выполнить линейный поиск в O (n) , или вы можете перестраивать свой вектор каждый раз, когда хотите получить случайный элемент, но это тоже O (n) .

Чтобы избежать этой проблемы и оставить вставку / удаление на O (log n) , вы можете оставить std::unordered_set и использовать аналогичный метод для первогорешение получить случайный элемент в O (1) .

ps: Если ваши элементы большие, вы можете использовать неупорядоченный набор указателей (с измененным хэшем), чтобы сэкономить часть памяти.

2 голосов
/ 02 июля 2014

Если важен произвольный доступ, и вы можете прожить со средним усилием O (N) для вставки, то обходной путь, приведенный в в этом документе , может быть удобен.

Основная идея заключается в том, чтобы использовать отсортированный вектор, а затем для поиска функцию std::lower_bound. Это, поиск принимает O (log N) так же, как в обычном наборе. Кроме того, (случайная) вставка занимает O (N), поскольку все последующие элементы должны быть сдвинуты так же, как и в нормальном векторе (и, возможно, выполняется перераспределение). Однако вставка сзади постоянна (за исключением перераспределения. Этого можно избежать, вызвав reserve() с достаточно большим хранилищем).

Наконец, основной вопрос: произвольный доступ - это O (1). Просто нарисуйте случайное число i из равномерного распределения в [0, V.size()-1] и верните соответствующий элемент V[i].

Вот кодовая база из бумаги, которая реализует этот отсортированный вектор. Расширьте его по мере необходимости: 

template <class T, class Compare = std::less<T> >
struct sorted_vector {
 using std::vector;
 using std::lower_bound;
 vector<T> V;
 Compare cmp; 
 typedef typename vector<T>::iterator iterator;
 typedef typename vector<T>::const_iterator const_iterator;
 iterator begin() { return V.begin(); }
 iterator end() { return V.end(); }
 const_iterator begin() const { return V.begin(); }
 const_iterator end() const { return V.end(); }

 //...if needed, implement more by yourself

 sorted_vector(const Compare& c = Compare()) : V(), cmp(c) {}
 template <class InputIterator>
 sorted_vector(InputIterator first, InputIterator last, Const Compare& c = Compare())
 : V(first, last), cmp(c)
 {
 std::sort(begin(), end(), cmp);
 }

 //...

 iterator insert(const T& t) {
     iterator i = lower_bound(begin(), end(), t, cmp);
     if (i == end() || cmp(t, *i))
        V.insert(i, t);
      return i;
 }
 const_iterator find(const T& t) const {
     const_iterator i = lower_bound(begin(), end(), t, cmp);
      return i == end() || cmp(t, *i) ? end() : i;
 }
};

Для более сложной реализации, вы также можете рассмотреть эту страницу .

РЕДАКТИРОВАТЬ: или, что еще лучше, использовать boost::container::flat_set, который реализует набор с использованием идеи, описанной выше, то есть в качестве отсортированного вектора.

1 голос
/ 16 июня 2010 
int GetSample(const std::set<int>& s) {
  double r = rand() % s.size();
  std::set<int>::iterator it = s.begin();
  for (; r != 0; r--) it++;
  return *it;
}

будет одним из способов сделать это, хотя и не очень;

0 голосов

C ++ 17 std::sample

Это будет удобный, хотя и не очень эффективный (O (n)) метод: 

#include <algorithm>
#include <iostream>
#include <random>
#include <set>
#include <vector>

int main() {
    std::set<int> in{1, 2, 3, 5, 7};
    std::vector<int> out;
    std::sample(in.begin(), in.end(), std::back_inserter(out),
                3, std::mt19937{std::random_device{}()});
    for (auto i : out)
        std::cout << i << std::endl;
}

Но я думаю, что для эффективности вам просто нужно скопировать структуру другого типа: Как выбрать случайный элемент в std :: set менее чем за O (n) раз?

...