algorithm - Muestreo de yacimientos

random

Question

Para recuperar k números aleatorios de una matriz de tamaño indeterminado, utilizamos una técnica llamada muestreo de yacimientos. ¿Alguien puede destacar brevemente cómo sucede con un código de muestra?

Answer 1

De hecho, no me di cuenta de que había un nombre para esto, así que probé e implementé esto desde cero:

import random
def random_subset( iterator, K ):
result = []
N = 0
for item in iterator:
N += 1
if len( result ) < K:
result.append( item )
else:
s = int(random.random() * N)
if s < K:
result[ s ] = item
return result

De: http://web.archive.org/web/20141026071430/http://propersubset.com:80/2010/04/choosing-random-elements.html

Con una prueba cerca del final.

Answer 2

Java

import java.util.Random;
public static void reservoir(String filename,String[] list)
{
File f = new File(filename);
BufferedReader b = new BufferedReader(new FileReader(f));
String l;
int c = 0, r;
Random g = new Random();
while((l = b.readLine()) != null)
{
if (c < list.length)
r = c++;
else
r = g.nextInt(++c);
if (r < list.length)
list[r] = l;
b.close();}
}

Answer 3

Siguiendo más de cerca la descripción de Knuth (1981), Reservoir Sampling (Algoritmo R) podría implementarse de la siguiente manera:

import random
def sample(iterable, n):
"""
Returns @param n random items from @param iterable.
"""
reservoir = []
for t, item in enumerate(iterable):
if t < n:
reservoir.append(item)
else:
m = random.randint(0,t)
if m < n:
reservoir[m] = item
return reservoir