Как выбрать случайный элемент в std :: set менее чем за O (n) раз? - PullRequest
Новая
       26

Как выбрать случайный элемент в std :: set менее чем за O (n) раз?

15 голосов
/ 29 ноября 2011

Этот вопрос с добавленным ограничением.

Я готов разрешить неравномерный выбор, если он не является односторонним.

Учитывая, что " наборы обычно реализуются как двоичные деревья поиска ", и я ожидаю, что они будут содержать некоторую информацию о глубине или размере для балансировки, я ожидаю, что вы могли бы сделать какой-то взвешенныйслучайная прогулка по дереву.Однако я не знаю ни одного удаленно переносимого способа сделать это.

Редактировать: ограничение НЕ на амортизированное время.

Ответы [ 5 ]

6 голосов
/ 29 ноября 2011

Ввести массив с размером, равным установленному. Заставить элементы массива содержать адреса каждого элемента в наборе. Генерирует случайное целое число R, ограниченное размером массива / набора, выбирает адрес в элементе массива, проиндексированном R, и разыменовывает его для получения элемента набора.

3 голосов
/ 29 ноября 2011

Я не вижу, как это сделать, просто std::set, поэтому вам, вероятно, нужна другая структура данных.Как сказал Виктор Сорокин, вы можете комбинировать набор с вектором.Вместо set<T> используйте map<T, size_t> плюс vector< map<T, size_t>::iterator >.Значением для каждого ключа является индекс в векторе, а каждый элемент вектора указывает обратно на элемент карты.Векторные элементы не имеют определенного порядка.Когда вы добавляете элемент, поместите его в конец вектора.Когда вы удаляете элемент, который не является последним в векторе, перемещайте последний элемент в позицию удаленного элемента.

1 голос
/ 29 ноября 2011

ЕСЛИ вы знаете распределение элементов в наборе, вы можете случайным образом выбрать ключ (с тем же распределением) и использовать std::set::lower_bound.Хотя это много, если. 

int main() {
    std::set<float> container;
    for(float i=0; i<100; i += .01)  
        container.insert(i);
    //evenish distribution of 10000 floats between 0 and 100.
    float key = std::rand() *10000f / RAND_MAX; //not random, sue me
    std::set<float>::iterator iter = container.lower_bound(key); //log(n)
    std::cout << *iter;
    return 0;
}
0 голосов
/ 11 февраля 2014

Для std::unordered_set<int> s:

1) принять случайным образом R в min(s)..max(s)

2) если R in s: вернуть R

3) 

newIter = s.insert(R).first;
newIter++;
if (newIter == s.end()) {
    newIter = s.begin();
}
auto result = *newIter;
s.erase(R);
return result;

Для упорядоченного множества (std :: set) вероятность будет зависеть от расстояния между элементами. unordered_set рандомизирован по хешу.

Надеюсь, это поможет.

PS преобразование std::set<V> в std::set<std::pair<int, V>> (где первый элемент в паре - хэш второго) делает этот метод подходящим для любого хэшируемого V.

0 голосов
/ 29 ноября 2011

Вы можете создать произвольно упорядоченную копию карты, используя этот конструктор 

template <class InputIterator>
set(InputIterator f, InputIterator l,
    const key_compare& comp)

.. и передавая компаратор, который сравнивает хеш-коды ключей (или какую-либо другую детерминированную функцию расширения.) Затем возьмите «самые маленькие» ключи в соответствии с этой новой картой.

Вы можете создать карту один раз и амортизировать стоимость по нескольким запросам на «случайный» элемент.

...