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

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

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

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

Изменить: ограничение не является допустимым временем.

Ответ 1

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

Ответ 2

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

Ответ 3

Если вы знаете распределение элементов в наборе, вы можете случайно выбрать ключ (с тем же распределением) и использовать 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;
}

Ответ 4

Вы можете сделать случайно упорядоченную копию карты с помощью этого конструктора

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

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

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

Ответ 5

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

1) возьмем случайный R в min(s)..max(s)

2) если R в s: return R

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.