Algoritmo para imprimir una baraja de lista, en el lugar y con O(1) memoria

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

  •  18-09-2019
  •  | 
  •  

Pregunta

Después de la lectura esta pregunta Me empecé a preguntar:es posible tener un revolver algoritmo, el cual no modificar o copiar la lista original?

Para dejarlo claro:

Imagine que se le da una lista de objetos.El tamaño de la lista puede ser arbitraria, sino asumir que es bastante grande (digamos, 10.000.000 de elementos).Usted necesita para imprimir los elementos de la lista en orden aleatorio, y necesita hacerlo tan rápido como sea posible.Sin embargo, usted no debe:

  • Copia de la lista original, porque es muy grande y la copia sería un desperdicio de una gran cantidad de memoria (probablemente golpear los límites de la memoria RAM disponible);
  • Modificar la lista original, porque está ordenado de alguna manera y en alguna otra parte más adelante de ello depende que se ordena.
  • Crear un índice de la lista, porque, de nuevo, la lista es muy grande y la copia se toma todo demasiado tiempo y la memoria.(Aclaración:este es el significado de cualquier otra lista, que tiene el mismo número de elementos de la lista original).

Es esto posible?

Añadió: Más aclaraciones.

  1. Quiero que la lista se barajan en cierto modo aleatorio con todas las permutaciones igualmente probables (por supuesto, suponiendo que tenemos una adecuada función Rand() para empezar).
  2. Las sugerencias de que puedo hacer una lista de punteros, o una lista de índices, o de cualquier otra lista que hubiera el mismo número de elementos de la lista original, está explícitamente considerado como ineficaz por la pregunta original.Usted puede crear listas adicionales si lo desea, pero debe ser seria órdenes de magnitud más pequeño que el original de la lista.
  3. La lista original es como una matriz, y usted puede recuperar cualquier elemento de la misma por su índice en O(1).(Así que no hay lista doblemente vinculadas cosas, donde tienes que recorrer la lista para llegar a su punto deseado.)

Añadido 2:OK, vamos a ponerlo de esta manera:Usted tiene un HDD de 1 tb lleno de elementos de datos, cada una de 512 bytes grandes (un solo sector).Desea copiar todos los datos a otro de 1 tb disco duro mientras está barajando todos los elementos.Usted quiere hacer esto tan rápido como sea posible (solo pase de datos, etc).Tiene 512 MB de memoria RAM, y no contar con el espacio de intercambio.(Este es un escenario teórico, no tengo nada como esto en la práctica.Yo sólo quiero encontrar el perfecto algoritmo.elemento).

¿Fue útil?

Solución

Esta es una prueba muy sencilla que ningún esquema PRNG puede trabajar:

  

La idea PRNG tiene dos fases: primero, seleccionar un PRNG y su estado inicial; En segundo lugar, utilizar el PRNG para mezclar la salida. Bueno, hay N permutaciones posibles, por lo que necesita al menos N diferentes estados posibles de inicio, entrando en la fase 2. Esto significa que, al inicio de la fase 2 se debe tienen al menos log 2 N bits de estado, que no está permitido.

Sin embargo, esto no descarta esquemas en los que el algoritmo recibe nuevos bits aleatorios del ambiente a medida que avanza. Puede haber, por ejemplo, un PRNG que lee su estado inicial perezosamente y, sin embargo, no se garantiza que se repita. Podemos probar que no es?

Supongamos que tenemos un algoritmo de barajado perfecto. Imaginemos que empezar a implementarla, y cuando se hace la mitad, ponemos el ordenador en reposo. Ahora el estado completo del programa se ha guardado en alguna parte. Deje S como el conjunto de todos los estados posibles del programa podría ser en este punto medio.

Dado que el algoritmo es correcto y garantizado para terminar, hay una función f , que, dado el estado del programa salvado más cualquier cadena de tiempo suficiente de bits, produce una secuencia válida de disco lee y escribe completar la confusión. El propio ordenador implementa esta función. Pero considerarlo como una función matemática:

f : (S × bits) → secuencia de lee y escribe

A continuación, trivialmente, existe una función g que, por solamente el estado del programa guardado, produce el conjunto de las ubicaciones de discos aún para ser leído y escrito. (Basta con pasar una cuerda arbitraria de bits a f , y luego mirar los resultados.)

g S → conjunto de lugares para leer y escribir

El bit restante de la prueba es demostrar que el dominio de g contiene al menos N C N / 2 diferentes conjuntos independientemente de la elección del algoritmo. Si eso es cierto, debe haber al menos que muchos elementos de S , y así el estado del programa debe contener al menos log 2 N C N / 2 bits a la mitad del recorrido, en violación de los requisitos.

No estoy seguro de cómo demostrar que el último bit, sin embargo, ya sea o los lugares de puesta a-set-de-lugares-a-lea -to-escritura puede ser de baja entropía, dependiendo del algoritmo. Sospecho que hay algún principio evidente de la teoría de la información que puede cortar el nudo. Marcando esta comunidad wiki con la esperanza de que alguien va a suministrarla.

Otros consejos

Bueno, depende un poco en qué tipo de aleatoriedad que excepto por el roce, es decir, deben ser todos shufflings como probable, o puede ser sesgada la distribución.

Hay formas matemáticas para producir "al azar de aspecto" permutaciones de N enteros, por lo que si P es una permutación de tales 0..N-1 a 0..N-1, sólo puede iterar x de 0 a N -1 y lista de salida elemento L (P (x)) en lugar de L (x) y que haya obtenido un barajado. Tales permutaciones se pueden obtener, por ejemplo, utilizando aritmética modular. Por ejemplo, si N es primo, P (x) = (x * k) mod N es una permutación para cualquier 0

Cabe señalar que la exponenciación modular es la base de muchos algoritmos criptográficos (por ejemplo, RSA, Diffie-Hellman) y se considera una operación fuertemente pseudoaleatoria por los expertos en el campo.

Otra manera fácil (que no requiere números primos) es el primero en ampliar el dominio de modo que en lugar de N se tiene en cuenta que M es la menor potencia de dos por encima de N. Así, por ejemplo, Si n = 12 configura M = 16. A continuación, utiliza operaciones de bits biyectiva, por ejemplo. 

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

A continuación, cuando la salida de su lista, iterar x de 0 a M-1 y la salida L (P (x)) sólo si P (x) es en realidad

Una solución "verdadera, imparcial aleatorio" se puede construir mediante la fijación de un criptográficamente fuerte cifrado de bloque (por ejemplo AES) y una clave aleatoria (k) y entonces iterar la secuencia 

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

y emitir el elemento correspondiente de la secuencia si y sólo si AES (k, i)

No se te permite hacer una copia, modificación, o hacer un seguimiento de cuáles son los elementos que has visitado? Voy a decir que no es posible. A menos que esté malentendido su tercer criterio.

Yo considero que significa que no está permitido decir, hacer una serie de 10.000.000 booleanos correspondientes, se establece en true cuando se haya impreso el elemento correspondiente. Y no se le permite hacer una lista de los índices de 10.000.000, baraja la lista, e imprimir los elementos en ese orden.

Estos artículos son sólo 10.000.000 de referencias (o punteros) a elementos reales, por lo que su lista no será tan grande. Sólo ~ 40 MB en la arquitectura de 32 bits para todas las referencias + tamaño de las variables internas de esa lista. En caso de que sus artículos son más pequeños que el tamaño de referencia, sólo tienes que copiar toda la lista.

No es posible hacer esto con un de verdad generador de números aleatorios ya que usted tiene que:

  • recuerde que los números ya han sido elegidos y les pase (que requiere una operación O(n) lista de booleanos y un empeoramiento progresivo de los tiempos de ejecución como saltar más y más números);o
  • reducir la piscina después de cada selección (que requiere modificaciones a la lista original o separados O(n) lista para modificar).

Ninguno de esos son posibilidades en tu pregunta, así que voy a tener que decir "no, usted no puede hacerlo".

Lo que tendería a ir, pues en este caso es una máscara de bits de los valores utilizados, pero no con saltar, ya que, como se ha mencionado, los tiempos de ejecución de empeorar a medida que los valores utilizados se acumulan.

Una máscara de bits será sustancialmente mejor que el original de la lista de 39Gb (10 millones de bits es de sólo 1,2 M), muchas orden de magnitud menos como usted pidió incluso a pesar de que sigue siendo O(n).

Con el fin de obtener todo el tiempo de ejecución de problema, sólo generar un número al azar cada vez y, si el "utilizado" bits ya está establecido, explorar hacia adelante a través de la máscara de bits hasta encontrar uno que no conjunto.

Eso significa que usted no va a colgar alrededor, desesperado por el generador de números aleatorios para darle un número que no se ha usado todavía.Los tiempos de ejecución sólo se consigue tan malo como el tiempo necesario para examinar 1.2 M de datos.

Por supuesto, esto significa que el número específico elegido en cualquier momento es sesgada basada en los números que ya han sido elegidos, pero, dado que los números eran al azar de todos modos, el sesgo es aleatorio (y si los números no verdaderamente aleatorios, para empezar, entonces el sesgo no importa).

Y usted podría incluso la alternativa de la dirección de búsqueda (escaneo hacia arriba o hacia abajo) si quieres un poco más de variedad.

Línea de base:No creo que lo que estás pidiendo es factible, pero tenga en cuenta que me he equivocado antes, como mi esposa se hará constar, de forma rápida y con frecuencia: -), Pero, como con todas las cosas, por lo general hay maneras de conseguir alrededor de estos temas.

Suena imposible.

Pero 10.000.000 punteros de 64 bits es sólo alrededor de 76MB.

Un linear feedback shift register puede hacer casi lo que quieras-generar una lista de números hasta cierto límite, pero en un (razonablemente) orden aleatorio.Los patrones que produce son estadísticamente similares a lo que usted esperaría de probar la aleatoriedad, pero no es ni siquiera cerca de criptográficamente seguro.El Berlekamp-Massey algoritmo permite aplicar ingeniería inversa a un equivalente LFSR basado en una secuencia de salida.

Dada su requisito para obtener una lista de ~10.000.000 de artículos, te gustaría 24 bits máxima longitud LFSR, y simplemente descartar salidas más grande que el tamaño de su lista.

Para lo que vale, un LFSR es generalmente muy rápido en comparación con una típica lineal congruential PRNG en el mismo periodo.En el hardware, un LFSR es muy simple, consta de un N-bits de registro, y M 2-entrada XOR es (donde M es el número de grifos-a veces sólo un par, y rara vez más de una media docena o así).

Si hay suficiente espacio, se podría almacenar punteros de nodo en una matriz, crear un mapa de bits y obtener enteros aleatorios que apuntan al tema escogido siguiente. Si ya elegida (que se almacenan en su mapa de bits), a continuación, obtener más cercano (izquierda o derecha, se puede cambiar aleatoriamente eso), hasta que no se dejan artículos.

Si no hay espacio suficiente, entonces usted podría hacer iguales sin almacenar punteros de nodo, pero el tiempo van a sufrir (que es la compensación de tiempo-espacio ☺).

Se puede crear un pseudo aleatorio, la permutación 'seguro' usando un cifrado de bloques - ver aquí . Ellos idea clave es que, dado un cifrado de bloque de longitud N bits, puede utilizar 'plegado' para acortarlo a m

En esencia lo que necesita es un generador de números aleatorios que produce los números 0..n-1 exactamente una vez cada uno.

Aquí es una idea a medio cocer: Usted podría hacer bastante bien escogiendo un primo p ligeramente más grande que n, entonces la selección de un x aleatorio entre 1 y p-1 cuyo orden en el grupo mod multiplicativo p es p-1 (Pick XS azar y prueba de cuáles satisfacen x ^ i! = 1 para i = n y que le da una secuencia de índices para imprimir.

Esto no es muy aleatoria, pero se puede utilizar la misma técnica varias veces, teniendo los índices más arriba (1) y utilizarlos como los exponentes de otro módulo generador x2 otro p2 principales (necesitará n

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top