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

Ответ 1

Используйте boost::container::flat_set вместо:

boost::container::flat_set<int> set;
// ...
auto it = set.begin() + rand() % set.size();

Вставки и удаления становятся O (N), хотя я не знаю, была ли эта проблема. У вас все еще есть O (log N) lookups, и тот факт, что контейнер является непрерывным, дает общее улучшение, которое часто перевешивает потерю O (log N) вставок и исключений.

Ответ 2

Как насчет предиката для find (или lower_bound), который вызывает случайный обход дерева? Вы должны были бы рассказать об этом размеру набора, чтобы он мог оценить высоту дерева и иногда заканчиваться перед листовыми узлами.

Изменить: я понял, что проблема заключается в том, что std::lower_bound берет предикат, но не имеет никакого древовидного поведения (внутри он использует std::advance, который обсуждается в комментариях другого ответа). std::set<>::lower_bound использует предикат набора, который не может быть случайным и по-прежнему иметь поведение типа.

Aha, вы не можете использовать другой предикат, но вы можете использовать изменяемый предикат. Поскольку 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 искать нежелательные шаблоны.

Ответ 3

Если вы можете получить доступ к базовому красно-черному дереву (при условии, что он существует), вы можете получить доступ к случайному node в O (log n), выбрав L/R в качестве последовательных бит ceil(log2(n)) -битного случайного целое число. Однако вы не можете, так как базовая структура данных не отображается стандартом.

Решение Xeo размещения итераторов в векторе - это O (n) время и пространство для настройки, но амортизированная постоянная в целом. Это выгодно отличается от std::next, что является временем O (n).

Ответ 4

Вы можете использовать метод 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);

Ответ 5

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

Другой подход, как видно из комментария, состоит в том, чтобы сохранить вектор итераторов в набор (они только недействительны при удалении элемента для set s) и случайным образом выбирают итератор.

Наконец, если вам не нужен набор на основе дерева, вы можете использовать vector или deque в качестве основного контейнера и sort/unique-ify при необходимости.

Ответ 6

Вы можете сделать это, поддерживая нормальный массив значений; когда вы вставляете в набор, вы добавляете элемент в конец массива (O (1)), тогда, когда вы хотите сгенерировать случайное число, вы можете захватить его из массива в O (1).

Проблема возникает, когда вы хотите удалить элементы из массива. Самый наивный метод займет O (n), что может быть достаточно эффективным для ваших нужд. Однако это можно улучшить до O (log n), используя следующий метод:

Сохраняйте для каждого индекса i в массиве prfx[i], который представляет количество неиспользуемых элементов в диапазоне 0...i в массиве. Сохраните дерево сегментов, где вы сохраняете максимальный prfx[i], содержащийся в каждом диапазоне.

Обновление дерева сегментов можно выполнить в O (log n) за удаление. Теперь, когда вы хотите получить доступ к случайному числу, вы запрашиваете дерево сегментов, чтобы найти "реальный" индекс числа (путем поиска самого раннего диапазона, в котором максимальный prfx равен случайному индексу). Это делает генерацию случайных чисел сложной O (log n).