Выборки коллектора

Чтобы получить k случайных чисел из массива неопределенного размера, мы используем метод, называемый выборкой коллектора. Может ли кто-нибудь кратко указать, как это происходит с образцом кода?

Ответ 1

Я действительно не понимал, что для этого есть имя, поэтому я доказал и осуществил это с нуля:

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

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

С доказательством ближе к концу.

Ответ 2

Следующее описание Кнута (1981) более подробно, выборки коллектора (алгоритм R) можно реализовать следующим образом:

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

Ответ 3

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();}
}