Generare miliardi di numeri casuali Unici [chiuso]

-1

Recentemente ho partecipato a un'intervista. In che ho dovuto risolvere il problema per la generazione di un miliardo di numeri univoci casuali.
Ad esempio la firma del metodo è la seguente:

public Iterator<Long> generate(final long N, final Random rand){

}

L'iteratore restituito deve contenere N numeri casuali univoci. Questo metodo verrà testato contro 10 miliardi come N e si dispone solo di memoria JVM da 128 MB. Come lo faresti.?
Sono venuto con la risposta di sotto che ha detto che potrei me 1 o 2 istanze che il numero potrebbe ripetere. Come potrei garantire. Ad esempio: problema del paradosso del compleanno.
La mia soluzione:

public Iterator<Long> generate(long N, Random rand) {
            LongStream stream = rand.longs(N);
            return stream.iterator();
}

Purtroppo non ho seguito un processo di intervista dal momento che era poco tempo. Ma voglio ancora sapere come gestiremo efficientemente 10 miliardi di generazione casuale unica.

    
posta MrA 24.03.2018 - 05:03
fonte

1 risposta

2

Di solito sono domande trabocchetto. Un modo per pensare al trucco implicito è vedere che la RAM è consentita: 128mb- è circa 1 miliardo di bit. 10 miliardi di numeri possono essere visti come 1 miliardo di gruppi di 10 numeri. Quindi, per generare una sequenza casuale unica di 10 miliardi di numeri, pensateci come 1 miliardo di gruppi non sovrapposti di 10 numeri univoci.

Utilizza la struttura dati da 1 miliardo di bit come un grande set di flag per tracciare quali gruppi di numeri sono stati generati. Generare 10 numeri casuali alla volta, utilizzandoli per selezionare numeri specifici all'interno di un gruppo specifico di numeri.

Puoi usare casualità per scegliere quale gruppo generare; diventa costoso quando arrivi alla fine, quindi è meglio avere un algoritmo per attraversare lo spazio del gruppo. Generare numeri da alcuni gruppi specifici alla volta, quindi randomizzare la sequenza con cui vengono restituiti quei numeri. Ci sono molte varianti su questo tema, naturalmente, e diversi modi per soddisfare diversi standard di casualità.

    
risposta data 26.03.2018 - 01:01
fonte

Leggi altre domande sui tag