8
votes

Générer un code unique aléatoire

J'ai besoin de générer un code numérique à neuf chiffres (de préférence aléatoire) qui est unique pour une journée donnée (le même numéro ne peut plus être généré le même jour). Je pensais utiliser HHMMSSMMM (heures, minutes, secondes et millisecondes) pour générer le code unique mais n'est pas vraiment aléatoire. Cette méthode de génération de code est accessible par plusieurs méthodes en même temps afin de pouvoir mettre un verrou sur la méthode. Mais cela garantira-t-il que le nombre est unique car il est possible que la génération de nombre puisse prendre moins d'une milliseconde et deux threads obtiennent le même numéro?

Y a-t-il un meilleur moyen de générer un code numérique unique aléatoire unique pour une journée donnée? Le nombre de chiffres peut être compris entre 6 et 9 chiffres.

edit: Le nombre de nombres aléatoires à générer dépend du nombre de transactions. Initialement, le nombre pourrait être plus bas mais sur une période de temps, il peut devenir très élevé (multiples transactions par seconde). Par conséquent, je ne voudrais pas comparer le nombre à une liste utilisée car cela pourrait avoir des problèmes de performance.

aléatoire est nécessaire car ce nombre sera entré par l'utilisateur sur le téléphone. Ce numéro est le seul moyen de relier la transaction en ligne avec la transaction téléphonique afin que je ne souhaite pas que l'utilisateur entrait un numéro différent par erreur.

La génération de nombres aléatoires doit avoir lieu dans une application ASP.NET MVC.


15 commentaires

@achinth's doivent-ils être numéros ?


Je pense que vous avez déjà répondu à votre question. La question il y a sa prévisibilité.


Un système régulier.Uuid ne fera pas?


Ils doivent être des chiffres seulement !!


@TZUP C'est pourquoi je lui ai demandé. Avez-vous un moyen de convertir un objet GUID GUT à un numéro en essayant de les garder aussi uniques que dans le GUID?


Il ne peut pas être supérieur à 9 chiffres et doit être un numéro car on peut avoir besoin d'entrer dans ce numéro sur un téléphone.


Vous omettez un peu d'informations cruciales: Combien de ces nombres aléatoires à neuf chiffres uniques créez par jour? Parce que si vous créez deux ou trois par jour, c'est un problème beaucoup plus facile à résoudre que si vous créez vingt millions. Si vous créez un billion de dollars par jour, le problème n'est pas satisfable; Il n'y a pas beaucoup de neuf chiffres disponibles. (Par coïncidence, je pose souvent la question de votre question comme un problème d'entrevue; il est étonnant du nombre de candidats qui ne pensent jamais à demander combien de numéros concernés.)


En outre, au sujet du temps: N'oubliez pas aussi que le jour où l'heure d'épargne de la lumière du jour "tombe", il y a deux heures entières ce jour-là quand deux temps physiques peuvent avoir la même horloge temps. L'heure de l'horloge n'est pas unique, alors n'essayez pas de l'utiliser comme source d'unicité.


Pouvez-vous également décrire pourquoi "aléatoire" est important? Il existe de nombreuses raisons différentes de quelque chose à être "aléatoire" et chacun place une exigence différente sur le générateur de randomneurs. Le hasard cryptographique est très différent de la pseudo-aléatoire, par exemple. Avez-vous réellement besoin de non-prévisibilité pour une raison de sécurité?


@ERIC: Votre interview est-elle disponible sur le net? Je me demandais si vous avez une liste fixe de questions que vous utilisez tout le temps ou que vous les faites, car vous allez dans l'entretien, en fonction de la personne?


@Joan: Je n'utilise plus cette question si souvent, je pourrais donc le bloguer à un moment donné. J'ai une petite liste de problèmes que j'aime utiliser, en fonction du niveau de la position.


@ERIC: Merci Eric. Semble comme de grandes questions pour vraiment tester son processus de pensée.


@achinth Comme vous pouvez le constater dans les commentaires / réponses, de nombreux éléments sont impliqués pour résoudre le problème. Vous voulez vraiment poster une mise à jour à la question pour inclure des réponses aux commentaires @eric, et si cela se trouve dans le même processus que @jon mentionné.


J'ai mis à jour la question pour répondre à toutes les questions


Quel est le problème avec pré-générer les chiffres? (Comme suggéré dans ma réponse) Je ne comprends pas pourquoi ceci est un problème.


13 Réponses :


1
votes

EDIT: Cette réponse n'a pas de sens lorsque j'ai réalisé l'obligation d'avoir plusieurs codes uniques par jour, mais qu'ils peuvent répéter le lendemain. Si vous recherchez un seul code unique par jour (pour une raison quelconque), cette réponse est utile :)

Donc, si le code est juste requis pour être unique par jour, utilisez simplement la date comme code ...

Peut-être que YyyymMdd, qui vous donnerait (pour la date d'aujourd'hui) 20110505, et demain serait 20110506.


4 commentaires

@Alastairpitts C'est ce qu'il dit, mais je ne pense pas vraiment qu'il veut un code par da. Sinon, il ne penserait pas à deux méthodes accédant à la même seconde: /


@Alastairpitts Oui, c'est ce qu'il a dit;)


Le code ne doit pas répéter dans un jour de donner, il peut répéter le lendemain


@achinth: ahh ok. Je vois ce que tu veux dire maintenant. J'ai mal interprété ce que votre exigence était :)



1
votes

ne doit-il pas être unique dans le processus?

Une raison de ne pas conserver un compteur que vous incrémentez atomiquement à chaque fois, puis la réinitialisez-la si la date roule sur?


7 commentaires

Bonne idée, mais je voudrais du bruit dans les chiffres. Est-ce possible Jon?


@achinth: Il existe différentes manières que vous puissiez inclure le hasard - la plus simple à mettre en œuvre serait de rappeler toutes les valeurs que vous avez créées jusqu'à présent aujourd'hui, générez un nombre aléatoire et vérifiez si vous l'avez renvoyé ou non. Cela ne ferait pas bien échouer du tout (horriblement, en fait) mais cela fonctionnerait si vous n'avez pas besoin de générer de nombreux chiffres. Notez que l'utilisation du temps est loin d'être aléatoire ...


@achinth Je pense que vous devriez ajouter toutes les informations nécessaires à votre question. Si vous recherchez un moyen de générer des chiffres uniques, vous en avez un. Maintenant, si vous voulez des chiffres aléatoires ... vous auriez dû l'ajouter dans la question. Peut-être que vous pourriez nous dire ce que le scénario est ...


@jon La génération de numéro doit être rapide pour que je ne souhaite pas vérifier les chiffres existants si possible.


Une autre question de supposer dans le processus et de conserver une liste de chiffres déjà générés, est s'il s'agit d'une application ASP.NET qui devrait survivre à un recyclage.


@EGLASIUS: Oui, c'est vrai. Si les valeurs sont réellement stockées, vous pouvez rendre le processus de lecture «Valeurs d'aujourd'hui» au démarrage pour déterminer la valeur initiale à utiliser. Cela ne fonctionnerait pas bien dans un environnement plus distribué bien sûr.


convenu / BTW, la bowvote n'est pas à moi, je trouve une réponse raisonnable compte tenu du manque de spécifications dans la question



0
votes

Ajoute un identifiant de thread à la fin du code pour faire face à la concurrence.


3 commentaires

Supposons que vous appendez l'ID de thread à l'heure actuelle. Supposons maintenant que l'ID soit créé au début de l'heure lorsque l'heure d'épargne du jour "tombe". Une heure plus tard, le même thread est invité à produire un ID, et produit le même identifiant qu'avant, contrevenant à l'exigence qu'elle soit unique. Le problème ici est que les temps ne sont pas uniques. Ajout d'autres choses pour eux n'améliore pas la situation.


Regardons un autre problème avec votre solution. Supposons que vous ayez une pièce d'identité en deux parties. La première partie est garantie d'être unique sur un thread donné, la deuxième partie est l'ID de thread. Vous générez un identifiant. Alors ce fil se termine. Quelques heures passent. Un nouveau thread est créé et il arrive à obtenir le même identifiant. C'est un fil différent, il pourrait donc générer la même première partie que le fil antérieur, et les ID sont identiques, à nouveau, nous n'avons pas un caractère unique.


Le long et court est-il: ni le temps ni les poignées de fil sont en réalité des sources d'unicité à chaque jour. Vous ne pouvez pas faire de l'unicité de deux choses qui ne sont elles-mêmes pas uniques.



1
votes

Si tous les appels sont dans le même JVM, je pense que tout ce dont vous aurez besoin est de créer un statique pour contenir le dernier numéro attribué, écrivez une seule fonction pour incrémenter le numéro et renvoyer la nouvelle valeur, puis synchroniser sur ce. Comme: xxx

S'il existe plusieurs JVM, la chose la plus facile à faire serait de stocker le numéro sur une base de données et d'utiliser la base de données Verrouillage pour conserver les chiffres uniques.

Mise à jour

Je vois que vous avez ajouté une obligation au hasard. Si vous souhaitez que les chiffres soient aléatoires et uniques, je ne vois aucune alternative à la conservation de toutes les numéros précédemment attribuées. Vous pouvez les garder dans une sorte de table de hachage afin que vous n'ayez pas à rechercher la liste complète à chaque fois. Si vous attribuez beaucoup de ceux-ci, la taille de la table de hachage peut commencer à être un problème, même si vous n'avez pas besoin de la recherche de manière séquentielle.

Selon ce que vous essayez d'accomplir , vous pouvez proposer un schéma qui attribue des numéros non séquentiellement, mais dans une séquence rigide, de sorte que certains objectifs apparaissaient aléatoires. Par exemple, vous pouvez augmenter par un nombre très important en ce qui concerne le maximum et relativement ample avec le maximum, puis chaque fois que l'incrétement suivant passerait, soustrayez le maximum. Comme pour le réduire, supposons que vous attribuiez des numéros à 2 chiffres au lieu de 9 chiffres. Incrément de 37. Ensuite, vous cédez 37, 74, 111 enveloppements à 11, 48, 85, 122 enveloppements à 22, etc.


1 commentaires

@Oscar: Oups, ma bigotry Java Secret! Je voulais dire, bien sûr, le temps d'exécution .Net.



1
votes

Utilisez GUID.NewGuid () pour obtenir quelque chose comme:

0F8FAD5B-D9CB-469F-A165-70867728950E

Ensuite, éloignez-vous de «-, et convertissez les lettres à leurs homologues ASCII. (où a = 97)

puis convertir en un numéro.


3 commentaires

J'ai besoin que le nombre soit compris entre 6 et 9 chiffres et je ne veux pas vérifier l'unicité des nombres existants si possible.


C'est une mauvaise idée. Les GUID sont plus grands que 9 chiffres décimaux et les GUID ne sont garantis que d'être uniques lorsque vous regardez tous leurs bits. Tout sous-ensemble de bits donné dans un GUID n'est pas garanti d'être unique, plus que toute partie individuelle d'un avion est la partie qui vole.


Seuls les 6-9 premiers bits d'un GUID ne vont évidemment pas garantir l'unicité, donc la nécessité de vérifier contre les identifiants déjà alloués. OP veut éviter que si possible, donc il peut choisir parmi les autres réponses suggérées.



0
votes

Le générateur de code approprié dépend de la manière dont de nombreux nombres devraient être générés en période. Considérons les modèles suivants:

HHMMSS + NNN- vous donne de l'espace pour 999 numéros aléatoires dans une seconde.

hh + nnnnnnnn - vous donne de l'espace pour 9999999 Nombres aléatoires en une heure. C.

Si la méthode de génération de numéro de la génération de la distribution d'appel dans le temps est uniforme, tout modèle est presque égal.

Quoi qu'il en soit, compte tenu de la limitation de la limitation au nombre aléatoire. Il existe toujours une limite pour le nombre d'appels de méthode avant que les affrontements ne soient apparemment. Par exemple. Si la méthode est appelée> 1000 fois par seconde.


0 commentaires

1
votes

je voudrais

  1. génère un ensemble de nombres aléatoires uniques au début de chaque jour, ou plutôt, avant chaque jour de temps suffisant

  2. prenez séquentiellement un numéro de la pile chaque fois que l'on est nécessaire


0 commentaires

0
votes

J'ai poursuivi votre idée d'utiliser l'heure actuelle, je viens d'ajouter une synchronisation multi-threads et de stocker des randoms utilisés pour comparer tous les prochains randoms avec eux afin de fournir un caractère unique.

private static DateTime DateInArray = DateTime.Today;
private static ICollection<string> UsedTodayRandoms = new List<string>();

[MethodImpl(MethodImplOptions.Synchronized)]
public static string RandomUniqueToday()
{
    if (! DateTime.Today.Equals(DateInArray) ) {
        UsedTodayRandoms.Clear();
        DateInArray = DateTime.Today;
    }

    string result = null;
    DateTime timeToGenerateUnique = DateTime.Now;
    do
    {
        result = timeToGenerateUnique.ToString("HHmmssfff");
        timeToGenerateUnique = timeToGenerateUnique.AddMilliseconds(-1);
    } while (UsedTodayRandoms.Contains(result));
    UsedTodayRandoms.Add(result);

    return result;
}


1 commentaires

Je voudrais éviter de comparer une liste utilisée comme cela pourrait entraîner des problèmes de performance.



1
votes

vous ne peut pas Assurez-vous que les numéros aléatoires ne se répètent pas. (parce qu'ils sont aléatoires)

Sans comparaison avec des nombres déjà générés, vous pouvez avoir:

  • nombre aléatoire ou
  • Numéro unique.

    Vous avez besoin d'un numéro unique avec un aspect aléatoire. Si les millisecondes dès le début de la journée n'ont pas assez d'aspect aléatoire, essayez de le combiner avec un autre numéro unique .

    Par exemple:

    • Combinez le nombre de millisecondes et
    • Compteur atomique (qu'est l'incrément d'une fois que vous générez un numéro)

      Par exemple, lorsque vous les résumez, vous pouvez générer: 999999999-86400000 = 913599999 numéros uniques par jour.

      Bien qu'ils ne seront pas aléatoires, ils seront uniques - et prévisibles seulement à 00h00.

      Voici les variations pour cela, par exemple, ne pas réinitialiser le compteur à 00:00.


0 commentaires

0
votes

double getRandomNumber () {Opération d'objet = nouvel objet (); verrouillage (opération) {retourner nouveau aléatoire (). Nextdouble (); }} ferait.

Cela ne dépend pas du jour / heure d'où il est encore plus aléatoire que votre exigence. Maintenant, le fait que le nombre soit inférieur à 1, je vous laisserai comme un exercice ...

En outre, si vous souhaitez garder une trace de tout numéro généré pendant une journée donnée - gardez une liste d'entre eux et régénérer si duplicata est généré. Mais que je ne vais pas écrire pour vous comme vous êtes le programmeur de votre situation ...


1 commentaires

Votre solution comporte deux problèmes. Premièrement, une nouvelle classe aléatoire () qui n'a pas été ensemencée avec un nombre utilisera le temps du système actuel pour une valeur de semences. Cela signifie que deux créés dans environ 15 millisecondes (la résolution de l'horloge du système Windows) de l'autre produiront probablement les mêmes valeurs. Le verrouillage n'empêchera pas cela. Deuxièmement, étant donné que l'objet que vous verrouillez a été créé dans votre méthode, il ne bloquera jamais quoi que ce soit car d'autres threads auront créé leurs propres nouveaux objets à verrouiller.



0
votes

Selon la quantité de randonneur requise, un Générateur confortable linéaire avec les paramètres appropriés peut Soyez ce que vous recherchez. Par exemple, à la suite des lignes directrices données sur l'entrée Wikipedia sur la longueur de la période, un ensemble de paramètres pouvant fonctionner pour vous est: M = 1000000000, A = 21, C = 3, utilisez ensuite toute graine initiale x 0 IN [0..9999999999] et calculez X N + 1 = (A * X N + C)% m. Cela génère une séquence de x n avec la période M, c'est-à-dire que la séquence génère tous les nombres dans [0..999999999] exactement une fois avant de commencer à répéter.


0 commentaires

4
votes

Si vous commencez à partir d'un nombre aléatoire avec 6 chiffres, continuez d'ajouter au hasard, mais de petits numéros suffisants, vous risquez de le faire. Vous pouvez utiliser le système de fichiers comme stockage de verrouillage si vous voulez ... Mais je pense que vous devriez utiliser un dB pour la production!

Voici l'échantillon de ce dont je parle: strong> p >

Cet exemple est une application de console, qui utilise un fichier pour contrôler la concurrence, et pour stocker le dernier numéro et la date d'utilisation et la date à laquelle il a été généré. P>

Si vous l'exécutez plusieurs fois, vous voyez ce qui se passe . Les deux auront leurs propres numéros uniques. P>

It ne stockera pas tous les numéros générés em> str forts>, comme vous avez besoin! P>

Cet échantillon Peut générer environ 999 000 numéros aléatoires par jour, dans la gamme de 6 et 9 chiffres inclus. C'est environ 11 nombres par seconde. P>

using System;
using System.IO;
namespace _5893408
{
    class Program
    {
        static void Main(string[] args)
        {
            Random rand = new Random();
            var futureTime = DateTime.Now.AddSeconds(60);
            while (DateTime.Now < futureTime)
                Console.WriteLine(GetNextNumber(rand));
        }

        public static int GetNextNumber(Random rand)
        {
            var now = DateTime.Now;
            string filePath = @"C:\num.txt";
            FileStream fileStream = null;
            while (fileStream == null)
            {
                try { fileStream = File.Open(filePath, FileMode.OpenOrCreate, FileAccess.ReadWrite, FileShare.None); }
                catch { }
            }
            using (fileStream)
            {
                DateTime date;
                int prevNum;
                if (fileStream.Length == 0)
                {
                    date = now;
                    prevNum = rand.Next(100000, 999999);
                }
                else
                {
                    var reader = new StreamReader(fileStream);
                    {
                        date = DateTime.Parse(reader.ReadLine());
                        prevNum = int.Parse(reader.ReadLine());
                    }
                    if (date.DayOfYear != now.DayOfYear)
                        prevNum = rand.Next(100000, 999999);
                }
                int nextNum = prevNum + rand.Next(10, 1000);
                fileStream.Seek(0, SeekOrigin.Begin);
                using (var writer = new StreamWriter(fileStream))
                {
                    writer.WriteLine(now);
                    writer.WriteLine(nextNum);
                }
                return nextNum;
            }
        }
    }
}


2 commentaires

En cas de cartographie de rappel sécurisé, cela ne le rendrait pas un peu prévisible.


@Yetanotheruser: Oui ... un peu! Mais il peut être possible de le rendre moins prévisible en utilisant une sorte de mathématiques entier ... comme les mathématiques utilisées dans la cryptographie, faisant de grosses sommes de grande taille, puis module.



1
votes

Que diriez-vous d'une version modifiée de Sac shuffle . Voici comment cela fonctionnerait -

  1. Avant votre début de journée, vous mettez n de numéros distincts satisfaisant votre critère dans un sac de diffusion
  2. Au cours de la journée, vous demandez un numéro du sac de shuffle.
  3. Sac Shuffle vous donne un nombre aléatoire dans le sac et le rejeter - c'est-à-dire de retourner le même numéro.
  4. à la fin de la journée, il effacerait le sac, prêt pour le lendemain.

    Avantages

    • assure le nombre n'est pas réutilisé, sans vérifier avec la liste existante
    • numéros serait aléatoire, sans une séquence
    • Appliquez des règles simples en matière de santé mentale pour initialiser le sac shuffle, par ex. Pas de séquences communes / répétitives autorisées (1111111 ou 123456789)
    • Simple à initialiser Sac Shuffle - Utilisez des numéros séquentiels aléatoires. I.e. Démarrez à partir de six chiffres, continuez à ajouter un petit nombre aléatoire pour initialiser le sac.
    • facile à modifier la taille du sac en fonction de l'utilisation historique.
    • Emploi très simple de fil en toute sécurité en C #.

      La source d'origine est ici - la version modifiée pourrait servir votre objectif.


0 commentaires