Выборка водохранилища

Question

Выборка водохранилища

Для получения k случайных чисел от массива неопределенного размера, мы используем технику, названную выборкой водохранилища. Кто-либо может кратко выделиться, как это происходит с примером кода?

24

algorithm random

задан templatetypedef 14 August 2017 в 01:41

1 ответ

Другие вопросы по тегам:

algorithm random

Похожие вопросы:

score 35 · Accepted Answer

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

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

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