El muestreo de reservorio es una familia de algoritmos aleatorios para elegir aleatoriamente k muestras de una lista de n elementos, donde n es un número muy grande o desconocido. Por lo general, n es lo suficientemente grande como para que la lista no quepa en la memoria principal. Por ejemplo, una lista de consultas de búsqueda en Google y Facebook.
Así que tenemos una gran array (o flujo) de números (para simplificar), y necesitamos escribir una función eficiente para seleccionar aleatoriamente k números donde 1 <= k <= n . Deje que la array de entrada sea stream[].
Una solución simple es crear un depósito de array [] de tamaño máximo k . Uno por uno, seleccione aleatoriamente un elemento de stream[0..n-1] . Si el elemento seleccionado no se seleccionó previamente, colóquelo en depósito[] . Para verificar si un elemento se seleccionó previamente o no, debemos buscar el elemento en el depósito [] . La complejidad temporal de este algoritmo será O(k^2) . Esto puede ser costoso si k es grande. Además, esto no es eficiente si la entrada tiene la forma de una secuencia.
Se puede resolver en tiempo O(n) . La solución también se adapta bien a la entrada en forma de flujo. La idea es similar a este post. Los siguientes son los pasos. 1) Cree un depósito de array [0..k-1] y copie los primeros k elementos de stream[] en él. 2) Ahora, uno por uno, considere todos los elementos desde (k+1) hasta el elemento n . … a) Genere un número aleatorio de 0 a i donde i es el índice del elemento actual en stream[] . Deje que el número aleatorio generado sea j .
… b) Si j está en el rango de 0 a k-1 , reemplace el depósito [j] con la corriente [i]
A continuación se muestra la implementación del algoritmo anterior.
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 \n";
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("\n");
}
// 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 \n");
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;
}
Java
// 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
import random
# 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 "\n";
}
// 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\n";
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('\n');
}
// 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 \n");
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>
Producción:
Following are k randomly selected items 6 2 11 8 12 Note: Output will differ every time as it selects and prints random elements
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(k)
¿Como funciona esto?
Para probar que esta solución funciona perfectamente, debemos probar que la probabilidad de que cualquier flujo de elementos[i] donde 0 <= i < n esté en el depósito final[] es k/n . Dividamos la prueba en dos casos ya que los primeros k elementos se tratan de manera diferente.
Caso 1: Para los últimos nk elementos de flujo, es decir, para flujo[i] donde k <= i <n Para cada uno de esos elementos de flujo flujo[i] , elegimos un índice aleatorio de 0 a i y si el índice seleccionado es uno de los primeros k índices, reemplazamos el elemento en el índice seleccionado con stream[i] Para simplificar la prueba, primero consideremos el último elemento . La probabilidad de que el último artículo esté en el reservorio final = La probabilidad de que uno de los primeros k índices sea seleccionado para el último artículo = k/n (la probabilidad de seleccionar uno de los k artículos de una lista de tamaño n )
Consideremos ahora el penúltimo elemento . La probabilidad de que el penúltimo elemento esté en el reservorio final[] = [Probabilidad de que uno de los primeros k índices se elija en la iteración para la corriente[n-2] ] X [Probabilidad de que el índice se seleccione en la iteración para la corriente[n-1 ] no es lo mismo que el índice seleccionado para el flujo [n-2] ] = [ k/(n-1)]*[(n-1)/n ] = k/n .
De manera similar, podemos considerar otros elementos para todos los elementos del flujo desde el flujo [n-1] hasta el flujo [k] y generalizar la prueba.
Caso 2: Para los primeros k elementos de flujo, es decir, para flujo[i] donde 0 <= i <k
Los primeros k elementos se copian inicialmente en depósito[] y pueden eliminarse más tarde en iteraciones para flujo[k] a flujo[n ] .
La probabilidad de que un elemento del flujo[0..k-1] esté en la array final = Probabilidad de que el elemento no se elija cuando los elementos fluyen[k], transmiten[k+1], …. stream[n-1] se consideran = [k/(k+1)] x [(k+1)/(k+2)] x [(k+2)/(k+3)] x … x [ (n-1)/n] = k/n
Referencias:
http://en.wikipedia.org/wiki/Reservoir_sampling
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA