Как эффективно выбрать случайный элемент из std :: set
Как я могу эффективно выбрать случайный элемент из std::set?
std::set::iterator является не итератор с произвольным доступом. Поэтому я не могу напрямую индексировать случайно выбранный элемент, как я мог бы для std::deque или же std::vector
я мог взять итератор, возвращенный из std::set::begin() и увеличить его 0 в std::set::size()-1 раз, но это, кажется, делает много ненужной работы. Для «индекса», близкого к размеру набора, я бы закончил обход всей первой половины дерева, хотя уже известно, что элемент там не будет найден.
Есть ли лучший подход?
Во имя эффективности я хочу определить «случайный» как менее случайный чем любой другой подход, который я мог бы использовать для выбора случайного индекса в векторе. Назовите это «достаточно случайно».
Редактировать…
Многие проницательные ответы ниже.
Короткая версия заключается в том, что, хотя вы можете найти конкретный элемент в войти (п) время, вы не можете найти произвольный элемент в то время через std::set интерфейс.
Решение
использование boost::container::flat_set вместо:
boost::container::flat_set<int> set;
// ...
auto it = set.begin() + rand() % set.size();
Вставки и удаления становятся O (N), хотя, я не знаю, если это проблема. У вас все еще есть O (log N) поисков, и тот факт, что контейнер является смежным, дает общее улучшение, которое часто перевешивает потерю O (log N) вставок и удалений.
Другие решения
Как насчет предиката для find (или же lower_bound) что вызывает случайный обход дерева? Вы должны сказать ему размер набора, чтобы он мог оценить высоту дерева и иногда заканчиваться перед конечными узлами.
Редактировать: я понял, проблема в том, что это std::lower_bound принимает предикат, но не имеет никакого древовидного поведения (внутренне оно использует std::advance что обсуждается в комментариях другого ответа). std::set<>::lower_bound использует предикат набора, который не может быть случайным и при этом вести себя как набор.
Ага, вы не можете использовать другой предикат, но вы можете использовать изменяемый предикат. поскольку std::set передает объект предиката по значению, которое вы должны использовать predicate & в качестве предиката, чтобы вы могли получить доступ и изменить его (установив его в режим «рандомизации»).
Вот квази-рабочий пример. К сожалению, я не могу обернуть свой мозг вокруг правильного случайного предиката, так что моя случайность не превосходна, но я уверен, что кто-то может понять это:
#include <iostream>
#include <set>
#include <stdlib.h>
#include <time.h>
using namespace std;
template <typename T>
struct RandomPredicate {
RandomPredicate() : size(0), randomize(false) { }
bool operator () (const T& a, const T& b) {
if (!randomize)
return a < b;
int r = rand();
if (size == 0)
return false;
else if (r % size == 0) {
size = 0;
return false;
} else {
size /= 2;
return r & 1;
}
}
size_t size;
bool randomize;
};
int main()
{
srand(time(0));
RandomPredicate<int> pred;
set<int, RandomPredicate<int> & > s(pred);
for (int i = 0; i < 100; ++i)
s.insert(i);
pred.randomize = true;
for (int i = 0; i < 100; ++i) {
pred.size = s.size();
set<int, RandomPredicate<int> >::iterator it = s.lower_bound(0);
cout << *it << endl;
}
}
Мой полуиспеченный тест случайности ./demo | sort -u | wc -l чтобы увидеть, сколько уникальных целых чисел я получаю. С большим набором образцов попробуйте ./demo | sort | uniq -c | sort -n искать нежелательные шаблоны.
Если вы можете получить доступ к базовому красно-черному дереву (при условии, что оно существует), затем вы можете получить доступ к случайному узлу в O (log n), выбрав L / R в качестве последовательных битов ceil(log2(n))случайное целое число Однако вы не можете этого сделать, так как базовая структура данных не представлена стандартом.
Решение Xeo по размещению итераторов в векторе — это O (n) время и пространство для настройки, но в целом амортизированная константа. Это выгодно отличается от std::next, что является O (N) время.
Вы можете использовать std::advance метод:
set <int> myset;
//insert some elements into myset
int rnd = rand() % myset.size();
set <int> :: const_iterator it(myset.begin());
advance(it, rnd);
//now 'it' points to your random element
Другой способ сделать это, вероятно, менее случайный:
int mini = *myset().begin(), maxi = *myset().rbegin();
int rnd = rand() % (maxi - mini + 1) + mini;
int rndresult = *myset.lower_bound(rnd);
Если или набор не обновляется часто, или вам не нужно часто запускать этот алгоритм, сохраните зеркальную копию данных в vector (или просто скопируйте набор в вектор по необходимости) и выберите случайным образом из этого.
Другой подход, как видно из комментария, заключается в сохранении вектора итераторов в наборе (они становятся недействительными только при удалении элемента для sets) и случайным образом выбрать итератор.
Наконец, если вам не нужен набор на основе дерева, вы можете использовать vector или же deque в качестве основного контейнера и сортируйте / unique-ify, когда это необходимо.
Вы можете сделать это, поддерживая нормальный массив значений; когда вы вставляете в набор, вы добавляете элемент в конец массива (O (1)), затем, когда вы хотите сгенерировать случайное число, вы можете получить его из массива в O (1) также.
Проблема возникает, когда вы хотите удалить элементы из массива. Самый наивный метод займет На), который может быть достаточно эффективным для ваших нужд. Тем не менее, это может быть улучшено до O (log n) используя следующий метод;
Сохранить для каждого индекса i в массиве, prfx[i], который представляет количество не удаленных элементов в диапазоне 0...i в массиве. Держите дерево сегментов, где вы держите максимум prfx[i] содержится в каждом диапазоне.
Обновление дерева сегментов можно выполнить в O (log n) за удаление. Теперь, когда вы хотите получить доступ к случайному числу, вы запрашиваете дерево сегментов, чтобы найти «реальный» индекс числа (находя самый ранний диапазон, в котором максимальное prfx равен случайному индексу). Это делает сложность случайных чисел O (log n).