Случайный элемент из unordered_set в O (1)

std::unordered_set не предоставлять итератор произвольного доступа. Я предполагаю, что это выбор дизайнеров stl, чтобы дать реализаторам stl больше свободы … базовая структура должна поддерживать вставку и удаление O (1), но не должна поддерживать произвольный доступ. Например, вы можете кодировать stl-совместимый unordered_set в виде двусвязного списка, даже если невозможно кодировать итератор произвольного доступа для такого базового контейнера.

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

Я могу подумать о «взломе», если вы можете создать случайный элемент value_type в O (1) … Вот идея:

1. отметьте неупорядоченный набор в непустом (если он есть, надежды нет)
2. генерировать случайный элемент value_type
3. если уже в неупорядоченном наборе вернуть его, то еще вставить
4. получить итератор it на этом элементе
5. получить случайный элемент как *(it++) (и если *it последний элемент получить первый элемент)
6. удалить вставленный элемент и вернуть значение в (5)

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

Н.Б .: Пятый шаг, хотя и очень странный, также важен … потому что, например, если вы получаете случайный элемент как it++ (а также it-- если it является последним итератором), тогда первый элемент будет в два раза менее вероятным, чем другие (не тривиально, но подумайте об этом …). Если вас не интересует искажение дистрибутива, это нормально, вы можете просто получить передний элемент.

std::unordered_set не имеет O (1) произвольного доступа в смысле массива. Можно получить доступ к элементу на основе ключа в O (1), но невозможно найти k-й элемент.

Несмотря на это, вот способ получить случайный элемент с равномерным распределением из std::unordered_map (или с std::unordered_set если ключ имеет изменяемое поле). Я выложил похожую технику в ответе на вопрос SO Структура (-и) данных, допускающая изменение посредством итерации и случайного выбора из подмножества (C ++).

Идея состоит в том, чтобы дополнить каждую запись в std::unordred_set с изменяемым значением индекса в вектор указателей в unordered_set, Размер вектора равен размеру unordered_set, Каждый раз, когда новый элемент вставляется в unordered_setуказатель на этот элемент push_backв векторе. Каждый раз, когда элемент удаляется из unodrered_set, соответствующая запись в векторе находится в O (1) и заменяется на back() элемент вектора. Индекс ранее back() элемент изменен, и теперь указывает на его новое местоположение в векторе. Наконец старая запись pop_back()-ed из вектора.

Этот вектор точно указывает на все элементы в unordered_set, Требуется O (1), чтобы выбрать случайный элемент из объединенной структуры в равномерном распределении. Требуется O (1), чтобы добавить или стереть элемент в объединенной структуре.

ПРИМЕЧАНИЕ. Указатели на элементы (в отличие от итераторов) гарантированно остаются действительными, пока элемент существует.

Вот как это должно выглядеть:

Для стирания элемента c:

1. Поменяйте местами элементы c_index и a_index и закрепите на них указатели:
2. pop_back последний элемент, который является element_c из вектора.
3. стереть с из unordred_set,

Рандомизация тривиальна — просто выберите элемент случайным образом из вектора.

Я написал решение, используя методы buck_count () и cbegin (n), чтобы выбрать случайный сегмент, а затем выбрать случайный элемент в сегменте.

Две проблемы:
— это не постоянное время (в худшем случае много пустых корзин и много элементов в одной корзине)
— распределение вероятностей искажено

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

#include <random>
#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <cassert>

using namespace std;

ranlux24_base randomEngine(5);

int rand_int(int from, int to)
{
assert(from <= to);

return uniform_int_distribution<int>(from, to)(randomEngine);
}

int random_peek(const unordered_set<int> & container)
{
assert(container.size() > 0);

auto b_count = container.bucket_count();
auto b_idx = rand_int(0, b_count - 1);
size_t b_size = 0;

for (int i = 0; i < b_count; ++i)
{
b_size = container.bucket_size(b_idx);
if (b_size > 0)
break;

b_idx = (b_idx + 1) % b_count;
}

auto idx = rand_int(0, b_size - 1);

auto it = container.cbegin(b_idx);

for (int i = 0; i < idx; ++i)
{
it++;
}

return *it;
}

int main()
{
unordered_set<int> set;

for (int i = 0; i < 1000; ++i)
{
set.insert(rand_int(0, 100000));
}

unordered_map<int,int> distribution;

const int N = 1000000;
for (int i = 0; i < N; ++i)
{
int n = random_peek(set);
distribution[n]++;
}

int min = N;
int max = 0;

for (auto & [n,count]: distribution)
{
if (count > max)
max = count;
if (count < min)
min = count;
}

cout << "Max=" << max << ", Min=" << min << "\n";
return 0;
}