Próbkowanie zbiorników

Question

Aby pobrać k losowych liczb z tablicy o nieokreślonym rozmiarze, używamy techniki zwanej próbkowaniem zbiorników. Czy ktokolwiek może krótko podkreślić, jak to się dzieje w przypadku przykładowego kodu?

Answer 1

I rzeczywiście nie zdawali sobie sprawy było imię tego, więc to udowodnione i realizowane od podstaw:

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 

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

z dowodem blisko końca.

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

Po Knutha (1981) opis dokładniej, zbiornik Sampling (algorytm R) mogą być realizowane w następujący sposób:

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