algorithm - metaheuristica - Buen algoritmo para la generación aleatoria única de IDs

colonia de hormigas metaheuristica

Question

Necesito generar una identificación aleatoria, alfanumérica, 6 caracteres, como la identificación para el servicio de enlace corto.

Actualmente, genero un código aleatorio de 6 caracteres, busco en la base de datos para ver si se ha usado antes, y si lo ha hecho, repita el proceso. Necesito que sea único para todas las 36 ^ 6 combinaciones. A medida que el sistema crece, peor es su rendimiento.

¿Existe un buen enfoque conocido que minimice golpear la base de datos, conserve el estado globalmente y no tome más de 100 ms en la búsqueda?

Gracias por cualquier ayuda

Answer 1

Este problema tiene una solución bien conocida:

http://en.wikipedia.org/wiki/Linear_congruential_generator

Solo genere el siguiente número aleatorio con su LCG, luego conviértalo a base 36 y escriba la cadena pseudoaleatoria correspondiente.

¡Buena suerte!

Answer 2

Use números secuenciales, para que nunca tenga que ir a la base de datos buscando si ya existe una clave. Solo necesita realizar un seguimiento del número máximo asignado hasta el momento.

Para hacer este ID secuencial alfanumérico, conviértalo a la base 36.

Si no te gusta el hecho de que las primeras ID asignadas se vean como 000000 , 000001 , ... 00000z , 000010 , ..., puedes hacer uso de un truco matemático: mantener internamente la ID numérica secuencial, pero para la representación externa visible para el usuario, multiplíquelo (mod 36 ^ 6) por un primo grande más pequeño que 36 ^ 6-1 - 1679979167 sería una opción decente, antes de convertir a la base 36. Esto hará que sus ID aparezcan al azar El usuario a pesar de que realmente no lo son.

Aquí hay una muestra de python con salida:

def baseN(num,b,numerals="0123456789abcdefghijklmnopqrstuvwxyz"):
    return ((num == 0) and numerals[0]) or (baseN(num // b, b, numerals).lstrip(numerals[0]) + numerals[num % b])

for internalID in range(1,200):
    mangled = (internalID*1679979167)%(36**6)
    print internalID, mangled, baseN(mangled,36)

(El código baseN es jellyfishtree''s desde here )

1 1679979167 rs7s7z
2 1183175998 jkfkfy
3 686372829 bcncnx
4 189569660 34v4vw
5 1869548827 ux2x3v
6 1372745658 mpapbu
7 875942489 ehihjt
8 379139320 69q9rs
9 2059118487 y1y1zr
10 1562315318 pu5u7q
11 1065512149 hmdmfp
12 568708980 9eleno