Contrassegna x% articoli in streaming

Diciamo che hai n elementi e sai che vuoi segnare m articoli, m < = n (secondo il valore%). Ora contrassegni gli oggetti uno per uno, iniziando con una probabilità casuale di m / n per contrassegnare il primo oggetto. Ma invece di mantenere tale probabilità fissa, dopo ogni passaggio si adatta la probabilità effettiva a ciò che è necessario ora!

Quindi, quando dopo i passaggi di k hai segnato l elementi, dovrai elaborare (n-k) gli elementi rimanenti e vuoi avere (m-l) di essi marcati. Quindi scegli la probabilità dell'elemento successivo come (m-l) / (n-k).

Come vedi, più mi si avvicina a m, minore sarà la probabilità di marcatura. Quando l è uguale a m, la probabilità è 0. D'altra parte, quando il numero di oggetti rimanenti raggiunge il numero di elementi rimanenti da contrassegnare, la probabilità diventerà 1. Infine, si finirà con esattamente gli elementi contrassegnati m.

Dovrebbe essere ovvio che il tempo di esecuzione è O (n), dal momento che ogni elemento viene elaborato una volta, e l'unica cosa che devi tenere traccia sono entrambi i numeri (m-l) e (n-k).

Sarà asintoticamente corretto, ovvero tenderà ad avvicinarsi alle specifiche con il passare del tempo. Tuttavia, per una quantità di tempo non specificata, si discosterà dalle specifiche, possibilmente piuttosto severamente (e forse molto più di quanto sarebbe necessario, dato che non è possibile contrassegnare parzialmente un articolo).

Se ciò è abbastanza buono per il tuo caso d'uso è una domanda alla quale solo tu puoi rispondere. Se devi approssimare la percentuale specificata il più vicino possibile, allora i tuoi suggerimenti non sono abbastanza buoni, e dovrai mantenere anche contatori aggiuntivi. (Tuttavia, questo non dovrebbe portarti fuori dal regno delle soluzioni a tempo lineare.)

Se contrassegni semplicemente x% per probabilità indipendente per ogni oggetto potresti non finire per un n fisso con esattamente x% degli n elementi.

Consiglio qualcosa del genere:

n è noto, quindi puoi calcolare quanti articoli devi contrassegnare markSize=n*x/100 .

Ora prendi i primi markSize elementi dallo stream e mentre leggi il resto del flusso, sostituiscili casualmente con la relativa probabilità.

L'esempio semplificato, se vuoi contrassegnare uno di uno stream di n:

1. prendi il primo come candidato al voto
2. leggi il secondo dallo stream e sostituisci il tuo vecchio mark-candidate con una probabilità di 1/2
3. leggi il terzo dallo stream e sostituisci il tuo vecchio mark-candidate con una probabilità di 1/3
4. e così via (In questo caso non hai nemmeno bisogno di sapere in anticipo.)

Questa idea può essere generalizzata per qualsiasi numero di elementi da contrassegnare da un flusso. Poiché leggi il flusso una volta sola, la complessità temporale è O (n) .

Dovrebbe funzionare in modo accettabile nel tuo caso d'uso. La regola generale è che la distribuzione del numero di elementi segnati su molti campioni avrà media e (dove e è n volte x%) e deviazione standard sqrt (e). Ciò significa che hai il 99,7% di possibilità che il numero di elementi segnati cada tra e-3sqrt (e) ed e + 3sqrt (e). Diciamo n = 1.000.000.000 e x = 1%. Quindi e = 10.000.000 e sqrt (e) sono circa 3.000. Puoi avere il 99,7% di certezza che il numero di articoli contrassegnati scenderà tra 9,994,000 e 10,006,000. Probabilmente è abbastanza buono per i tuoi scopi. Quando x diventa molto piccolo, tuttavia, la precisione diminuisce.