Отбор проб из коллектора
Выборка резервуара - это семейство рандомизированных алгоритмов для случайного выбора k выборок из списка из n элементов, где n - очень большое или неизвестное число. Обычно n достаточно велико, чтобы список не помещался в основную память. Например, список поисковых запросов в Google и Facebook.
Итак, нам дан большой массив (или поток) чисел (для упрощения), и нам нужно написать эффективную функцию для случайного выбора k чисел, где 1 <= k <= n . Пусть входным массивом будет stream [].
Простое решение - создать массив резервуар [] максимального размера k . Один за другим случайным образом выберите элемент из потока [0..n-1] . Если выбранный элемент ранее не был выбран, поместите его в резервуар [] . Чтобы проверить, был ли элемент выбран ранее или нет, нам нужно выполнить поиск элемента в резервуаре [] . Временная сложность этого алгоритма будет O (k ^ 2) . Это может быть дорогостоящим, если k велико. Кроме того, это неэффективно, если ввод находится в форме потока.
Ее можно решить за O (n) раз . Решение также хорошо подходит для ввода в виде потока. Идея похожа на этот пост. Ниже приведены шаги.
1) Создайте массив резервуар [0..k-1] и скопируйте в него первые k элементов потока [] .
2) Теперь поочередно рассмотрим все элементы от (k + 1) -го до n- го.
… A) Сгенерировать случайное число от 0 до i, где i - индекс текущего элемента в потоке [] . Пусть сгенерированное случайное число равно j .
… Б) Если j находится в диапазоне от 0 до k-1 , замените резервуар [j] потоком [i]
Ниже приводится реализация описанного выше алгоритма.
C ++
// An efficient program to randomly select // k items from a stream of items #include <bits/stdc++.h> #include <time.h> using namespace std; // A utility function to print an array void printArray( int stream[], int n) { for ( int i = 0; i < n; i++) cout << stream[i] << " " ; cout << endl; } // A function to randomly select // k items from stream[0..n-1]. void selectKItems( int stream[], int n, int k) { int i; // index for elements in stream[] // reservoir[] is the output array. Initialize // it with first k elements from stream[] int reservoir[k]; for (i = 0; i < k; i++) reservoir[i] = stream[i]; // Use a different seed value so that we don't get // same result each time we run this program srand ( time (NULL)); // Iterate from the (k+1)th element to nth element for (; i < n; i++) { // Pick a random index from 0 to i. int j = rand () % (i + 1); // If the randomly picked index is smaller than k, // then replace the element present at the index // with new element from stream if (j < k) reservoir[j] = stream[i]; } cout << "Following are k randomly selected items
" ; printArray(reservoir, k); } // Driver Code int main() { int stream[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}; int n = sizeof (stream)/ sizeof (stream[0]); int k = 5; selectKItems(stream, n, k); return 0; } // This is code is contributed by rathbhupendra |
C
// An efficient program to randomly select k items from a stream of items #include <stdio.h> #include <stdlib.h> #include <time.h> // A utility function to print an array void printArray( int stream[], int n) { for ( int i = 0; i < n; i++) printf ( "%d " , stream[i]); printf ( "
" ); } // A function to randomly select k items from stream[0..n-1]. void selectKItems( int stream[], int n, int k) { int i; // index for elements in stream[] // reservoir[] is the output array. Initialize it with // first k elements from stream[] int reservoir[k]; for (i = 0; i < k; i++) reservoir[i] = stream[i]; // Use a different seed value so that we don't get // same result each time we run this program srand ( time (NULL)); // Iterate from the (k+1)th element to nth element for (; i < n; i++) { // Pick a random index from 0 to i. int j = rand () % (i+1); // If the randomly picked index is smaller than k, then replace // the element present at the index with new element from stream if (j < k) reservoir[j] = stream[i]; } printf ( "Following are k randomly selected items
" ); printArray(reservoir, k); } // Driver program to test above function. int main() { int stream[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}; int n = sizeof (stream)/ sizeof (stream[0]); int k = 5; selectKItems(stream, n, k); return 0; } |
Джава
// An efficient Java program to randomly // select k items from a stream of items import java.util.Arrays; import java.util.Random; public class ReservoirSampling { // A function to randomly select k items from // stream[0..n-1]. static void selectKItems( int stream[], int n, int k) { int i; // index for elements in stream[] // reservoir[] is the output array. Initialize it // with first k elements from stream[] int reservoir[] = new int [k]; for (i = 0 ; i < k; i++) reservoir[i] = stream[i]; Random r = new Random(); // Iterate from the (k+1)th element to nth element for (; i < n; i++) { // Pick a random index from 0 to i. int j = r.nextInt(i + 1 ); // If the randomly picked index is smaller than // k, then replace the element present at the // index with new element from stream if (j < k) reservoir[j] = stream[i]; } System.out.println( "Following are k randomly selected items" ); System.out.println(Arrays.toString(reservoir)); } // Driver Program to test above method public static void main(String[] args) { int stream[] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 }; int n = stream.length; int k = 5 ; selectKItems(stream, n, k); } } // This code is contributed by Sumit Ghosh |
Python3
# An efficient Python3 program # to randomly select k items # from a stream of items random import # A utility function # to print an array def printArray(stream,n): for i in range (n): print (stream[i],end = " " ); print (); # A function to randomly select # k items from stream[0..n-1]. def selectKItems(stream, n, k): i = 0 ; # index for elements # in stream[] # reservoir[] is the output # array. Initialize it with # first k elements from stream[] reservoir = [ 0 ] * k; for i in range (k): reservoir[i] = stream[i]; # Iterate from the (k+1)th # element to nth element while (i < n): # Pick a random index # from 0 to i. j = random.randrange(i + 1 ); # If the randomly picked # index is smaller than k, # then replace the element # present at the index # with new element from stream if (j < k): reservoir[j] = stream[i]; i + = 1 ; print ( "Following are k randomly selected items" ); printArray(reservoir, k); # Driver Code if __name__ = = "__main__" : stream = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 ]; n = len (stream); k = 5 ; selectKItems(stream, n, k); # This code is contributed by mits |
C #
// An efficient C# program to randomly // select k items from a stream of items using System; using System.Collections; public class ReservoirSampling { // A function to randomly select k // items from stream[0..n-1]. static void selectKItems( int []stream, int n, int k) { // index for elements in stream[] int i; // reservoir[] is the output array. // Initialize it with first k // elements from stream[] int [] reservoir = new int [k]; for (i = 0; i < k; i++) reservoir[i] = stream[i]; Random r = new Random(); // Iterate from the (k+1)th // element to nth element for (; i < n; i++) { // Pick a random index from 0 to i. int j = r.Next(i + 1); // If the randomly picked index // is smaller than k, then replace // the element present at the index // with new element from stream if (j < k) reservoir[j] = stream[i]; } Console.WriteLine( "Following are k " + "randomly selected items" ); for (i = 0; i < k; i++) Console.Write(reservoir[i]+ " " ); } //Driver code static void Main() { int []stream = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}; int n = stream.Length; int k = 5; selectKItems(stream, n, k); } } // This code is contributed by mits |
PHP
<?php // An efficient PHP program // to randomly select k items // from a stream of items // A utility function // to print an array function printArray( $stream , $n ) { for ( $i = 0; $i < $n ; $i ++) echo $stream [ $i ]. " " ; echo "
" ; } // A function to randomly select // k items from stream[0..n-1]. function selectKItems( $stream , $n , $k ) { $i ; // index for elements // in stream[] // reservoir[] is the output // array. Initialize it with // first k elements from stream[] $reservoir = array_fill (0, $k , 0); for ( $i = 0; $i < $k ; $i ++) $reservoir [ $i ] = $stream [ $i ]; // Iterate from the (k+1)th // element to nth element for (; $i < $n ; $i ++) { // Pick a random index // from 0 to i. $j = rand(0, $i + 1); // If the randomly picked // index is smaller than k, // then replace the element // present at the index // with new element from stream if ( $j < $k ) $reservoir [ $j ] = $stream [ $i ]; } echo "Following are k randomly " . "selected items
" ; printArray( $reservoir , $k ); } // Driver Code $stream = array (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12); $n = count ( $stream ); $k = 5; selectKItems( $stream , $n , $k ); // This code is contributed by mits ?> |
Javascript
<script> // An efficient program to randomly select // k items from a stream of items // A utility function to print an array function printArray(stream, n) { for (let i = 0; i < n; i++) document.write(stream[i] + " " ); document.write( '
' ); } // A function to randomly select // k items from stream[0..n-1]. function selectKItems(stream, n, k) { // Index for elements in stream[] let i; // reservoir[] is the output array. Initialize // it with first k elements from stream[] let reservoir = []; for (i = 0; i < k; i++) reservoir[i] = stream[i]; // Use a different seed value so that // we don't get same result each time // we run this program // Iterate from the (k+1)th element // to nth element for (; i < n; i++) { // Pick a random index from 0 to i. let j = (Math.floor(Math.random() * 100000000) % (i + 1)); // If the randomly picked index is // smaller than k, then replace the // element present at the index // with new element from stream if (j < k) reservoir[j] = stream[i]; } document.write( "Following are k randomly " + "selected items
" ); printArray(reservoir, k); } // Driver Code let stream = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ]; let n = stream.length; let k = 5; selectKItems(stream, n, k); // This code is contributed by rohan07 </script> |
Выход:
Ниже приведены k случайно выбранных предметов. 6 2 11 8 12 Примечание. Вывод будет каждый раз отличаться, поскольку он выбирает и печатает случайные элементы.
Сложность времени: O (n)
Как это работает?
Чтобы доказать, что это решение работает идеально, мы должны доказать, что вероятность того, что любой поток элементов [i], где 0 <= i <n, будет в конечном резервуаре [], составляет k / n . Разобьем доказательство на два случая, так как первые k пунктов трактуются по-разному.
Случай 1: для последних nk элементов потока, т. Е. Для потока [i], где k <= i <n
Для каждого такого элемента потока stream [i] мы выбираем случайный индекс от 0 до i, и если выбранный индекс является одним из первых k индексов, мы заменяем элемент с выбранным индексом на stream [i]
Для упрощения доказательства рассмотрим сначала последний пункт . Вероятность того, что последний элемент находится в конечном резервуаре = вероятность того, что один из первых k индексов будет выбран для последнего элемента = k / n (вероятность выбора одного из k элементов из списка размера n )
Давайте теперь рассмотрим второй последний пункт . Вероятность того, что второй последний элемент находится в конечном резервуаре [] = [Вероятность того, что один из первых k индексов будет выбран в итерации для потока [n-2] ] X [Вероятность того, что индекс выбран в итерации для потока [n-1 ] не то же самое, что индекс, выбранный для потока [n-2] ] = [ k / (n-1)] * [(n-1) / n ] = k / n .
Точно так же мы можем рассмотреть другие элементы для всех элементов потока от потока [n-1] до потока [k] и обобщить доказательство.
Случай 2: для первых k элементов потока, т. Е. Для потока [i], где 0 <= i <k
Первые k эл