Выбор N случайных чисел из набора

Question

У меня есть отсортированный набор (точнее, std :: set), который содержит элементы с назначенным весом.Я хочу случайным образом выбрать N элементов из этого набора, в то время как элементы с более высоким весом должны иметь большую вероятность выбора.Любой элемент может быть выбран несколько раз.

Я хочу сделать это максимально эффективно - я хочу избежать любого копирования набора (он может стать очень большим) и запускаться во время O (N), есливозможно.Я использую C ++ и хотел бы придерживаться решения только для STL + Boost.

Кто-нибудь знает, есть ли в STL / Boost функция, которая выполняет эту задачу?Если нет, то как его реализовать?

Answer 1

Вам необходимо вычислить (и, возможно, кешировать, если вы думаете о производительности) сумму всех весов в вашем наборе. Затем сгенерируйте N случайных чисел, начиная с этого значения. Наконец, повторите ваш набор, считая сумму весов, с которыми вы столкнулись до сих пор. Осмотрите все (оставшиеся) случайные числа. Если число находится между предыдущим и следующим значением суммы, вставьте значение из набора и удалите случайное число. Остановитесь, если ваш список случайных чисел пуст или вы достигли конца набора.

Answer 2

Я не знаю ни о каких библиотеках, но, похоже, у вас есть весовое колесо рулетки.Вот ссылка с некоторым псевдокодом, хотя контекст связан с генетическими алгоритмами: http://www.cse.unr.edu/~banerjee/selection.htm

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

Answer 3

Многое зависит от объема дополнительной памяти, которую вы готовы потратить, чтобы сделать выбор быстрее.

Если вы не хотите использовать какое-либо дополнительное хранилище, ответ @Alex Emelianov в значительной степени соответствует тому, что я собирался опубликовать. Если вы хотите использовать дополнительное хранилище (и, возможно, структуру данных, отличную от std::set), вы можете создать дерево (как использует набор), но на каждом узле дерева вы также должны хранить (взвешенное) число предметов слева от этого узла. Это позволит вам сопоставить сгенерированное число с правильным ассоциированным значением с логарифмической (а не линейной) сложностью.