Generando códigos únicos que son diferentes en dos dígitos

Question

Quiero generar números de código únicos (compuestos de 7 dígitos exactamente). El número de código se genera aleatoriamente y se guarda en la tabla MySQL.

Tengo otro requisito. Todos los códigos generados deben diferir en al menos dos dígitos. Esto es útil para evitar errores al escribir el código de usuario. Con suerte, evitará referirse a otro código de usuario mientras se realizan algunas operaciones, ya que es más improbable que pierda dos dígitos y coincida con otro código de usuario existente.

La generar algoritmo funciona simplemente les gusta:

1. Recuperación de todos los códigos anteriores si alguno de tabla de MySQL.
2. Genera un código a la vez.
3. Reste el código generado con todos los códigos anteriores.
4. Compruebe el número de dígitos distintos de cero en el resultado de la resta.
5. Si es> 1, acepte el código generado y añádalo a los códigos anteriores.
6. De lo contrario, salte a 2.
7. Repita los pasos del 2 al 6 para la cantidad de códigos solicitados.
8. Guarde los códigos generados en la tabla DB.

El algoritmo funciona bien, pero el problema está relacionado con el rendimiento. Lleva mucho tiempo terminar de generar los códigos cuando se solicita generar un gran número de códigos como: 10,000.

La pregunta: ¿Hay alguna forma de mejorar el rendimiento de este algoritmo?

Estoy usando perl + MySQL en el servidor de Ubuntu si eso importa.

Answer 1

¿Ha considerado alguna variante del algoritmo de Luhn? Luhn se utiliza para generar un dígito de control para cadenas de números en muchas aplicaciones, incluidos los números de cuenta de la tarjeta de crédito. Es parte del estándar ISO-7812-1 para generar identificadores. Capturará cualquier número que se ingrese con un dígito incorrecto, lo que implica que dos números válidos difieren en al menos dos dígitos.

Consulte Algoritmo :: LUHN en CPAN para una implementación perl.

Answer 2

no recupera los códigos existentes, simplemente generar un potencial código de nuevo y ver si hay alguna los conflictivos en la base de datos:

SELECT code FROM table WHERE abs(code-?) regexp '^[1-9]?0*$'; 

(donde el marcador de posición es el código recién generado).

Ah, me perdí la generación de muchos códigos a la vez parte. Hágalo así (completamente no probado):

my @codes = existing_codes(); 

my $frontwards_index = {}; 
my $backwards_index = {}; 
for my $code (@codes) { 
    index_code($code, $frontwards_index); 
    index_code(reverse($code), $backwards_index); 
} 

my @new_codes = map generate_code($frontwards_index, $backwards_index), 1..10000; 

sub index_code { 
    my ($code, $index) = @_; 
    push @{ $index{ substr($code, 0, length($code)/2) } }, $code; 
    return; 
} 

sub check_index { 
    my ($code, $index) = @_; 
    my $found = grep { ($_^$code) =~ y/\0//c <= 1 } @{ $index{ substr($code, 0, length($code)/2 } }; 
    return $found; 
} 

sub generate_code { 
    my ($frontwards_index, $backwards_index) = @_; 

    my $new_code; 
    do { 
     $new_code = sprintf("%07d", rand(10000000)); 
    } while check_index($new_code, $frontwards_index) 
     || check_index(reverse($new_code), $backwards_index); 
    index_code($new_code, $frontwards_index); 
    index_code(reverse($new_code), $backwards_index); 
    return $new_code; 
} 

Answer 3

Ponga los números del 0 al 9.999.999 en un árbol de búsqueda binaria aumentada. El aumento es para realizar un seguimiento de la cantidad de subnodos a la izquierda y a la derecha. Entonces, por ejemplo, cuando comienza su algoritmo, el nodo superior debe tener un valor de 5,000,000, y debe saber que tiene 5,000,000 nodos a la izquierda y 4,999,999 nodos a la derecha. Ahora crea una tabla hash. Para cada valor que ya haya utilizado, elimine su nodo del árbol de búsqueda binaria aumentada y agregue el valor a la tabla hash. Asegúrese de mantener el aumento.

Para obtener un valor único, siga estos pasos.

1. Utilice el nodo superior para determinar cuántos nodos quedan en el árbol. Digamos que te quedan n nodos. Elija un número aleatorio entre 0 y n. Usando el aumento, puede encontrar el n-ésimo nodo en su árbol en tiempo de registro (n).
2. Una vez que haya encontrado ese nodo, calcule todos los valores que invalidarían el valor en ese nodo. Digamos que su nodo tiene valor 1,111,111. Si ya tiene 2,111,111 o 3,111,111 o ... entonces no puede usar 1,111,111. Como hay otras 8 opciones por dígito y 7 dígitos, solo necesita verificar 56 valores posibles. Verifique si alguno de esos valores está en su hashtable. Si aún no ha utilizado ninguno de esos valores, puede usar su nodo aleatorio. Si has usado alguno de ellos, entonces no puedes.
3. Elimina tu nodo del árbol aumentado. Asegúrese de mantener la información aumentada.
4. Si no puede usar ese valor, regrese al paso 1.
5. Si puede usar ese valor, tiene un nuevo código aleatorio. Agrégalo a la tabla hash.

Ahora, verificando si hay un valor disponible toma O (1) tiempo en lugar de O (n) tiempo. Además, encontrar otro valor aleatorio disponible para verificar toma el tiempo O (log n) en lugar de ... ah ... No estoy seguro de cómo analizar tu algoritmo.

Para abreviar, si comienza desde cero y utiliza este algoritmo, generará una lista completa de códigos válidos en O (n log n). Como n es 10,000,000, tomará unos segundos o algo así.

¿Hice los cálculos allí mismo? Avíseme si eso no funciona o si necesito aclarar algo.

Answer 4

Utilice un hash.

Después de generar un código exitoso (que no esté en conflicto con ningún código existente), pero ese código en la tabla hash, y también poner los otros 63 códigos que difieren exactamente en un dígito en el hash.

Para ver si un código generado aleatoriamente entrará en conflicto con un código existente, simplemente verifique si ese código existe en el hash.

Answer 5

Howabout:

generar un código de 6 dígitos por autoincremental la anterior. Genere un código de 1 dígito incrementando el mod anterior 10. Concatene los dos.

Presto, garantizado para diferir en dos dígitos. : D

(Supongo que es "aleatorio" o al menos cuasialeatorio. En ese caso, genere una clave aleatoria de 6 dígitos, repita hasta que no sea un duplicado (es decir, haga la columna única, repita hasta que la inserción no falle la restricción), luego genere un dígito de control, como ya se dijo).