La méthode la plus efficace pour ... Chaîne aléatoire unique

Question

J'ai besoin d'insérer efficacement une chaîne RANDOM de 5 caractères dans une base de données tout en m'assurant qu'elle est UNIQUE. Générer la chaîne aléatoire n'est pas le problème, mais actuellement ce que je fais est de générer la chaîne et ensuite vérifier la DB si elle existe déjà ... si c'est le cas, je recommence.

Existe-t-il un moyen plus efficace de faire ce processus?

S'il vous plaît noter, je ne veux pas utiliser GUID ou toute autre chose qui est plus de 5 caractères .... Je dois coller à 5 caractères. PS: Je ne pense pas que cela fasse une différence, mais mes cordes sont toutes sensibles à la casse.

Voici la partie

Public Function GetRandomNumbers(ByVal numChars As Integer) As String 
    Dim chars As String() = { _ 
    "A", "B", "C", "D", "E", "F", _ 
    "G", "H", "I", "J", "K", "L", _ 
    "M", "N", "O", "P", "Q", "R", _ 
    "S", "T", "U", "V", "W", "X", _ 
    "Y", "Z", "0", "1", "2", "3", _ 
    "4", "5", "6", "7", "8", "9", _ 
    "a", "b", "c", "d", "e", "f", _ 
    "g", "h", "i", "j", "k", "l", _ 
    "m", "n", "o", "p", "q", "r", _ 
    "s", "t", "u", "v", "w", "x", _ 
    "y", "z"} 
    Dim rnd As New Random() 
    Dim random As String = String.Empty 
    Dim i As Integer = 0 
    While i < numChars 
     random += chars(rnd.[Next](0, 62)) 
     System.Math.Max(System.Threading.Interlocked.Increment(i), i - 1) 
    End While 
    Return random 
End Function 

Answer 1

Créez une table avec un grand groupe de chaînes de 5 caractères ajoutées en séquence (elles sont donc uniques) et ayant un GUID comme clé primaire. Ajoutez une colonne pour indiquer s'ils sont utilisés ou non.

Lorsque vous avez besoin d'un nouveau numéro, vous sélectionnez 1 dans le pool, vous commandez par le guid (de sorte qu'il devient aléatoire) et définissez le résultat comme "dépensé".

Answer 2

Vous pouvez générer un GUID « chaîne aléatoire » et utiliser uniquement les 5 premiers caractères?

Answer 3

Le caractère aléatoire est-il plus important ou l'unicité est-elle plus importante? - notez que j'ai dit "plus" important; Je comprends le fait que vous avez besoin des deux.

Si le caractère aléatoire est plus important, alors vous aurez besoin d'un moyen de suivre les valeurs historiques. La base de données elle-même (avec un index approprié) sera le meilleur moyen de le faire.

Si l'unicité est plus importante, utilisez simplement un compteur et mettez-le à zéro à cinq chiffres. Cela vous limitera bien sûr à 100 000 lignes, vous pouvez donc utiliser un compteur et une transformation dans l'espace des caractères (par exemple, 1 = "A", 2 = "B", 27 = "AA", etc.) .

Answer 4

Il existe une méthode pour sélectionner des mots uniques inutilisés par hasard, mais cela ne va probablement pas être mieux que ce que vous faites maintenant. Le principe est que vous déterminez les permutations des mots inutilisés, générez un nombre aléatoire en fonction du nombre de permutations inutilisées et choisissez celui-là.

Si vous utilisez par exemple un mot avec trois caractères, et seulement les caractères 0 et 1, il y a huit permutations possibles. Si vous avez déjà utilisé les combinaisons "010" et "100", vous obtiendrez quelque chose qui ressemble à ceci:

PI = indice de permutation
UI = indice de permutation utilisé

No. PI UI 
---------- 
000 0 0 
001 1 1 
010 2 - 
011 3 2 
100 4 - 
101 5 3 
110 6 4 
111 7 5 

Pour choisir une permutation non utilisée , vous générez simplement un nombre aléatoire de 0 à 5, et choisissez la permutation correspondante. Garder une liste de toutes les permutations possibles n'est bien sûr pas pratique, vous aurez donc besoin d'une fonction qui peut déterminer l'index de permutation de la chaîne, et une fonction qui peut déterminer la chaîne de l'index de permutation.

De même, pour déterminer quelles permutations sont inutilisées, vous devez vérifier quelles sont les valeurs utilisées, donc vous devez toujours interroger la table à un moment donné.

Answer 5

Si vous insérez la chaîne dans une table existante, remplie, vous devrez toujours vérifier si la chaîne n'existe pas (il ne doit pas s'agir d'un SELECT explicite). Vous pouvez soit manuellement, soit avoir une contrainte UNIQUE sur la colonne et laisser la base de données le faire. Donc, si la base de données renvoie une erreur parce que la chaîne est déjà là, en générer une autre.

Notez que si vous avez une table vide et que vous voulez la remplir avec plusieurs chaînes aléatoires, c'est un problème différent.

Answer 6

Je pense que vous devriez s'en tenir à votre idée d'origine. Mettre une contrainte unique sur l'index et laisser la base de données vérifier/rapporter des dupes pour vous serait une méthode assez efficace de vérification de dupe mais cette hypothèse dépend de certaines informations non fournies comme le nombre de lignes et la probabilité de rencontrer des dupes avec des données sélectionnées aléatoirement.

Le pré-remplissage complet d'un pool de séquences unique avec vos paramètres nécessite une table de 459 millions de lignes. Vous pouvez utiliser un filtre de bloom pour charger des statistiques gérables dans une base de données ou une mémoire principale et éviter les doublons, mais en fonction du nombre de lignes et de la configuration du filtre, cela peut entraîner la saturation du filtre lorsque le nombre de lignes est significatif. Comme le filtre peut signaler des faux positifs, vous devez vous assurer que vous ne vous retrouvez pas dans une situation où votre système est bloqué en essayant des permutations qui dépassent le filtre pour toujours.

Answer 7

Comme vous savez combien de temps votre mot doit être, pourquoi ne pas utiliser une approche arborescente? (Appelons-le marche aléatoire)

Dites ce que vous avez de mots. Générer une liste de tous les symboles s de S et relier un compteur pour chaque symbole et position possible dans la chaîne, essentiellement une matrice M de dimensions s fois n. Maintenant lancez vos dés et choisissez la première lettre et cherchez M (s, 1). Si M (s, 1) est plus grand ou égal au nombre de mots possibles commençant par s, relancez. Sinon, incrémenter M (s, 1). Répétez cette opération pour chaque lettre 1 jusqu'à n.

Devrait être assez rapide jusqu'à ce que vous ayez utilisé jusqu'à plusieurs mots.