c# - rand - Generar una secuencia aleatoria y no repetitiva de todos los enteros en.NET

random.next c#

Question

¿Existe alguna forma en .NET de generar una secuencia de todos los enteros de 32 bits ( Int32 ) en orden aleatorio, sin repeticiones y de manera eficiente desde el punto de vista de la memoria? La eficiencia de la memoria significaría usar un máximo de unos cientos de mega bytes de memoria principal.

Idealmente, la secuencia debería ser algo así como un IEnumerable<int> , y devuelve lentamente el siguiente número en secuencia, solo cuando se solicite.

Hice algunas investigaciones rápidas y encontré algunas soluciones parciales para esto:

• Usar un registro de desplazamiento de retroalimentación lineal máximo - si entendí correctamente, solo genera los números en secuencia creciente y no cubre todo el rango
• El uso de Fisher-Yates u otros algoritmos de mezcla sobre colecciones - esto violaría las restricciones de memoria dado el amplio rango
• Mantener una colección tipo set y seguir generando un entero aleatorio (quizás utilizando Random ) hasta que no se repita, es decir, no está en el conjunto, aparte de posiblemente no satisfacer los requisitos de memoria, sería ridículamente lento al generar el último números en la secuencia.
• Las permutaciones aleatorias de más de 32 bits, sin embargo, no puedo pensar en una forma de garantizar la no repetibilidad.

¿Hay alguna otra forma de ver este problema, tal vez aprovechando el rango fijo de valores, que daría una solución que satisfaga los requisitos de memoria? ¿Tal vez las bibliotecas de clases .NET vienen con algo útil?

ACTUALIZACIÓN 1

Gracias a todos por sus ideas y sugerencias creativas para una solución. Trataré de implementar y probar pronto (tanto para la corrección como para la eficiencia de la memoria) las 2 o 3 soluciones más prometedoras propuestas aquí, publicar los resultados y luego elegir un "ganador".

ACTUALIZACIÓN 2

Intenté implementar la sugerencia de hvd en el comentario a continuación . Intenté usar tanto BitArray en .NET como mi implementación personalizada, ya que .NET one está limitado a int.MaxValue entradas int.MaxValue , por lo que no es suficiente para cubrir todo el rango de enteros.

Me gustó la simplicidad de la idea y estaba dispuesto a "sacrificar" esos 512 MB de memoria si funcionaba bien. Desafortunadamente, el tiempo de ejecución es bastante lento, gastando hasta decenas de segundos para generar el siguiente número aleatorio en mi máquina, que tiene una CPU Core i7 de 3.5 GHz. Desafortunadamente, esto no es aceptable si solicita muchos, muchos números aleatorios para ser generados. Sin embargo, creo que es predecible, es un algoritmo O (M x N) si no me equivoco, donde N es 2 ^ 32 y M es el número de enteros solicitados, por lo que todas esas iteraciones cobran su precio.

Idealmente, me gustaría generar el siguiente número aleatorio en O (1) tiempo, al mismo tiempo que cumplo con los requisitos de memoria, tal vez los siguientes algoritmos sugeridos aquí sean adecuados para esto. Voy a intentarlo tan pronto como pueda.

ACTUALIZACIÓN 3

Acabo de probar el generador lineal congruente y puedo decir que estoy bastante satisfecho con los resultados. Parece un fuerte contendiente para la posición de ganador en este hilo.

Corrección : todos los enteros generados exactamente una vez (utilicé un vector de bits para verificar esto).

Aleatoriedad : bastante bueno.

Uso de la memoria : excelente, solo unos pocos bytes.

Tiempo de ejecución : genera el siguiente entero aleatorio muy rápido, como se puede esperar de un algoritmo O (1). Generar cada entero tomó un total de aprox. 11 segundos en mi máquina.

En general, diría que es una técnica muy apropiada si no estás buscando secuencias altamente aleatorias.

ACTUALIZACIÓN 4

La técnica inversa multiplicativa modular descrita a continuación se comporta de manera bastante similar a la técnica LCG, lo cual no es sorprendente, ya que ambas se basan en la aritmética modular, aunque me pareció un poco menos sencillo implementarla para obtener secuencias aleatoriamente satisfactorias.

Una diferencia interesante que encontré es que esta técnica parece más rápida que LCG: generar toda la secuencia tomó aproximadamente 8 segundos, frente a 11 segundos para LCG. Aparte de esto, todas las demás observaciones sobre la eficiencia de la memoria, la corrección y la aleatoriedad son las mismas.

ACTUALIZACIÓN 5

Parece que el usuario TomTom eliminó su respuesta con Mersenne Twister sin previo aviso después de que señalé en un comentario que descubrí que genera números duplicados antes de lo requerido. Así que supongo que esto excluye por completo a Mersenne Twister.

ACTUALIZACIÓN 6

Skip32 otra técnica sugerida que parece prometedora, Skip32 , y aunque realmente me gustó la calidad de los números aleatorios, el algoritmo no es adecuado para generar todo el rango de números enteros en un tiempo aceptable. Por lo tanto, lamentablemente se queda corto en comparación con las otras técnicas que pudieron finalizar el proceso. Usé la implementación en C # a partir de here , por cierto, cambié el código para reducir el número de rondas a 1, pero todavía no puede finalizar de manera oportuna.

Después de todo, a juzgar por los resultados descritos anteriormente, mi elección personal para la solución va a la técnica modular inversos multiplicativos , seguida muy de cerca por el generador congruencia lineal . Algunos pueden argumentar que esto es inferior en ciertos aspectos a otras técnicas, pero teniendo en cuenta mis limitaciones originales, diría que les queda mejor.

Answer 1

¿Hay alguna manera en .NET

En realidad, esto se puede hacer en casi cualquier idioma

para generar una secuencia de todos los enteros de 32 bits (Int32)

Sí.

En orden aleatorio,

Aquí debemos ponernos de acuerdo sobre la terminología, ya que "al azar" no es lo que la mayoría de la gente cree que es. Más sobre esto en un momento.

sin repeticiones,

Sí.

y de una manera eficiente con la memoria?

Sí.

La eficiencia de la memoria significaría usar un máximo de unos cientos de mega bytes de memoria principal.

Ok, entonces ¿no sería aceptable usar casi ningún recuerdo? ;-)

Antes de llegar a la sugerencia, tenemos que aclarar el asunto de la "aleatoriedad". Algo que es verdaderamente aleatorio no tiene un patrón discernible. Por lo tanto, ejecutar el algoritmo millones de veces seguidas podría teóricamente devolver el mismo valor en todas las iteraciones. Si arroja el concepto de "debe ser diferente de la iteración anterior", entonces ya no es aleatorio. Sin embargo, al analizar todos los requisitos, parece que todo lo que se está pidiendo realmente es "diferentes patrones de distribución de los enteros". Y esto es factible.

Entonces, ¿cómo hacer esto de manera eficiente? Haz uso de inversas multiplicativas modulares . Lo usé para responder a la siguiente pregunta que tenía un requisito similar para generar datos de muestra no repetitivos y pseudoaleatorios dentro de ciertos límites:

Genera diferentes tiempos aleatorios en el intervalo dado

Primero aprendí sobre este concepto aquí ( genero ID numérico único al azar en SQL Server ) y puede usar cualquiera de las siguientes calculadoras en línea para determinar sus valores "Integer" y "Inversión Multiplicativa Modular (MMI)":

• http://planetcalc.com/3311/
• http://www.cs.princeton.edu/~dsri/modular-inversion-answer.php

Aplicando ese concepto aquí, usaría Int32.MaxSize como el valor del Módulo.

Esto daría una apariencia definida de distribución aleatoria sin posibilidad de colisiones y sin memoria necesaria para almacenar los valores ya utilizados.

El único problema inicial es que el patrón de distribución siempre es el mismo dados los mismos valores de "Entero" y "MMI". Por lo tanto, podría idear patrones diferentes agregando un valor interno generado "aleatoriamente" al valor inicial (como creo que lo hice en mi respuesta sobre la generación de datos de muestra en SQL Server) o puede pregenerar varias combinaciones de " Entero "y los valores correspondientes" MMI ", almacene aquellos en un archivo / diccionario de configuración y use una función aleatoria .NET para seleccionar uno al comienzo de cada ejecución. Incluso si almacena 100 combinaciones, casi no se usa la memoria (suponiendo que no esté en un archivo de configuración). De hecho, si almacena ambos como Int y el diccionario usa Int como índice, ¿entonces 1000 valores son aproximadamente 12k?

ACTUALIZAR

Notas:

• Hay un patrón en los resultados, pero no es discernible a menos que tenga suficientes en un momento dado para mirar en total. Para la mayoría de los casos de uso, esto es aceptable ya que ningún destinatario de los valores tendría una gran colección de ellos, o sabe que fueron asignados en secuencia sin ningún espacio (y que se requiere conocimiento para determinar si hay un patrón) .
• Solo se necesita 1 de los dos valores de variable - "Integer" y "Modular Multiplicative Inverse (MMI)" - en la fórmula para una ejecución en particular. Por lo tanto:
  • cada par da dos secuencias distintas
  • si se mantiene un conjunto en la memoria, solo se necesita una matriz simple, y suponiendo que el índice de la matriz es simplemente un desplazamiento en memoria desde la dirección base de la matriz, entonces la memoria requerida debe ser solo de 4 bytes * (es decir, 1024 opciones es solo 4k, ¿verdad?)

Aquí hay un código de prueba. Está escrito en T-SQL para Microsoft SQL Server ya que es donde trabajo principalmente, y también tiene la ventaja de hacerlo realmente fácil, como probar la exclusividad, los valores mínimos y máximos, etc., sin la necesidad de compilar nada. La sintaxis funcionará en SQL Server 2008 o posterior. Para SQL Server 2005, la inicialización de las variables aún no se había introducido, por lo que cada DECLARE que contenga an = simplemente tendría que separarse en DECLARE por sí misma y SET @Variable = ... para cualquier variable que se esté inicializando. Y el SET @Index += 1; necesitaría convertirse en SET @Index = @Index + 1; .

El código de prueba generará un error si proporciona valores que producen duplicados. Y la consulta final indica si hay vacíos, ya que se puede inferir que si la población de la tabla variable no produjo errores (por lo tanto no hay duplicados), y el número total de valores es el número esperado, entonces solo podría haber lagunas (es decir, falta valores) SI uno o ambos valores reales MIN y MAX están fuera de los valores esperados.

TENGA EN CUENTA que este código de prueba no implica que ninguno de los valores esté pregenerado o deba almacenarse. El código solo almacena los valores para probar la singularidad y los valores mínimo / máximo. En la práctica, todo lo que se necesita es la fórmula simple, y todo lo que se necesita para pasar es:

• la capacidad (aunque eso también podría estar codificado en este caso)
• el valor de MMI / Integer
• el "índice" actual

Entonces solo necesita mantener 2 - 3 valores simples.

DECLARE @TotalCapacity INT = 30; -- Modulo; -5 to +4 = 10 OR Int32.MinValue
                                 -- to Int32.MaxValue = (UInt32.MaxValue + 1)
DECLARE @MMI INT = 7; -- Modular Multiplicative Inverse (MMI) or
                      -- Integer (derived from @TotalCapacity)

DECLARE @Offset INT = 0; -- needs to stay at 0 if min and max values are hard-set
-----------
DECLARE @Index INT = (1 + @Offset); -- start

DECLARE @EnsureUnique TABLE ([OrderNum] INT NOT NULL IDENTITY(1, 1),
                             [Value] INT NOT NULL UNIQUE);
SET NOCOUNT ON;

BEGIN TRY
    WHILE (@Index < (@TotalCapacity + 1 + @Offset)) -- range + 1
    BEGIN
        INSERT INTO @EnsureUnique ([Value]) VALUES (
                 ((@Index * @MMI) % @TotalCapacity) - (@TotalCapacity / 2) + @Offset
                                                   );
        SET @Index += 1;
    END;
END TRY
BEGIN CATCH
    DECLARE @Error NVARCHAR(4000) = ERROR_MESSAGE();
    RAISERROR(@Error, 16, 1);
    RETURN;
END CATCH;

SELECT * FROM @EnsureUnique ORDER BY [OrderNum] ASC;
SELECT COUNT(*) AS [TotalValues],
       @TotalCapacity AS [ExpectedCapacity],
       MIN([Value]) AS [MinValue],
       (@TotalCapacity / -2) AS [ExpectedMinValue],
       MAX([Value]) AS [MaxValue],
       (@TotalCapacity / 2) - 1 AS [ExpectedMaxValue]
FROM   @EnsureUnique;

Answer 2

Buen rompecabezas. Algunas cosas vienen a la mente:

• Necesitamos almacenar qué elementos se han utilizado. Si aproximadamente es lo suficientemente bueno, es posible que desee utilizar un filtro de floración para esto. Pero dado que especifica específicamente que desea todos los números, solo hay una estructura de datos para esto: un vector de bits.
• Probablemente desee utilizar un algoritmo de generador pseudoaleatorio con un período largo.
• Y la solución probablemente implica el uso de algoritmo múltiple.

Mi primer intento fue descubrir cómo funciona la buena generación de números pseudoaleatorios con un simple vector de bits. Acepto colisiones (y por lo tanto una desaceleración), pero definitivamente no demasiadas colisiones. Este algoritmo simple generará aproximadamente la mitad de los números para usted en un período de tiempo limitado.

static ulong xorshift64star(ulong x)
{
    x ^= x >> 12; // a
    x ^= x << 25; // b
    x ^= x >> 27; // c

    return x * 2685821657736338717ul;
}

static void Main(string[] args)
{
    byte[] buf = new byte[512 * 1024 * 1024];
    Random rnd = new Random();

    ulong value = (uint)rnd.Next(int.MinValue, int.MaxValue);
    long collisions = 0;

    Stopwatch sw = Stopwatch.StartNew();

    for (long i = 0; i < uint.MaxValue; ++i)
    {
        if ((i % 1000000) == 0)
        {
            Console.WriteLine("{0} random in {1:0.00}s (c={2})", i, sw.Elapsed.TotalSeconds, collisions - 1000000);
            collisions = 0;
        }

        uint randomValue; // result will be stored here
        bool collision;

        do
        {
            value = xorshift64star(value);
            randomValue = (uint)value;

            collision = (buf[randomValue >> 4] & (1 << (int)(randomValue & 7))) != 0;
            ++collisions;
        }
        while (collision);

        buf[randomValue >> 4] |= (byte)(1 << (int)(randomValue & 7));
    }

    Console.ReadLine();
}

Después de aproximadamente 1,9 billones de números aleatorios, el algoritmo comenzará a detenerse.

1953000000 aleatorio en 283.74s (c = 10005932) [...] 2108000000 aleatorio en 430.66s (c = 52837678)

Entonces, por el bien del argumento, di que vas a usar este algoritmo para los primeros números de +/- 2 mil millones.

A continuación, necesita una solución para el resto, que es básicamente el problema descrito por el OP. Para eso, muestrearé números aleatorios en un buffer y combinaré el buffer con el algoritmo Knuth Shuffle. También puede usar esto desde el principio si lo desea.

Esto es lo que se me ocurrió (probablemente todavía con errores, así que prueba ...):

static void Main(string[] args)
{
    Random rnd = new Random();

    byte[] bloom = new byte[512 * 1024 * 1024];
    uint[] randomBuffer = new uint[1024 * 1024];

    ulong value = (uint)rnd.Next(int.MinValue, int.MaxValue);
    long collisions = 0;

    Stopwatch sw = Stopwatch.StartNew();
    int n = 0;

    for (long i = 0; i < uint.MaxValue; i += n)
    {
        // Rebuild the buffer. We know that we have uint.MaxValue-i entries left and that we have a 
        // buffer of 1M size. Let''s calculate the chance that you want any available number in your 
        // buffer, which is now:

        double total = uint.MaxValue - i;
        double prob = ((double)randomBuffer.Length) / total;

        if (i >= uint.MaxValue - randomBuffer.Length)
        {
            prob = 1; // always a match.
        }

        uint threshold = (uint)(prob * uint.MaxValue);
        n = 0;

        for (long j = 0; j < uint.MaxValue && n < randomBuffer.Length; ++j)
        {
            // is it available? Let''s shift so we get ''0'' (unavailable) or ''1'' (available)
            int available = 1 ^ ((bloom[j >> 4] >> (int)(j & 7)) & 1);

            // use the xorshift algorithm to generate a random value:
            value = xorshift64star(value);

            // roll a die for this number. If we match the probability check, add it.
            if (((uint)value) <= threshold * available)
            {
                // Store this in the buffer
                randomBuffer[n++] = (uint)j;

                // Ensure we don''t encounter this thing again in the future
                bloom[j >> 4] |= (byte)(1 << (int)(j & 7));
            }
        }

        // Our buffer now has N random values, ready to be emitted. However, it''s 
        // still sorted, which is something we don''t want. 
        for (int j = 0; j < n; ++j)
        {
            // Grab index to swap. We can do this with Xorshift, but I didn''t bother.
            int index = rnd.Next(j, n);

            // Swap
            var tmp = randomBuffer[j];
            randomBuffer[j] = randomBuffer[index];
            randomBuffer[index] = tmp;
        }

        for (int j = 0; j < n; ++j)
        {
            uint randomNumber = randomBuffer[j];
            // Do something with random number buffer[i]
        }

        Console.WriteLine("{0} random in {1:0.00}s", i, sw.Elapsed.TotalSeconds);
    }

    Console.ReadLine();
}

Volver a los requisitos:

¿Existe alguna forma en .NET de generar una secuencia de todos los enteros de 32 bits (Int32) en orden aleatorio, sin repeticiones y de manera eficiente desde el punto de vista de la memoria? La eficiencia de la memoria significaría usar un máximo de unos cientos de mega bytes de memoria principal.

Costo: 512 MB + 4 MB. Repeticiones: ninguna.

Es bastante rápido. Simplemente no es "uniformemente" rápido. Cada 1 millón de números, debe volver a calcular el búfer.

Lo que también es bueno: ambos algoritmos pueden funcionar juntos, por lo que primero se pueden generar los primeros números, por ejemplo, 2 billones de números muy rápido, y luego usar el segundo algoritmo para el resto.

Answer 3

Como se supone que sus números según su definición son aleatorios , por definición no hay otra manera que almacenarlos todos, ya que el número no tiene una relación intrínseca entre sí. Esto significa que debe almacenar todos los valores que utilizó para evitar que se vuelvan a utilizar.

Sin embargo, en informática no existe la aleatoriedad real. Por lo general, el sistema calcula un número aleatorio realizando operaciones de multiplicación con valores predeterminados enormes y valores de temporizador de tal manera que sobrepasan las limitaciones de memoria y, por lo tanto, aparecen seleccionados aleatoriamente. Entonces, o utilizas tu tercera opción o tienes que pensar en generar estos números pseudoaleatorios de forma que puedas reproducir la secuencia de cada número generado y verificar si hay algo nuevo. Obviamente, esto sería extremadamente costoso desde el punto de vista computacional, pero usted solicitó la eficiencia de la memoria.

De modo que podría almacenar el número con el que se sembró el generador aleatorio y la cantidad de elementos que generó. Cada vez que necesite un número nuevo, reinicie el generador e itere a través del número de elementos que generó + 1. Este es su nuevo número. Ahora resevee e itere a través de la secuencia nuevamente para verificar si ocurrió antes.

Entonces algo como esto:

int seed = 123;
Int64 counter = 0;
Random rnd = new Random(seed);

int GetUniqueRandom()
{
    int newNumber = rnd.Next();
    Random rndCheck = new Random(seed);

    counter++;

    for (int j = 0; j < counter; j++)
    {
        int checkNumber = rndCheck.Next();

        if (checkNumber == newNumber)
            return GetUniqueRandom();
    }

    return newNumber;        
}

EDITAR: Se señaló que el counter alcanzará un gran valor y no se sabe si se desbordará antes de obtener los 4 mil millones de valores o no.

Pensando en ello, una llamada recursiva tampoco es adecuada para esto, ya que casi con certeza dará lugar a un (y innecesariamente gastará toneladas de memoria), pero quería darte la idea general.

Answer 4

Si no necesita que los números aleatorios sean criptográficamente seguros, puede usar un generador congruente lineal .

Un LCG es una fórmula de la forma X_n + 1 = X_n * a + c (mod m), necesita memoria constante y tiempo constante para cada número generado.
Si se eligen los valores adecuados para el LCG, tendrá una longitud de período completa, lo que significa que generará cada número entre 0 y su módulo elegido.

Un LCG tiene un período completo si y solo si:

• El módulo y el incremento son relativamente primos, es decir, GCD(m, c) = 1
• a - 1 es divisible por todos los factores primos de m
• Si m es divisible por 4, a - 1 debe ser divisible por 4.

Nuestro módulo es 2 ^ 32 , lo que significa que debe ser un número de forma 4k + 1 donde k es un número entero arbitrario, y c no debe ser divisible por 2.

Si bien esta es una pregunta de C # he codificado un pequeño programa de C ++ para probar la velocidad de esta solución, ya que estoy más cómodo en ese idioma:

#include <iostream>
#include <stdlib.h>

class lcg {
private:
    unsigned a, c, val;
public:
    lcg(unsigned seed=0) : lcg(seed, rand() * 4 + 1, rand() * 2 + 1) {}
    lcg(unsigned seed, unsigned a, unsigned c) {
        val = seed;
        this->a = a;
        this->c = c;
        std::cout << "Initiated LCG with seed " << seed << "; a = " << a << "; c = " << c << std::endl;
    }

    unsigned next() {
        this->val = a * this->val + c;
        return this->val;
    }
};

int main() {
    srand(time(NULL));
    unsigned seed = rand();
    int dummy = 0;
    lcg gen(seed);
    time_t t = time(NULL);
    for (uint64_t i = 0; i < 0x100000000ULL; i++) {
        if (gen.next() < 1000) dummy++; // Avoid optimizing this out with -O2
    }
    std::cout << "Finished cycling through. Took " << (time(NULL) - t) << " seconds." << std::endl;
    if (dummy > 0) return 0;
    return 1;
}

Puede observar que no estoy usando la operación de módulo en ninguna parte de la clase lcg, eso es porque utilizamos un desbordamiento de enteros de 32 bits para nuestra operación de módulo.
Esto produce todos los valores en el rango [0, 4294967295] inclusive.
También tuve que agregar una variable ficticia para que el compilador no optimizara todo.
Sin optimización, esta solución finaliza en aproximadamente 15 segundos, mientras que con -O2, una optimización moderada termina en menos de 5 segundos.

Si la aleatoriedad "verdadera" no es un problema, esta es una solución muy rápida.

Answer 5

Un PRP de 32 bits en modo CTR parece ser el único enfoque viable para mí (su cuarta variante).

Tu también puedes

• Use un cifrado de bloque de 32 bits dedicado.

  Skip32, la variante de 32 bits de Skipjack es una opción popular.

  Como compensación entre calidad / seguridad y rendimiento, puede ajustar el número de rondas según sus necesidades. Más rondas son más lentas pero más seguras.

• Longitud-preservación-encriptación (un caso especial de formato-preservación-encriptación)

  El modo FFX es la recomendación típica. Pero en sus instancias típicas (por ejemplo, utilizando AES como cifrado subyacente) será mucho más lento que los cifradores de bloque dedicados de 32 bits.

Tenga en cuenta que muchas de estas construcciones tienen un defecto importante: incluso son permutaciones. Eso significa que una vez que haya visto 2 ^ 32-2 salidas, podrá predecir la penúltima salida con certeza, en lugar de solo el 50%. Creo que el documento de Rogaways AEZ menciona una forma de solucionar este error.

Answer 6

Voy a adelantar esta respuesta diciendo que me doy cuenta de que algunas de las otras respuestas son infinitamente más elegantes, y probablemente se ajusten mejor a sus necesidades que esta. Este es sin duda un enfoque de fuerza bruta para este problema.

Si es importante obtener algo verdaderamente aleatorio * (o pseudoaleatorio * suficiente para fines criptográficos), podría generar una lista de todos los enteros con anticipación y almacenarlos todos en el disco en orden aleatorio antes de tiempo. En el tiempo de ejecución de su programa, entonces lee esos números del disco.

A continuación se muestra el esquema básico del algoritmo que propongo para generar estos números. Todos los enteros de 32 bits pueden almacenarse en ~ 16 GiB de espacio en disco (32 bits = 4 bytes, 4 bytes / entero * 2 ^ 32 enteros = 2 ^ 34 bytes = 16 GiB, más cualquier sobrecarga que necesite el sistema de archivos / sistema operativo), y tomé "unos cientos de megabytes" para indicar que desea leer en un archivo de no más de 256 MiB a la vez.

1. Genere 16 GiB / 256 MiB = 64 archivos de texto ASCII con 256 MiB de caracteres "nulos" (todos los bits configurados a 0) cada uno. Denomine cada archivo de texto "0.txt" a "64.txt"
2. Realice un ciclo secuencialmente desde Int32.MinValue a Int32.MaxValue, omitiendo 0. Este es el valor del entero que está almacenando actualmente.
3. En cada iteración, genere un entero aleatorio de 0 a UInt32.MaxValue a partir de la fuente de aleatoriedad de su elección (generador aleatorio verdadero de hardware, algoritmo pseudoaleatorio, lo que sea). Este es el índice del valor que está almacenando actualmente.
4. Divida el índice en dos enteros: los 6 más significativos y los restantes 26. Utilice los bits superiores para cargar el archivo de texto correspondiente.
5. Multiplica los 26 bits más bajos por 4 y úsalo como un índice en el archivo abierto. Si los cuatro bytes que siguen a ese índice siguen siendo el carácter "nulo", codifique el valor actual en cuatro caracteres ASCII y almacene esos caracteres en esa posición. Si no son todos los caracteres "nulos", regrese al paso 3.
6. Repita hasta que todos los enteros hayan sido almacenados.

Esto garantizaría que los números provengan de una fuente conocida de aleatoriedad pero sigan siendo únicos, en lugar de tener las limitaciones de algunas de las otras soluciones propuestas. Tomaría mucho tiempo "compilar" (especialmente usando el algoritmo relativamente ingenuo anterior), pero cumple con los requisitos de eficiencia de tiempo de ejecución.

En tiempo de ejecución, ahora puede generar un índice de inicio aleatorio, luego leer los bytes en los archivos secuencialmente para obtener una secuencia de enteros única, aleatoria * y no repetitiva. Asumiendo que está usando una cantidad relativamente pequeña de enteros a la vez, incluso podría indexar aleatoriamente los archivos, almacenar qué índices ha usado y asegurarse de que un número no se repita de esa manera.

(* Entiendo que la aleatoriedad de cualquier fuente se reduce imponiendo la restricción de "unicidad", pero este enfoque debería producir números relativamente aleatorizados a la fuente original)

TL; DR - Mezcle los enteros con anticipación, almacénelos en un disco en una cantidad de archivos más pequeños, luego lea los archivos según sea necesario en el tiempo de ejecución.

Answer 7

One of the easiest solutions is to use an block encrytion algorithm like AES in countermode. You need a seed which equals the key in AES. Next you need a counter which is incremented for each new random value. The random value is the result of encrypting the counter with the key. Since the cleartext (counter) and the random number (ciphertext) is bijectiv and because of the pigeon hole principle the random numbers are unique (for the blocksize).

Memory efficiency: you only need to store the seed and the counter.

The only limmitation is that AES has 128 bit block size instead of your 32 bit. So you might need to increase to 128 bit or find a block cipher with 32 bit block size.

For your IEnumerable you can write a wrapper. The index is the counter.

Disclaimer: You are asking for non-repeating/unique: This disqualifies from random because normally you should see collisions in random numbers. Therefore you should not use it for a long sequence. See also https://crypto.stackexchange.com/questions/25759/how-can-a-block-cipher-in-counter-mode-be-a-reasonable-prng-when-its-a-prp

Answer 8

You could try this homebrew block-cipher:

public static uint Random(uint[] seed, uint m)
{   
    for(int i = 0; i < seed.Length; i++)
    {
        m *= 0x6a09e667;
        m ^= seed[i];
        m += m << 16;
        m ^= m >> 16;
    }
    return m;
}

Test code:

const int seedSize = 3; // larger values result in higher quality but are slower
var seed = new uint[seedSize];
var seedBytes = new byte[4 * seed.Length];
new RNGCryptoServiceProvider().GetBytes(seedBytes);
Buffer.BlockCopy(seedBytes, 0, seed, 0, seedBytes.Length);  

for(uint i = 0; i < uint.MaxValue; i++)
{
    Random(seed, i);
}

I haven''t checked the quality of its outputs yet. Runs in 19 sec on my computer for seedSize = 3 .