STL random_sample заменить с уменьшением вероятности
STL random_sample Функция использует стратегию замены для выборки из заданного интервала. Почему нам нужна уменьшающаяся вероятность, я видел похожий алгоритм без уменьшения вероятности замены. В чем разница. Код такой:
/*This is an excerpt from STL implementation*/
template <class InputIterator, class RandomAccessIterator, class Distance>
RandomAccessIterator __random_sample(InputIterator first, InputIterator last,
RandomAccessIterator out,
const Distance n)
{
Distance m = 0;
Distance t = n;
for ( ; first != last && m < n; ++m, ++first) //the strategy is also used in mahout
out[m] = *first;//fill it
while (first != last) {
++t;
Distance M = lrand48() % t;
if (M < n)
out[M] = *first;//replace it with a decreasing probability
++first;
}
return out + m;
}
Решение
Очевидно, что первый элемент (действительно, первый n элементы) должен быть выбран с вероятностью 1 (этап «заполните это»). Чтобы остаться в окончательном образце, этот первый элемент должен затем выжить m-n возможные замены — это то, что снижает вероятность того, что он будет в образце n/m, С другой стороны, последний элемент участвует только в одной замене; таким образом, он должен быть добавлен к образцу с вероятностью n/m с самого начала.
Для простоты предположим, что вам нужно выбрать только один элемент из m, используя эту стратегию замены (обратите внимание, что вы не знаете заранее, что m есть: вы просто повторяете, пока не дойдете до конца). Вы берете первый элемент и сохраняете его с вероятностью 1 (из всего, что вы знаете, это единственный элемент). Затем вы обнаруживаете второй элемент, бросаете монету и либо сохраняете ее, либо выбрасываете с вероятностью 1/2, На этом этапе каждый из первых двух элементов имеет 1/2 вероятность быть избранным.
Теперь вы видите третий элемент и сохраняете его с вероятностью 1/3, Каждый из первых двух элементов имел 1/2 вероятность участия в этой встрече, и 2/3 выжить — в общей сложности 1/2 * 2/3 == 1/3 вероятность того, что все еще рядом. Итак, опять же, каждый из первых трех элементов имеет 1/3 вероятность быть выбранным в этой точке.
Индуктивный шаг доказательства того, что после tЭтот элемент проверен, каждый из первых t элементы имеет 1/t вероятность того, что вас выберут, оставляют читателю в качестве упражнения. Таким образом, расширение доказательства на выборку размера n > 1,
Другие решения
Других решений пока нет …