hashtable — Как случайным образом извлечь элемент из хеш-таблицы C ++ в O (1)
Есть ли способ случайного получения элемента из C ++ unordered_set в O (1) среднее время? Вместо того чтобы делать
std::unordered_set<int> s;
// initialize s
auto start = s.begin();
for (int i = 0; i < rand()%s.size()-1; ++i, ++start) {}
int randomNumber = *start;
Обновлено:
Мне нужно бороться за пост, поэтому я добавляю причины, по которым мне нужно было работать выше.
Я играю с реализацией генератора лабиринта. И как-то мне нужна структура данных, которая будет поддерживать:
- вставка / удаление в O (1)
- случайное извлечение элемента из структуры данных в O (1)
станд :: вектор имеет произвольный доступ, но вставка / удаление стоит дорого
станд :: список не имеет произвольного доступа
станд :: набор поддержка O (logN) произвольного доступа и O (logN) вставка / удаление, которые хороши, но моя инициализация представляет собой отсортированную последовательность, которая легко нарушит его баланс.
Поэтому я подумал, что хеш-таблица будет лучшим выбором, однако случайный поиск элемента будет нетривиальным.
Спасибо за ваше время.
Решение
Вы не можете выбрать случайный элемент из unordered_set в O (1) раз. Итераторы ForwardIteratorс не RandomAccessIterators. Вы должны будете использовать другой контейнер. Или boost::container::flat_set<int> или написать свой собственный, который также имеет что-то вроде vector внутренне:
template <typename T>
class set_with_random_access
{
std::vector<T*> vec;
std::unordered_set<T> set;
};
Для которых мы предоставляем функции, которые держат их в строке, такие как вставка:
void insert(const T& value) {
auto pr = set.insert(value);
if (pr.second) {
vec.push_back(&*pr.first);
}
}
И случайность:
template <typename GEN>
T& random(GEN& gen) {
std::uniform_int_distribution<size_t> dist(0, vec.size() - 1);
return *vec[dist(gen)];
}
Который, честно говоря, много работы, так что, вероятно, использовать повышение.
Другие решения
способ случайного получения элемента из C ++
unordered_setв O (1) среднее время?
Зависит от того, что считать «случайным» для ваших целей, и достаточно ли того, чтобы быть крошечным пятном над O (1). Вы можете выбрать случайное ведроb«между 0 а также s.bucket_count() - 1, повторяя, если корзина пуста, тогда индекс списка li между 0 а также s.bucket_size(b) - 1, затем std::advance(s.begin(li)) чтобы получить итератор для «случайного» элемента, но рассмотрим следующую ситуацию:
Вы бросаете три кубика, а затем случайным образом выбираете один из них: вы получаете случайное значение 1-6 с четной вероятностью, но если вы продолжаете выбирать без повторного броска, вы можете получить только те значения, которые оказались на трех кубиках: Вероятности каждого значения от 1 до 6 сильно неравномерны.
Вышеупомянутый подход к выбору случайного элемента в unordered_set немного так: если есть x ведра с элементами, то у каждого ведра есть равный шанс быть выбранным, но элементы в этом ведре имеют 1 / x / bucket_size() вероятность выбора, которая — для любого данного сегмента — может быть меньше или больше 1 / size(), Другими словами, если вы считаете хеширование практически случайным, то различные элементы имеют равные шансы на то, чтобы их одобрили или оштрафовали при их размещении, но этот «перекос» затем ставит его камнями до тех пор, пока данные таблицы не будут значительно видоизменены или таблица не будет перефразирована (и если он перефразируется, скажем, с удвоением размера таблицы, а не с большим простым числом (смутная память, unordered_set удваивается), то одноразовые штрафы будут иметь тенденцию оставаться штрафуемыми половину времени).
Приведенная выше эффективность big-O представляет собой крошечное пятно над O (1), потому что:
-
в начальном тесте есть некоторое повторение, чтобы найти корзину с элементами, но с коэффициентом загрузки 1,0 вряд ли потребуется больше, чем пара попыток (учитывая хорошую хэш-функцию); доступны и другие варианты — например, итерация из пустого сегмента или прыжок при различных смещениях (в зависимости от размера таблицы) — который может работать немного лучше, чем пробовать другой полностью случайный интервал, но также может усугубить расхождения в шансах выбора элемента
-
есть линейная итерация в элементах, сталкивающихся в любом конкретном сегменте, но, поскольку коэффициент загрузки по умолчанию равен 1,0, будет редко иметь более пары столкновений, и все более и более крайне редко будет иметь намного больше, чем это.
Выбор случайного элемента из std::unordered_set плохая идея Это связано с тем, что std::unordered_set не поддерживает произвольный доступ и, следовательно, не имеет оператора индексации (т.е. operator[]).
Я твердо верю, что вам нужно это std::vector в сочетании с std::unique чтобы удовлетворить уникальность элемента.
В приведенном ниже примере я использую std::vector и тогда я гарантирую, что он имеет только уникальные элементы, применяя std::unique алгоритм на нем. Тогда я использую random утилиты для генерации случайного индекса в [0, размер вектора — 1]:
std::vector<int> v{1, 2, 8, 3, 5, 4, 5, 6, 7, 7, 9, 9, 19, 19};
v.erase(std::unique(v.begin(), v.end()), v.end());
std::default_random_engine generator;
std::uniform_int_distribution<int> distribution(0, v.size() - 1);
std::cout << "Random number from vector: " << v[distribution(generator)] << std::endl;