Modo efficiente per calcolare quanti oggetti distruggere se ognuno ha una probabilità del 70% di essere distrutto

Per ottenere il numero di elementi rimanenti, devi campionare da una distribuzione binomiale , ovvero la distribuzione B(n, 0.3) dove n è il numero originale di elementi. Puoi farlo utilizzando un solo numero casuale usando il metodo di trasformazione inversa .

Un problema che potresti incontrare è che il calcolo del CDF inverso per la distribuzione binomiale è esplicitamente (sono abbastanza sicuro) anche lineare nel valore di n , quindi potrebbe essere troppo lento per un% molto grande din. Ma puoi approfittare del fatto che per il grande n , la distribuzione binomiale è ben approssimata da una distribuzione normale , nel tuo caso N(0.3*n, 0.21*n) . Il CDF inverso della distribuzione normale è una formula sgradevole, ma è fornito da varie librerie (ad esempio norminv in matlab, o scipy.stats.norm.ppf in SciPy). Passando da uno all'altro con un valore appropriato di n (Wikipedia suggerisce che l'approssimazione è abbastanza buona per n >= 24 quando p è 0.3, ma "abbastanza buono" è una questione di opinione), puoi ottenere una buona soluzione approssimativa con un tempo di esecuzione limitato indipendente da n .

Detto questo, dovresti provare a farlo nel modo più semplice prima di eliminarlo. Generare un miliardo di numeri casuali al secondo è possibile sui sistemi moderni, quindi milioni di elementi potrebbero non essere tanto un problema come si pensa.

Come altri hanno notato, puoi usare la distribuzione binomiale. Ma ti suggerisco di evitare di provare a scrivere il tuo algoritmo, è facile rovinarlo. Invece, molte lingue hanno librerie in grado di generare variabili casuali binomiali.

C ++ ha Boost.Random: link

Python ha numpy.random.binomial: link

Il nodo ha distribuzioni casuali: link

Java ha commons apache: link

Ma per aggiungere un altro approccio, è possibile generare una variabile da una distribuzione esponenziale con lambda = 1 / .3. Questa distribuzione ti darà il tempo tra due cancellazioni. Quindi lo useresti qualcosa come:

while(true) {
    int nextDeletion = exponential(1/.3)
    moveForward(nextDeletion);
    deleteCurrent();
}

L'ho usato nei casi in cui la mia probabilità era molto bassa, qualcosa come .00000001, ed era molto più veloce di un approccio ingenuo. Non so se può aiutarti.

Si genera un numero casuale compreso tra 1 e 10. Se il numero intero casuale è minore o uguale a 7, non fare nulla, altrimenti aggiungere 1 a una somma parziale. Ripetere questa funzione n volte per la dimensione del parametro di input n. Il risultato è il numero di oggetti distrutti che possono essere utilizzati per derivare il numero sopravvissuto.

Questa complessità operativa O (n) e complessità della memoria O (1). Questo perché il numero di operazioni da eseguire è costante rispetto al n parametro di input.

A meno di non sottrarre .7 dal numero intero, questo non sarà un tempo costante. È un tempo lineare.

Se vuoi simulare una variabile casuale con distribuzione binomiale, vai avanti e fallo.

Se vuoi solo un numero veloce e sporco la cui media si avvicina al numero previsto di elementi eliminati, usa semplicemente una variabile casuale uniforme con un intervallo adatto, ad esempio:

(rand() * 0.6 + 0.4) * num_of_items

Dove rand() è uniforme su [0; 1], rand() * 0.6 è uniforme su [0; 0.6] , rand() * 0.6 + 0.4 è uniforme su [0.4; 1] e con 0.7 come media, e infine abbiamo una variabile casuale uniforme su [0.4 * num_of_items; num_of_items] con una media di 0.7 * num_of_items .

Puoi ridurre il numero% di0.6 aumentando il 0.4 (mantenendo la media) per avere una deviazione più piccola.

Non è chiaro quale sia lo scopo o il requisito per questo, quindi non so se questo li incontrerà.

Ma potresti eseguire il loop su tutti gli oggetti, mantenendo un conteggio mod 10 e eliminando da 1 a 7. Per aggiungere casualità, inizia il conteggio a un valore casuale compreso tra 1 e 10. Ciò tecnicamente ti darà un 70%, cancellazione effettivamente casuale senza un milione di numeri casuali.

pseudocodice:

n = rand(1,10)
for i = 1 to objectCount
  if (n mod 10) <= 7
    doDelete(object[i])
  n++

Nota che ogni elemento avrebbe una possibilità di cancellazione del 70% e non sapresti quale sarà cancellato prima del tempo ... ma si eliminerebbe in modo coerente in gruppi di 7.

Detto questo, potresti comunque provarlo con un PRNG veloce per ogni oggetto solo per vedere. Il mio sospetto è che si sta ottimizzando prematuramente e che la maggior parte del tempo di esecuzione per questo processo libererà gli oggetti anziché il PRNG.