Algoritmo per stampare un elenco mescolato, sul posto e con memoria O(1).

StackOverflow https://stackoverflow.com/questions/1866684

  •  18-09-2019
  •  | 
  •  

Domanda

Dopo aver letto questa domanda Ho iniziato a chiedermi:è possibile avere un algoritmo di mescolamento che non modifichi o copi l'elenco originale?

Per chiarire:

Immagina che ti venga fornito un elenco di oggetti.La dimensione dell'elenco può essere arbitraria, ma presuppone che sia piuttosto grande (ad esempio, 10.000.000 di elementi).Devi stampare gli elementi dell'elenco in ordine casuale e devi farlo il più velocemente possibile.Tuttavia, non dovresti:

  • Copia l'elenco originale, perché è molto grande e la copia sprecherebbe MOLTA memoria (probabilmente raggiungendo i limiti della RAM disponibile);
  • Modifica l'elenco originale, perché è ordinato in qualche modo e qualche altra parte in seguito dipende dall'ordinamento.
  • Creare un elenco indice perché, ancora una volta, l'elenco è molto grande e la copia richiede troppo tempo e memoria.(Una precisazione:si intende qualsiasi altra lista, che abbia lo stesso numero di elementi della lista originaria).

È possibile?

Aggiunto: Ulteriori chiarimenti.

  1. Voglio che l'elenco venga mescolato in modo davvero casuale con tutte le permutazioni ugualmente probabili (ovviamente, supponendo che abbiamo una funzione Rand() corretta con cui iniziare).
  2. Il suggerimento di creare un elenco di puntatori, o un elenco di indici, o qualsiasi altro elenco che abbia lo stesso numero di elementi dell'elenco originale, è esplicitamente considerato inefficiente dalla domanda originale.Se lo desideri, puoi creare elenchi aggiuntivi, ma dovrebbero essere di ordini di grandezza inferiori rispetto all'elenco originale.
  3. L'elenco originale è come un array e puoi recuperare qualsiasi elemento da esso tramite il suo indice in O(1).(Quindi niente cose con elenchi doppiamente collegati, in cui devi scorrere l'elenco per arrivare all'elemento desiderato.)

Aggiunto 2:Ok, mettiamola così:Hai un HDD da 1 TB pieno di elementi di dati, ciascuno grande 512 byte (un singolo settore).Vuoi copiare tutti questi dati su un altro HDD da 1 TB mescolando tutti gli elementi.Vuoi farlo il più velocemente possibile (singolo passaggio di dati, ecc.).Hai 512 MB di RAM disponibili e non contare sullo swap.(Questo è uno scenario teorico, non ho nulla di simile nella pratica.Voglio solo trovare l'algoritmo perfetto.item.)

È stato utile?

Soluzione

Ecco una prova molto semplice che nessuno schema PRNG può funzionare:

L’idea del PRNG prevede due fasi:per prima cosa seleziona un PRNG e il suo stato iniziale;in secondo luogo, utilizzare il PRNG per riprodurre in modo casuale l'output.Bene, ci sono N! possibili permute, quindi ti servono almeno N! diversi possibili stati di avvio, entrando nella fase 2.Ciò significa che all'inizio della fase 2 devi avere almeno tronco d'albero2 N! bit di stato, il che non è consentito.

Tuttavia ciò non esclude schemi in cui l'algoritmo riceve nuovi bit casuali dall'ambiente man mano che procede.Potrebbe esserci, ad esempio, un PRNG che legge il suo stato iniziale pigramente eppure è garantito che non si ripeta.Possiamo dimostrare che non esiste?

Supponiamo di avere un algoritmo di mescolamento perfetto.Immagina di iniziare a eseguirlo e, quando è a metà, di mettere il computer in modalità di sospensione.Ora lo stato completo del programma è stato salvato da qualche parte.Permettere S essere l'insieme di tutti i possibili stati in cui il programma potrebbe trovarsi a metà strada.

Poiché l'algoritmo è corretto e garantisce la terminazione, esiste una funzione F che, dato lo stato del programma salvato più qualsiasi stringa di bit sufficientemente lunga, produce una sequenza valida di letture e scritture del disco completando lo shuffle.Il computer stesso implementa questa funzione.Ma considerala come una funzione matematica:

F : (S × bit) → sequenza di letture e scritture

Quindi, banalmente, esiste una funzione G il quale, dato soltanto lo stato del programma salvato, produce l'insieme di posizioni del disco ancora da leggere e scrivere.(Basta passare una stringa arbitraria di bit a F, quindi guarda i risultati.)

G : S → insieme di posizioni per leggere e scrivere

La restante parte della dimostrazione consiste nel dimostrare che il dominio di G contiene almeno NCN/2 insiemi diversi indipendentemente dalla scelta dell'algoritmo.Se questo è vero, devono esserci almeno altrettanti elementi di S, e quindi lo stato del programma deve contenere almeno tronco d'albero2 NCN/2 bit a metà percorso, in violazione dei requisiti.

Tuttavia, da allora non sono sicuro di come dimostrarlo O l'insieme delle posizioni da leggere O l'insieme di posizioni da scrivere può essere a bassa entropia, a seconda dell'algoritmo.Sospetto che ci sia qualche ovvio principio della teoria dell'informazione che può risolvere il problema.Segnando questo wiki della comunità nella speranza che qualcuno lo fornisca.

Altri suggerimenti

Beh, dipende un po 'da che tipo di casualità voi, se non per il rimescolamento, vale a dire tutti dovremmo stropiccii essere il più probabile, oppure può essere la distribuzione asimmetrica.

Ci sono modi matematici per la produzione di "random-looking" permutazioni di N interi, quindi se P è una tale permutazione da 0..n-1 a 0..n-1, si può solo iterata x da 0 a N -1 e elemento dell'elenco uscita L (P (x)) invece di L (x) e si è ottenuto un rimescolamento. Tali permutazioni possono essere ottenuti ad esempio utilizzando aritmetica modulare. Ad esempio, se N è primo, P (x) = (x * k) mod N è una permutazione per ogni 0

Si dovrebbe notare che elevamento modulare è la base per molti algoritmi crittografici (ad esempio RSA, Diffie-Hellman) ed è considerato un'operazione fortemente pseudocasuale dagli esperti del settore.

Un altro modo semplice (che non richiedono numeri primi) è il primo ad espandere il dominio in modo che invece di N si considera M dove M è il meno potenza di due sopra N. Quindi, per esempio se n = 12 si imposta M = 16. Quindi si utilizza operazioni bit biunivoche, per es. 

P(x) = ((x ^ 0xf) ^ (x << 2) + 3) & 0xf

Poi, quando si uscita la vostra lista, di eseguire iterazioni x da 0 a M-1 e l'uscita L (P (x)) solo se P (x) è in realtà

Una soluzione "vera, imparziale casuale" può essere costruito fissando un crittograficamente forte cifratura a blocchi (ad esempio AES) e una chiave casuale (k) e poi iterando la sequenza 

AES(k, 0), AES(k, 1), ...

ed emettere la voce corrispondente dalla sequenza IFF AES (k, i)

È proibito di fare una copia, modificarlo, o di tenere traccia di quali elementi che hai visitato? Che sto per dire non è possibile. A meno che non sto fraintendendo i criteri di terzi.

io lo prendo a significare non ti è permesso di dire, fare una serie di 10.000.000 booleani corrispondenti, impostata su true quando hai stampato l'elemento corrispondente. E non ti è permesso di fare una lista dei 10.000.000 indici, rimescola la lista, e stampare gli elementi in questo ordine.

Gli 10.000.000 articoli sono solo riferimenti (o puntatori) a elementi reali, così il vostro elenco non sarà così grande. Solo ~ 40MB su architettura a 32-bit per tutti i riferimenti + dimensioni variabili interne di quella lista. Nel caso in cui gli oggetti sono più piccoli del formato di riferimento, basta copiare tutta la lista.

Non è possibile farlo con un davvero generatore di numeri casuali da quando hai a:

  • ricordare che i numeri sono già stati scelti e li saltare (che richiede un elenco O (n) di booleani e progressivamente peggiorando run-volte si salta di più e più numeri); o
  • ridurre piscina dopo ogni selezione (che richiede o modifiche all'elenco originale o un elenco separato O (n) per modificare).

Nessuno di questi sono possibilità nella tua domanda in modo ho intenzione di dire "no, non si può fare".

Quello che mi tendono ad andare per in questo caso è una maschera di bit di valori usati, ma non con il salto in quanto, come detto, alla vigilia volte peggiorano i valori utilizzati si accumulano.

Una maschera di bit sarà sostanzialmente migliore rispetto alla lista originale di 39GB (10 milioni di bit è solo di circa 1.2M), molti ordine di grandezza inferiore, come richiesto anche se è ancora O (n).

Al fine di aggirare il problema in fase di esecuzione, solo generare un numero casuale ogni volta e, se il relativo "usato" bit è già impostato, la scansione in avanti attraverso la maschera di bit fino a trovare quello che è non set.

Ciò significa che non sarà in giro, disperata per il generatore di numeri casuali per darvi un numero che non è stato ancora utilizzato. I tempi di esecuzione saranno sempre e solo ottenere così male come il tempo impiegato per eseguire la scansione 1.2M dei dati.

Naturalmente questo significa che il numero specifico scelto in qualsiasi momento è inclinata basa sui numeri che sono già stati scelti, ma, dal momento che quei numeri erano casuali in ogni caso, l'inclinazione è casuale (e se i numeri non fosse veramente casuale per cominciare, poi l'inclinazione sarà poco importa).

E si potrebbe anche alternare la direzione di ricerca (la scansione su o giù) se si vuole un po 'più di varietà.

Linea di fondo: non credo che quello che stai chiedendo è fattibile, ma tenere a mente sono stato sbagliato prima come mia moglie si attestano, in modo rapido e spesso :-) Ma, come tutte le cose, non c'è di solito modi per aggirare questi problemi.

Sembra impossibile.

Ma 10.000.000 puntatori a 64 bit è solo circa 76MB.

Un registro a scorrimento lineare feedback può fare più o meno ciò che si vuole - generare un elenco di numeri fino a un certo limite, ma in un (ragionevolmente) ordine casuale. I modelli che produce sono statisticamente simile a quello che ci si aspetterebbe da provare casualità, ma non è nemmeno vicino a crittograficamente sicuro. L'algoritmo Berlekamp-Massey permette di invertire ingegnerizzare un LFSR equivalente basata su una sequenza di uscita.

Dato il vostro requisito per un elenco di ~ 10.000.000 articoli, che ci si vuole una massima lunghezza LFSR 24-bit, e semplicemente scartare uscite più grandi rispetto alle dimensioni della vostra lista.

Per quel che vale, un LFSR è in genere abbastanza veloce rispetto ad un tipico congruenziale PRNG lineare dello stesso periodo. In hardware, un LFSR è molto semplice, costituito da un registro a N bit, e M 2 ingressi di XOR (dove M è il numero di prese - a volte solo una coppia, e raramente più di un mezza dozzina o giù di lì).

Se c'è abbastanza spazio, è possibile memorizzare i puntatori del nodo in una matrice, creare una bitmap e ottenere interi casuali che puntano alla voce scelta successiva. Se già scelto (si memorizzano che nel vostro bitmap), quindi ottenere più vicino (a sinistra oa destra, è possibile che casuale), fino a quando non ci sono elementi lasciati.

Se non c'è spazio sufficiente, allora si potrebbe fare lo stesso senza memorizzare puntatori del nodo, ma il tempo soffriranno (che è il compromesso spazio-tempo ☺).

È possibile creare una pseudo-casuale, 'sicura' permutazione utilizzando un cifrario a blocchi - vedi qui . Essi intuizione fondamentale è che, dato un cifrario a blocchi di lunghezza n bit, è possibile utilizzare 'pieghevole' per accorciarlo a m

In sostanza quello che vi serve è un generatore di numeri casuali che produce i numeri 0..n-1 esattamente una volta ciascuno.

Ecco un'idea cotto a metà: Si potrebbe fare molto bene con la scelta di un primo p leggermente più grande di n, quindi scegliere un x casuale compreso tra 1 e P-1 il cui ordine del moltiplicativo gruppo mod p è p-1 (ritiro xs casuali e di test quali soddisfano x ^ i! = 1 per i = n e che ti dà una sequenza di indici per la stampa.

Questa non è molto casuale, ma è possibile utilizzare la stessa tecnica più volte, prendendo gli indici sopra (+1) e servirsi di esse come gli esponenti di un altro modulo generatore x2 un altro primo p2 (avrete bisogno di n

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top