Per recuperare i numeri casuali k da una matrice di dimensioni indeterminate si utilizza una tecnica chiamata campionamento del serbatoio. Qualcuno può evidenziare brevemente come accade con un codice di esempio?Campionamento serbatoio
risposta
Io in realtà non avevo capito c'era un nome per questo, così ho dimostrato e realizzato questo da zero:
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
Con una prova vicino alla fine.
@Larry: dove si trova il 'accept con la parte di probabilità s/k' nel tuo codice? [citazione dall'algoritmo menzionato su http://blogs.msdn.com/spt/archive/2008/02/05/reservoir-sampling.aspx] – Lazer
Per coincidenza, sembra che tra quell'articolo e il mio, usiamo le stesse variabili , ma per cose diverse. La mia "K" sembra essere la loro "S", e la mia "N" (in codice) sembra essere la loro "K". In altre parole, accetto le cose con probabilità 'K/N', dove N è il numero corrente di cose. – Larry
quello che intendevo chiedere era come stavi implementando la probabilità nel tuo codice. Ad ogni modo, ora capisco. Grazie! – Lazer
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();}
}
Questa domanda ha già una risposta accettata da * anni * fa ... – alestanis
seguendo (1981) descrizione di Knuth più da vicino, Reservoir campionamento (Algoritmo R) potrebbe essere implementato come segue:
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
Qual è la differenza tra questo e [la risposta accettata] (http://stackoverflow.com/a/2612822/481584)? Penso che sia esattamente la stessa cosa, anche se questo codice è più elegante. –
Può essere direttamente correlato alla ricerca pubblicata ([Knuth, 1981] (https://github.com/djtrack16/thyme/blob/master/computer%20science/Donald.E.Knuth.The.Art.of.Computer. Programming.Volume.2.pdf)), nel caso qualcuno sia interessato a una spiegazione più estesa o alla dimostrazione di Knuth. – sam
- 1. Campionamento statistico SQL
- 2. Campionamento casuale da Mongo
- 3. campionamento sul fattore R
- 4. Campionamento stratificato in Spark
- 5. Campionamento dati SQL
- 6. campionamento casuale basato su gruppi
- 7. ponderato campionamento casuale in elasticsearch
- 8. dplyr: Integer campionamento entro mutare
- 9. Panda: campionamento di un DataFrame
- 10. Frequenza di campionamento API WebAudio
- 11. array numpy di bilanciamento con sovra-campionamento
- 12. Dati delle serie temporali in MySQL: campionamento
- 13. Casualmente campionamento sottoinsiemi uniche di una matrice
- 14. Cambia frequenza di campionamento di AudioContext (getUserMedia)
- 15. Seleziona campionamento casuale da sqlserver rapidamente
- 16. Creazione di un livello/livello del serbatoio dinamico utilizzando html e css
- 17. python: campionamento senza sostituzione da una griglia 2D
- 18. La frequenza di campionamento audio si basa sui canali?
- 19. Trovare il tasso di campionamento del touch screen in Android
- 20. campionamento casuale di sottostringhe non sovrapposti di lunghezza k
- 21. campionamento permutazioni di [1,2,3, ..., N] per la grande N
- 22. Frequenza di campionamento per la registrazione audio dell'iPhone
- 23. interpolata campionamento di punti in un'immagine con tensorflow
- 24. Campionamento in R dal vettore di lunghezza variabile
- 25. Come convertire la frequenza di campionamento da AV_SAMPLE_FMT_FLTP a AV_SAMPLE_FMT_S16?
- 26. Campionamento da una distribuzione gamma inversa in R
- 27. FFT/IFFT: Campionamento frequenza e la durata del segnale
- 28. ottimizzazione del semplice programma di campionamento di Gibits Lisp comune
- 29. sequenze di campionamento di numeri casuali a Haskell
- 30. Campionamento di un vettore in base allo split uguale
questione connessa http://stackoverflow.com/questions/54059/efficiently-selection-a-set-of-random-elements-da-a-linked-list –
[Questa pagina] (http://blogs.msdn.com/spt/archive/2008/02/05/ reservoir-sampling.aspx) contiene una buona spiegazione con pseudo-codice. (La pagina di Wikipedia a cui ero originariamente collegato non è chiara, e lo pseudo-codice è incompleto.) –
Ho scritto un post sul blog sull'esatta cosa un paio di mesi fa, che ha un'implementazione in C#: http://gregbeech.com/ blog/sampling-sequenze molto grandi La migliore descrizione di come funziona è stata trovata qui: http://gregable.com/2007/10/reservoir-sampling.html –