Problema:

Given a stream of elements too large to store in memory, pick a random element from the stream with uniform probability.

Scegliere un elemento casuale con probabilità uniforme da un array di dimensione n è semplice:

from random import randrange

foo = ['A', 'B', 'C', 'D']
n = len(foo)

print(foo[randrange(n)])

in realtà vi sarebbe anche il metodo random.choice() o lo stesso metodo della libreria secrets che garantisce sicurezza a livello crittografico.

Se lo stream però è troppo grande per stare in memoria, e non ne conosciamo la dimensione in anticipo, non possiamo applicare il metodo precedente ma dobbiamo utilizzare una diversa strategia. Necessariamente dovremo selezionare un elemento mentre stiamo leggendo lo stream, avendo come unica informazione il numero di elementi ricevuti fino a quel momento, ma non sapendo quanti ne mancano alla fine.

L’elemento corrente avrà probabilità \(\frac{1}{n}\) di essere estratto, dove \({n}\) è il numero di elementi letti dallo stream fino a quel momento. Potremmo selezionarlo in questo modo:

if random.randint(1,n) == n:
    chosen = current_element_from_stream

che cosa succede ad eventuali elementi letti in precedenza? Dobbiamo dimostrare come tutti gli elementi abbiano a loro volta la stessa probabilità \(\frac{1}{n}\) di essere stati scelti.

L’elemento precedente lo abbiamo scelto con probabilità \(\frac{1}{(n - 1)}\) il quale ha probabilità \(\frac{(n - 1)}{n}\) di rimanere, da cui si ricava la sua probabilità che è \(\frac{1}{(n-1)} \cdot \frac{(n-1)}{n} = \frac{1}{n}\).

Il codice completo può essere il seguente (dove lo stream è “simulato” da un array):

import random

def get_random_element(stream):
    chosen = None
    n = 0

    for i in range(len(stream)):
        n=n+1
        if random.randint(1,n) == n:
            chosen = stream[i]

    return chosen

stream = ['A', 'B', 'C', 'D']
print(get_random_element(stream))