Является ли образец размером 1 рассмотреть выборки водохранилища?

Question

Я просто хочу знать, что мой код - выборка коллектора. У меня поток просмотров страниц, который я просто хочу обработать. Я обрабатываю один просмотр страницы за раз. Однако, поскольку большинство просмотров страниц одинаковы, поэтому я просто хочу случайным образом выбрать любое просмотрение страниц (по одному для обработки). Например, у меня есть страница

[www.example.com, www.example.com, www.example1.com, www.example3.com, ...] 

Я обрабатываю один элемент за раз. Вот мой код.

import random 

def __init__(self): 
    self.counter = 0 

def processable(): 
    self.counter += 1 
    return random.random() < 1.0/self.counter 

Answer 1

Следуя алгоритму выборки резервуара (можно найти здесь: https://en.wikipedia.org/wiki/Reservoir_sampling), где мы храним только один просмотр страницы (размер резервуара = 1), следующая реализация показывает, что, как стратегия вероятностного выбора из потокового просмотра страниц приводит к равномерному вероятностей отбора:

import numpy as np 
import matplotlib.pyplot as plt 
max_num = 10 # maximum number of pageviews we want to consider 
# replicate the experiment ntrials times and find the probability for selection of any pageview 
pageview_indices = [] 
ntrials = 10000 
for _ in range(ntrials): 
    pageview_index = None # index of the single pageview to be kept 
    i = 0 
    while True: # streaming pageviews 
     i += 1 # next pageview 
     if i > max_num: 
      break 
     # keep first pageview and from next pageview onwards discard the old one kept with probability 1 - 1/i 
     pageview_index = 1 if i == 1 else np.random.choice([pageview_index, i], 1, p=[1-1./i, 1./i])[0] 
     #print 'pageview chosen:', pageview_index 
    print 'Final pageview chosen:', pageview_index 
    pageview_indices.append(pageview_index) 
plt.hist(pageview_indices, max_num, normed=1, facecolor='green', alpha=0.75) 
plt.xlabel('Pageview Index') 
plt.ylabel('Probability Chosen') 
plt.title('Reservoir Sampling') 
plt.axis([0, max_num+1, 0, 0.15]) 
plt.xticks(range(1, max_num+1)) 
plt.grid(True) 

Как видно из сказанного выше, вероятность просмотра страницы выбранных индексов почти однородно (1/10 для каждого из 10 просмотров страниц), математически может быть также установлено, что оно равномерно.