Pregunta Generar permutación aleatoria de lista enorme (en Python)


Me gustaría crear una permutación aleatoria de los números. [1,2,...,N] dónde N es un gran numero Así que no quiero almacenar todos los elementos de la permutación en la memoria, sino iterar sobre los elementos de mi permutación particular sin tener los valores anteriores en la memoria.

¿Alguna idea de cómo hacer eso en Python?


5
2018-06-03 09:06


origen


Respuestas:


Una posibilidad es utilizar un cifrado. Dado que el cifrado es reversible, es decir, uno a uno, para una clave dada, obtendrá los mismos números que cifró pero en un orden diferente.

Necesita un código de bloque con un tamaño de bloque lo suficientemente grande como para incluir su máximo N. Use DES en el modo ECB para N = 2 ^ 64 - 1. Utilice AES en el modo ECB para N = 2 ^ 128 - 1. Para otros tamaños, ya sea utilizar Cifrado de pudin aplastante, que tiene tamaño de bloque variable, o escribe tu propio sencillo Cifrado de Feistel. Supongo que solo necesitas un shuffle, no un shuffle criptográficamente seguro.

Si la salida es mayor que N, entonces simplemente vuelva a cifrar hasta que sea menor que N, la propiedad 1-a-1 asegura que la cadena de grandes números también sea única.

No es necesario almacenar la matriz completa en la memoria, cada número puede cifrarse según sea necesario. Sólo la clave y el algoritmo de cifrado son necesarios. Una pequeña complicación es que los cifrados en bloque funcionan en [0 ... N-1]; Es posible que necesites un código extra para lidiar con los extremos.


6
2018-06-03 11:53



Este es un problema genérico y no es específico de Python. En la mayoría de los idiomas, incluso cuando se usan iteradores para usar estructuras, toda la estructura se guarda en la memoria. Por lo tanto, los iteradores se utilizan principalmente como herramientas "funcionales" y no como herramientas de "optimización de memoria".

En Python, muchas personas terminan usando mucha memoria debido a que tienen estructuras muy grandes (diccionarios, etc.). Sin embargo, todas las variables-objetos del programa se almacenarán en la memoria de cualquier manera. La única solución es la serialización de los datos (guardar en sistema de archivos, base de datos, etc.).

Entonces, en su caso, podría crear una función personalizada que crearía la lista de permutaciones. Pero, en lugar de agregar cada elemento de la permutación a una lista, guardaría el elemento en un archivo (o en una base de datos con la estructura correspondiente). Luego, podrá recuperar una por una cada una de las permutaciones del archivo (o la base de datos), sin llevar la lista completa a la memoria.

Sin embargo, como se mencionó anteriormente, siempre deberá saber en qué permutación se encuentra actualmente. Para evitar recuperar todas las permutaciones creadas de la base de datos (lo que crearía el mismo cuello de botella), podría tener un índice para cada lugar que contenga el símbolo usado en la permutación generada anteriormente (y crear las permutaciones agregando los símbolos y una secuencia predefinida) .


0
2018-06-03 09:25