Algoritmo para generar un número aleatorio

Question

Estoy tratando de generar un número aleatorio y emitirlo en una tabla en una base de datos para un user_id en particular. El truco es que el mismo número no se puede usar dos veces. Hay un millón de maneras de hacerlo, pero espero que alguien muy interesado en algoritmos tenga una manera ingeniosa de resolver el problema en una solución elegante en la que se cumplan los siguientes criterios:

1) La menor cantidad de consultas a la base de datos está hecha. 2) Se realiza la menor cantidad de rastreo a través de una estructura de datos en la memoria.

Básicamente la idea es hacer lo siguiente

1) Crear un número aleatorio de 0 a 9999999
2) Compruebe la base de datos para ver si existe el número
O
2) Consultar la base de datos para todos los números
3) Vea si el resultado devuelto coincide con lo que vino del db
4) Si coincide, repita el paso 1, si no, se resuelve el problema.

Gracias.

Answer 1

No, su algoritmo no es escalable. Lo que he hecho antes es emitir números en serie (+1 cada vez) y luego pasarlos a través de una operación XOR para mezclar los bits y así darme un número aparentemente aleatorio. Por supuesto, no son realmente al azar, pero se ven así para los ojos de los usuarios.

---

[Editar] Información adicional

la lógica de este algoritmo es la siguiente se utiliza una secuencia conocida a generar números únicos y entonces se forma determinista manipularlos, por lo que no se ven en serie más . La solución general es usar alguna forma de encriptación, que en mi caso era un XOR flipflop, porque es lo más rápido posible, y cumple la garantía de que los números nunca colisionarán.

Sin embargo, puede utilizar otras formas de cifrado, si quieres prefieren aún más números aleatorios que buscan, sobre la velocidad (dicen que no es necesario para generar identificadores de muchos a la vez). Ahora, el punto importante al elegir un algoritmo de cifrado es "la garantía de que los números nunca colisionarán". Y una forma de probar si un algoritmo de cifrado puede cumplir esta garantía es comprobar si tanto el número original como el resultado de el cifrado tienen el mismo número de bits, y que el algoritmo es reversible (biyección).

[Gracias a Adam Liss & CesarB para exapanding en la solución]

Answer 2

Creo que descubrirá que realmente no quiere hacer esto. A medida que aumentan los números en la base de datos, puede pasar demasiado tiempo en el ciclo "asegúrese de que no se tome este número".

Personalmente, he tenido suerte con hashes como alternativa, pero para llegar a una solución mejor, realmente necesito saber por qué quieres hacerlo de esta manera.

Answer 3

Mi experiencia simplemente fue usar el RNG en PHP. Encontré que usando un cierto tamaño de número (estoy usando un int, entonces tengo un máximo de 4G). Ejecuté algunas pruebas y descubrí que, en promedio, en 500,000 iteraciones, obtuve 120 duplicados individuales. Nunca obtuve un triplicado después de ejecutar el ciclo un montón de veces. Mi "solución" fue simplemente insertar y verificar si falla, luego generar una nueva ID y volver.

Mi consejo es hacer lo mismo y ver cuál es su tasa de colisión & c y ver si es aceptable para su caso.

Esto no es óptima, por lo que si alguien tiene sugerencias estoy buscando también :)

EDIT: estaba limitado a un ID de 5 dígitos ([a-zA-Z0-9] {5,5 }), cuanto más larga sea la identificación (más combinación, las pocas colisiones). Un md5 del correo electrónico casi nunca entraría en conflicto, por ejemplo.

Answer 4

El problema es que si va a generar números aleatorios es muy es posible producir duplicados infinatly.

sin embargo:

<?php 
//Lets assume we already have a connection to the db 
$sql = "SELECT randField FROM tableName"; 
$result = mysql_query($sql); 
$array = array(); 
while($row = mysql_fetch_assoc($result)) 
{ 
    $array[] = $row['randField']; 
} 
while(True) 
{ 
    $rand = rand(0, 999999); 
    if(!in_array($rand)) 
    { 
     //This number is not in the db so use it! 
     break; 
    } 
} 
?> 

Mientras que esto va a hacer lo que usted quiere también, que es una mala idea ya que esto no se escala por mucho tiempo, consiguiera la matriz se llega a grande y, tardarían mucho tiempo para generar un azar que aún no está en su db.

Answer 5

Suponiendo:

• Se necesita la aleatoriedad de singularidad, no para la seguridad
• Su user_id es de 32 bits
• Tu límite del 9999999 fue sólo un ejemplo

que podría hacer algo tan simple como tener el número aleatorio como un entero de 64 bits, con los 32 bits superiores que contienen la marca de tiempo (en el inserto de fila) y los 32 bits inferiores el user_id. Eso sería exclusivo incluso para varias filas con el mismo usuario, siempre que use una resolución adecuada en su marca de tiempo, dependiendo de la frecuencia con la que agregue filas nuevas para el mismo usuario. Combine con una restricción única en la columna aleatoria y capte cualquier error de este tipo en su lógica y luego simplemente vuelva a intentarlo.

Answer 6

Es fácil diseñar un generador de números pseudoaleatorio con un largo período de no repetición; p.ej. this one, que se utiliza para lo mismo que lo desea.

Por cierto, ¿por qué no emitir el ID de usuario secuencialmente?

Answer 7

PHP ya tiene una función para esto, uniqid. Genera un uuid estándar que es excelente si tiene que acceder a los datos de otros lugares. No reinventar la rueda.

Answer 8

¿Desea una solución over-the-top?

Supongo que la aleatoriedad no tiene la intención de ser de calidad de encriptación, sino solo lo suficiente para desalentar la adivinación de la longevidad de un usuario, por ID_usuario.

Durante el desarrollo, genere una lista de los 10 millones de números en forma de cadena.

Opcionalmente, realice una transformación simple, como agregar una cadena constante al centro. (Esto es solo en caso de que el resultado sea demasiado predecible).)

Páselos a una herramienta que genere Perfect Hash functions, como gperf.

El código resultante se puede utilizar para codificar rápidamente la id del usuario en tiempo de ejecución en un valor hash exclusivo que garantiza que no chocará con ningún otro valor hash.

Answer 9

¿Por qué no utiliza un GUID? La mayoría de los lenguajes deben tener una forma integrada de hacerlo. Se garantiza que es único (con límites muy razonables).

Answer 10

me gusta la idea de Oddthinking, pero en lugar de elegir la función hash más fuerte del mundo, usted podría simplemente:

• Generar el MD5 de los primeros 10 millones de números (expresadas como cadenas, + un poco de sal)
• Comprobar si hay duplicados fuera de línea, es decir, antes de entrar en la producción (supongo que no habrá ninguna)
• tienda los duplicados de una matriz en algún lugar
• Cuando se inicia la aplicación, cargue la matriz
• Cuando quiera insertar una ID, elija el siguiente número, calcule su MD5, verifique si está en la matriz, y si no lo está utilizando como ID en la base de datos. De lo contrario, elija el siguiente número

Los MD5 son rápidos, y comprobar si una cadena pertenece a una matriz le evitará un SELECCIONAR.

Answer 11

Prueba el comunicado en MySQL SELECT CAST (RAND() * 1000000 AS INT)

Answer 12

De hecho, he escrito anteriormente an article about this. Toma el mismo enfoque que la respuesta de Robert Gould, pero además muestra cómo acortar un cifrado de bloque a una longitud adecuada usando xor plegado, y luego cómo generar las permutaciones en un rango que no es una potencia de 2, conservando al mismo tiempo el propiedad de singularidad.

Answer 13

Probablemente no entiendo su punto, pero ¿qué pasa con los aumentos de auto?

Answer 14

Si realmente desea obtener números "aleatorios" de 0 a 9 999 999, entonces la solución es hacer la "aleatorización" una vez, y luego almacenar el resultado en su disco.

No es difícil obtener el resultado que desea, pero creo que es más como "hacer una larga lista con números" que "obtener un número aleatorio".

$array = range(0, 9999999); 
$numbers = shuffle($array); 

También necesita un puntero a la posición actual en $ números (guárdelo en una base de datos); comience con 0 e increméntelo cada vez que necesite un nuevo número. (O puede usar array_shift() o array_pop(), si no desea utilizar punteros.)

Answer 15

Un algoritmo PRNG (generador de números aleatorios) correcto tendrá un tiempo de ciclo durante el cual nunca estará en el mismo estado. Si expone el estado completo del PRNG en el número obtenido de él, obtendrá un número garantizado único para el período del generador.

A PRNG simple que hace esto se llama el 'Linear Congruential' PRNG que itera una fórmula:

X(i) = AX(i-1)|M 

Usando el par de factores puede obtener un periodo de 2^30 (aproximadamente 1 mil millones) de un PRNG simple con un acumulador de 32 bits. Tenga en cuenta que necesitará una variable temporal larga larga de 64 bit para mantener la parte intermedia 'AX' del cálculo. La mayoría, si no todos, los compiladores de C admitirán este tipo de datos. También debería poder hacerlo con un tipo de datos numéricos en la mayoría de los dialectos SQL.

Con los valores correctos de A y M podemos obtener un generador de números aleatorios con buenas propiedades estadísticas y geométricas. Hay un famoso artículo sobre esto escrito por Fishman y Moore.

Para M = 2^31 - 1 podemos obtener los valores de A a continuación para obtener un PRNG con un largo período (2^30 IIRC).

buenos valores de A:

742,938,285 
950,706,376 
1,226,874,159 
62,089,911 
1,343,714,438 

en cuenta que este tipo de generador es (por definición) no criptográficamente seguro. Si conoce el último número generado a partir de él, puede predecir qué hará a continuación. Lamentablemente, creo que no se puede obtener seguridad criptográfica y no repetibilidad garantizada al mismo tiempo. Para que un PRNG sea criptográficamente seguro (por ejemplo, Blum Blum Shub), no puede exponer el estado suficiente en un número generado para permitir que se prediga el siguiente número en la secuencia. Por lo tanto, el estado interno es más amplio que el número generado y (para tener una buena seguridad) el período será más largo que el número de valores posibles que se pueden generar. Esto significa que el número expuesto no será único dentro del período.

Por razones similares, el mismo se puede decir de los generadores de periodo largo como el Mersenne Twister.

Answer 16

hay un par de maneras de hacer esto de una manera que sería construir una matriz con los números 0000000 a través de 9999999 y luego elegir una selección al azar de estos números en esta matriz y cambiar los valores de los números escogidos con el valor más alto Max luego reducir max por 1 y recoger otro miembro aleatorio de esta matriz hasta el nuevo máximo

cada vez que la reducción de Max por uno

por ejemplo (en la base): (a la derecha son los comentarios que deben eliminarse en el programa real) Rndfunc es una llamada a la función de generador de cualquier número al azar que está utilizando

dim array(0 to 9999999) as integer 
for x% = 1 to 9999999 
array(x%)=x% 
next x% 
maxPlus = 10000000 
max =9999999 
pickedrandom =int(Rndfunc*maxPlus) picks a random indext of the array based on  
            how many numbers are left 
maxplus = maxplus-1 
swap array(pickedrandom) , array(max) swap this array value to the current end of the 
            array 
max = max -1     decrement the pointer of the max array value so it 
           points to the next lowest place.. 

continuación, seguir haciendo esto para cada número que desea elegir, pero deberá tener la opción de utilizar matrices muy grandes

el otro método sería el siguiente: generar un número y almacenarlo en una matriz que puede crecer dinámicamente y luego seleccionar un nuevo número y compararlo con el valor que está a medio camino entre el primero y el último elemento de la matriz, en este caso sería el primer número elegido si coincide escoja otro número aleatorio, ordene la matriz de acuerdo al tamaño y si no hay coincidencia, dependiendo del clima es mayor o menor que el número que comparó con usted, suba o baje en la lista la mitad de la mitad distancia, cada vez que no coincide y es mayor o menor de lo que está comparando.

cada vez que lo reduce a la mitad hasta que alcanza un tamaño de hueco de uno, comprueba una vez y se detiene porque no hay coincidencia, luego el número se agrega a la lista y la lista se reorganiza en orden ascendente, etc. hasta que termine de seleccionar números aleatorios ... espero que esto ayude ...

Answer 17

Si desea asegurarse de que los números aleatorios no se repitan, necesita un generador de números aleatorio no repetitivo (como se describe here) .

La idea básica es que la siguiente fórmula seed * seed & p será producido no repetidos números aleatorios para cualquier entrada x such that 2x < p y p - x * x % p produce todos los demás de números aleatorios aswell no se repite, pero sólo si p = 3 mod 4. Así que, básicamente, todo lo que necesita es un único número primo tan cerca de 9999999 como sea posible. De esta forma, el esfuerzo puede reducirse a un solo campo de lectura, pero con la desventaja de que se generan IDs demasiado grandes o se generarán muy pocos ID.

Este algoritmo no se permuta muy bien, por lo que recomiendo combinarlo con XOR o adición o algún otro enfoque para cambiar el valor exacto sin destruir la relación 1 a 1 entre las semillas y su valor generado .