Algoritmo de generación de números aleatorios de código abierto en C++?

Question

Necesito generar números aleatorios en el rango 1 - 10000 continuamente sin duplicación. ¿Alguna recomendación?

Descripción: estamos construyendo una nueva versión para nuestra aplicación, que mantiene registros en Sqlite DB. en la última versión de nuestra aplicación, no teníamos una clave única para cada registro. Pero ahora, con la nueva versión mejorada, debemos admitir la instalación de importación desde la base de datos de la última versión. Entonces, lo que hacemos es leer todos y cada uno de los registros del antiguo DB y generar un número aleatorio para la clave única y almacenarlo en el nuevo DB. Aquí, muchos tenemos que importar hasta 10000 registros continuamente.

Answer 1

Bueno, con el tiempo tendrá que dejar de generarlos, o tendrá que duplicarlos.

En una computadora, sus opciones están bastante limitadas a Pseudo Generadores de números aleatorios (PRNG), y dada su restricción de que nunca se repiten, un PRNG es su mejor opción: datos aleatorios reales ocasionalmente duplicarán un número.

En su caso, consideraría usar un PRNG grande (32 bit o más) para mezclar sus 10,000 números, y luego enviar los números en orden aleatorio.

Una vez que se hayan agotado, puede volver a mezclar: dado que el PRNG es tan grande, podrá recorrer los números de 10k muchas veces antes de duplicar una secuencia.

Danos más información sobre lo que estás haciendo y podemos encontrar una mejor respuesta.

-Adam

Answer 2

Mersenne Twister es el actual mejor (aunque podría haber algunas semanas detrás de cualquier realmente nuevos descubrimientos). La fuente en casi todos los idiomas está disponible en algún lugar, y MT también se proporciona en Boost here

Answer 3

Boost.Random es una buena opción y funciona bien para mí. Sin embargo, si no necesita muchos generadores y distribuciones de números aleatorios, puede buscar otra biblioteca simplemente para no instalar todo el paquete de Boost.

Answer 4

¿Cómo aleatorio? Obviamente hay rand(), también hay cosas específicas del sistema operativo (Windows tiene algo en el CryptoAPI, por ejemplo). ¿Estás escribiendo algo (no recomendado), o simplemente buscando una función preexistente para usar?

Answer 5

TR1 tiene buena compatibilidad con números aleatorios, si su compilador lo admite.

De lo contrario Boost

Se trata básicamente de lo que se convirtió en TR1.

En cuanto a no obtener duplicados, quiere un shuffle. Puede ser bastante simple, pero hay algunas trampas si no lo haces bien. Jeff Atwood hizo un buen escritura hasta hace un tiempo:

http://www.codinghorror.com/blog/archives/001015.html

Answer 6

mtrand es agradable.

Answer 7

Boost probablemente hace algo que garantiza que no se repitan los números. Pero por un poco de diversión, esta es mi idea.

Nota: No intento generar mi rand en esa dirección, yace la locura.

#include <iostream> 
#include <vector> 
#include <algorithm> 


class GaranteedNoRepeatRandom 
{ 
    public: 
     GaranteedNoRepeatRandom(int limit) 
      :data(limit) 
      ,index(0) 
     { 
      for(int loop=0;loop < limit;++loop) 
      { data[loop] = loop; 
      } 
      // Note: random_shuffle optionally takes a third parameter 
      // as the rand number generator. 
      std::random_shuffle(&data[0],&data[0]+limit); 
     } 

     unsigned int rand() 
     { 
      unsigned int result = data[index]; 
      index = (index+1) % data.size(); 

      // Add code to re-shuffle after index wraps around 
      return result; 
     } 
    private: 
     std::vector<unsigned int>    data; 
     std::vector<unsigned int>::size_type index; 
}; 

int main() 
{ 
    GaranteedNoRepeatRandom  gen(10000); 

    for(int loop =0;loop < 10;++loop) 
    { 
     std::cout << gen.rand() << "\n"; 
    } 
} 

Answer 8

Numerical Recipes in C tiene un capítulo completo dedicado a la generación de números aleatorios. Hay algunas implementaciones allí. De simple y directo a complejo con buenas propiedades estadísticas.

Answer 9

¿Es correcto cuestionar la idea de utilizar un número aleatorio como la clave única para el registro de la base de datos? No estoy familiarizado con sqlite, pero vale la pena investigar si es compatible internamente con algún tipo de identificador de columna único. SQL Server tiene columnas de 'identidad', por ejemplo, y Oracle tiene 'secuencias', que tienen el mismo propósito.

Answer 10

Generar números aleatorios grandes. Digamos 128 bits. Las probabilidades de que dos de esos números sean iguales en un conjunto de 10000 son ridículamente pequeñas (del orden de n^2/2^b, donde n = número de números necesarios yb = número de bits utilizados). Con suficientes bits, las probabilidades serán menores que las probabilidades de que tu rayo se corrompa con un rayo cósmico, de modo que tu algoritmo falla de todos modos. Tenga cuidado de que el espacio del que está dibujando los números aleatorios realmente tenga la cantidad de bits que está buscando. Es fácil generar erróneamente números de 128 bits de un conjunto de 32 bits (es decir, solo hay 2^32 posibilidades aunque esté generando los números del 1 al 2^128). Los generadores de números aleatorios en la biblioteca de impulso pueden hacerlo correctamente. Por cierto: si no te gustan los 128 bits, entonces usa 256 bits o más hasta que te sientas cómodo de que no hay posibilidad práctica de una colisión hash. Si solo tiene que hacer esto una vez, simplemente use el método de mezcla ya mencionado en una respuesta anterior. Eso tendrá la ventaja de generar un hash perfecto.

Answer 11

http://random.org/ si necesita verdaderamente números aleatorios

Answer 12

Si bien es posible que tenga un requisito para generar una secuencia de valores que no se repiten, no se puede llamar el resultado "al azar". La aleatoriedad verdadera tiene menos que ver con la falta de repetición que con la distribución de valores en una secuencia.

Answer 13

Si realmente debe estar en el rango de 1 a 10,0000 sin repeticiones, pero no secuencial, entonces probablemente sea mejor primero crear una matriz secuencial de 10000 elementos y luego mezclarlos.

Sin embargo, estoy de acuerdo con los comentarios sobre la pregunta original. No veo valor en hacerlos no secuenciales.

Alternativamente, en el único & no secuencial son importantes, entonces el rango de 1 a 10,000 se vuelve cuestionable. Probablemente sea mejor simplemente usar un GUID.

Answer 14

La generación de números aleatorios es demasiado importante como para dejarla al azar. - Robert R. Coveyou, Oak Ridge National Laboratory