Выберите случайный элемент в unordered_map

Question

Выберите случайный элемент в unordered_map

Я определяю unordered_map как это:

std::unordered_map<std::string, Edge> edges;

Есть ли эффективный способ выбрать случайное ребро из ребра unordered_map?

12

c++prims-algorithm

Решение

Другие решения

Есть ли эффективный способ выбрать случайное ребро из ребра unordered_map?

Если под эффективностью вы подразумеваете O (1), то нет, это невозможно.

Поскольку итераторы возвращены unordered_map::begin / end являются ForwardIteratorс, подходы, которые просто используют std::advance O (n) в количестве элементов.

Если ваше конкретное использование позволяет, вы можете обменять некоторую случайность на эффективность:

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

int bucket, bucket_size;
do
{
bucket = rnd(edges.bucket_count());
}
while ( (bucket_size = edges.bucket_size(bucket)) == 0 );

auto element = std::next(edges.begin(bucket), rnd(bucket_size));

куда rnd(n) возвращает случайное число в диапазоне [0, n).

На практике, если у вас есть приличный хэш, большинство блоков будет содержать ровно один элемент, в противном случае эта функция будет слегка отдавать предпочтение элементам, которые находятся в их сегментах.

9

Вот как вы можете получить случайный элемент с карты:

std::unordered_map<std::string, Edge> edges;
iterator item = edges.begin();
int random_index = rand() % edges.size();
std::advance(item, random_index);

Или посмотрите на этот ответ, который обеспечивает следующее решение:

std::unordered_map<std::string, Edge> edges;
iterator item = edges.begin();
std::advance( item, random_0_to_n(edges.size()) );

5

Строгое решение O (1) без ведер:

Сохраняйте вектор ключей, когда вам нужно получить случайный элемент с карты, выбрать случайный ключ из вектора и вернуть соответствующее значение с карты — занимает постоянное время
Если вы вставляете пару ключ-значение в карту, проверьте, существует ли такой ключ, и если это не так, добавьте этот ключ к вашему вектору ключей — это займет постоянное время
Если вы хотите удалить элемент с карты после того, как он был выбран, поменяйте ключ, который вы выбрали, с элементом back () вашего ключевого вектора и вызовите pop_back (), после этого удалите элемент с карты и верните значение — принимает постоянное время

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

1

Источник

Accepted Answer

Решение до C ++ 11:

std::tr1::unordered_map<std::string, Edge> edges;
std::tr1::unordered_map<std::string, Edge>::iterator random_it = edges.begin();
std::advance(random_it, rand_between(0, edges.size()));

C ++ 11 и далее:

std::unordered_map<std::string, Edge> edges;
auto random_it = std::next(std::begin(edges), rand_between(0, edges.size()));

Функция, которая выбирает действительное случайное число, зависит от вашего выбора, но убедитесь, что она возвращает число в диапазоне [0 ; edges.size() - 1] когда edges не пусто

std::next функция просто оборачивает std::advance функционировать таким образом, что позволяет прямое назначение.

17