Scegliere N elementi a caso dalla sequenza di lunghezza sconosciuta

Question

Sto provando a scrivere un algoritmo che scegli N elementi distinti da una sequenza a caso, senza conoscere la dimensione della sequenza in anticipo e dove è costoso iterare su la sequenza più di una volta. Ad esempio, gli elementi della sequenza potrebbero essere le linee di un file enorme.

Ho trovato una soluzione quando N = 1 (cioè, quando si cerca di scegliere esattamente un elemento a caso da una sequenza enorme):

import random 
items = range(1, 10) # Imagine this is a huge sequence of unknown length 
count = 1 
selected = None 
for item in items: 
    if random.random() * count < 1: 
     selected = item 
    count += 1 

Ma come posso ottenere la stessa cosa per altri valori di N (per esempio, N = 3)?

Answer 1

Utilizzare reservoir sampling. È un algoritmo molto semplice che funziona con qualsiasi N.

Here è un'implementazione Python e here è un'altra.

Answer 2

Come aix ha menzionato i lavori di campionamento del giacimento. Un'altra opzione è generare un numero casuale per ogni numero che vedi e selezionare i primi numeri k.

Per farlo iterativamente, mantenere un mucchio di k (, il numero di numeri casuali) coppie e ogni volta che si vede un numero nuovo inserto all'heap se è maggiore del valore più piccolo nel mucchio.

Answer 3

Dovrebbe essere sufficiente accettare o rifiutare ogni nuovo elemento solo una volta e, se lo si accetta, lanciare un vecchio articolo scelto a caso.

Supponiamo di aver selezionato N elementi di K casualmente e si vede un (K + 1) articolo. Accettalo con probabilità N/(K + 1) e le sue probabilità sono OK. Gli oggetti attuali sono arrivati ​​con probabilità N/K, e vengono espulsi con probabilità (N/(K + 1)) (1/N) = 1/(K + 1) quindi sopravvivi con probabilità (N/K) (K/(K + 1)) = N/(K + 1) quindi anche le loro probabilità sono accettabili.

E sì, vedo qualcuno che ti ha indicato il campionamento del serbatoio: questa è una spiegazione di come funziona.

Answer 4

@NPE è corretto, ma le implementazioni a cui si sta collegando sono sub-ottimali e non molto "pythonic". Ecco un'implementazione meglio:

def sample(iterator, k): 
    """ 
    Samples k elements from an iterable object. 

    :param iterator: an object that is iterable 
    :param k: the number of items to sample 
    """ 
    # fill the reservoir to start 
    result = [next(iterator) for _ in range(k)] 

    n = k - 1 
    for item in iterator: 
     n += 1 
     s = random.randint(0, n) 
     if s < k: 
      result[s] = item 

    return result 

Modifica Come @ panda-34 ha sottolineato la versione originale è stata viziata, ma non perché stavo usando randint vs randrange. Il problema è che il mio valore iniziale per n non ha tenuto conto del fatto che randint è compreso su entrambe le estremità dell'intervallo. Tenendo conto di ciò, si risolve il problema. (Nota: è possibile utilizzare anche randrange poiché è inclusivo sul valore minimo ed esclusivo sul valore massimo.)

Answer 5

Se la sequenza è abbastanza breve da poterla leggere in memoria e ordinarla casualmente è accettabile, allora un approccio diretto sarebbe essere quella di utilizzare solo random.shuffle:

import random 
arr=[1,2,3,4] 

# In-place shuffle 
random.shuffle(arr) 

# Take the first 2 elements of the now randomized array 
print arr[0:2] 
[1, 3] 

a seconda del tipo di sequenza, potrebbe essere necessario convertirlo in un elenco chiamando list(your_sequence) su di esso, ma questo funzionerà indipendentemente dai tipi di oggetti nella sequenza .

Naturalmente, se non è possibile adattare la sequenza in memoria o la memoria oi requisiti della CPU di questo approccio sono troppo alti per te, sarà necessario utilizzare una soluzione diversa.

Answer 6

seguito vi darà articoli N casuali da una matrice X

import random 
list(map(lambda _: random.choice(X), range(N))) 

Answer 7

Questa era la mia risposta a una domanda duplicato (chiuso prima che potessi postare), che era un po 'correlato ("generazione di numeri casuali senza duplicati"). Poiché, è un approccio diverso rispetto alle altre risposte, lo lascio qui nel caso in cui fornisca ulteriori informazioni.

from random import randint 

random_nums = [] 
N = # whatever number of random numbers you want 
r = # lower bound of number range 
R = # upper bound of number range 

x = 0 

while x < N: 
    random_num = randint(r, R) # inclusive range 
    if random_num in random_nums: 
     continue 
    else: 
     random_nums.append(random_num) 
     x += 1 

Il motivo per il ciclo mentre il ciclo for è che consente una più facile attuazione non saltare in generazione casuale (cioè se si ottiene 3 duplicati, non sarà possibile ottenere N-3 numeri).

Answer 8

userei scelte

from random import choices 

items = range(1, 10) 
new_items = choices(items, k = 3) 

print(new_items) 
[6, 3, 1]