Отбор проб из коллектора

Опубликовано: 5 Января, 2022

Выборка резервуара - это семейство рандомизированных алгоритмов для случайного выбора 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 эл