Bonjour,
J'aimerai proposer un service web ouvert où des utilisateurs pourraient créer une page avec un identifiant unique. Imaginons que je voudrais cet identifiant sur 3 caractères alphabétiques, j'aimerai générer des séquences aléatoires comme aie, tpc, dui… qui ne se suivent pas. Ces identifiants seront ensuite enregistrés dans une base de données.
Une solutions évidentes seraient de parcourir séquentiellement les caractères (aaa, aab, aac…) mais je ne souhaite pas que les id se suivent.
Une autre solution pourrait être de générer une suite aléatoire puis vérifier qu'elle n'existe pas dans la BDD, mais ça va être un désastre quand on arrivera à la fin des combinaisons disponibles.
Est ce qu'il y a une solution pour ce genre de problème? Du genre une fonction qui traduise 1 en eih, 2 en dme… sans collision possible.
edit: ou peut être générer toutes les chaînes possibles, faire un shuffle et les enregistrer dans une BDD? Je ne sais pas si ce serait efficient par exemple avec 205 chaines différentes.
# Non
Posté par beaulieu1 . Évalué à 2.
Pas avec 3 caractères alphabétiques. Mis à part générer séquentiellement ces identifiants.
D'où sors-tu le 205 ? Enfin, 263 entrées, c'est gérable en mémoire.
[^] # Re: Non
Posté par ted (site web personnel) . Évalué à 3.
Les 3 caractères c'était juste pour l'explication, je pensais plutôt partir sur 5 en éliminant éventuellement les caractères pouvant être confondus (genre D et O). Désolé, sans explications on peut pas comprendre…
Je pense partir sur cette solution (générer les id à l'avance), je vais tester!
Un LUG en Lorraine : https://enunclic-cappel.fr
# Challenge intéressant
Posté par Nanawel (site web personnel, Mastodon) . Évalué à 1. Dernière modification le 02 avril 2020 à 07:26.
Je dirais que c'est possible. Sans trop réfléchir à l'implémentation exacte il faudrait une fonction bijective qui à chaque entier positif non nul (modulo 100000 si tu pars sur 5 chiffres) te donne un enchaînement de caractères ASCII unique.
En jouant sur les codes ASCII des caractères (des entiers donc) et en utilisant un vecteur d'initialisation configurable, ça doit permettre de générer toutes les séquences possibles, sans les précalculer à l'avance.
(je suis preneur des remarques sur cette idée de solution)
[^] # Re: Challenge intéressant
Posté par chimrod (site web personnel) . Évalué à 5. Dernière modification le 02 avril 2020 à 08:22.
Ça n'est pas un problème nouveau !
Tiens, voilà un article qui était resté dans mes favoris depuis quelques années (basé sur le principe du résidu quadratique) : how to generate a sequence of unique random integer
(à noter que les commentaires fournissent aussi beaucoup d'autres pistes)
[^] # Re: Challenge intéressant
Posté par Nanawel (site web personnel, Mastodon) . Évalué à 1.
Ah super, merci pour la source !
Oui je me doutais bien que ce n'était pas nouveau, mais je n'ai pas cherché…
[^] # Re: Challenge intéressant
Posté par gUI (Mastodon) . Évalué à 2.
Je me suis permis de corriger le lien invalide.
En théorie, la théorie et la pratique c'est pareil. En pratique c'est pas vrai.
[^] # Re: Challenge intéressant
Posté par chimrod (site web personnel) . Évalué à 2. Dernière modification le 02 avril 2020 à 08:34.
Ah ? Merci, je pensais avoir testé avant d'envoyer le message, mais je me souviens avoir reformulé le message au dernier moment…
[^] # Re: Challenge intéressant
Posté par ted (site web personnel) . Évalué à 2.
Merci pour cette solution, je vais étudier ça!
J'ai commencé à tester ma solution, la génération des séquences est assez rapide, le mélange aussi, mais l'enregistrement dans la base trop lente… J'ai dû stopper, peut être qu'il y a moyen d'optimiser aussi…
Un LUG en Lorraine : https://enunclic-cappel.fr
# Ça se tente sans rien faire
Posté par gUI (Mastodon) . Évalué à 2.
Là tu pars du principe que pour chercher si ta chaîne existe tu fais un "for i = 1 to nb". Dans ton cas il doit y avoir bcp plus malin à faire puisque ton ID est un hashage à lui tout seul. Je suis pas expert en BDD mais si cet ID unique est vraiment l'ID de tes enregistrements, laisse faire ton SGBD, il te dira de manière très efficace si l'ID existe déjà et tu auras tout loisir d'en recréer un.
Mais dans tous les cas, c'est à toi de surdimensionner cet ID pour que la collision soit peu probable (si tu vises 1 million d'enregistrements, chercher un ID avec 1 milliard de possibilités) comme ça tu passeras pas des heures à chercher le dernier ID disponible.
En théorie, la théorie et la pratique c'est pareil. En pratique c'est pas vrai.
[^] # Re: Ça se tente sans rien faire
Posté par ted (site web personnel) . Évalué à 2.
Eh bien justement, le problème n'est pas de vérifier si l'id existe mais que si il existe j'en recalcule un autre, je re-teste… Si il y a 1 million de possibilités et qu'il reste 1000 id de dispo il faudrait en moyenne 1000 tentatives avant de tomber sur un id.
Mon but est d'avoir une chaîne courte c'est pourquoi je veux utiliser toutes les possibilités, sinon effectivement je pourrai générer un id sur 30 caractères et là c'est facile :)
Un LUG en Lorraine : https://enunclic-cappel.fr
[^] # Re: Ça se tente sans rien faire
Posté par gUI (Mastodon) . Évalué à 2. Dernière modification le 02 avril 2020 à 14:01.
C'est pour ça que je te dis que cette situation ne doit pas arriver. Il te faut surdimensionner le nombre d'ID. Parce que de toutes façons si tu as 1 million de possibilité et qu'il ne t'en reste plus que 1000, dans pas longtemps tu vas être bien emmerdé.
Le milliard de possibilités est atteint avec 7 caractères (sur 20 positions seulement si j'ai bien compris). C'est trop gros ?
En théorie, la théorie et la pratique c'est pareil. En pratique c'est pas vrai.
# UUID
Posté par eggus . Évalué à 3.
En général lorsque je dois générer des identifiants uniques alphanumériques, j'utilise des UUID. Les bibliothèques existent déjà pour tous les langages courants.
Alors c'est sur c'est moins mémorisable qu'un id de 5 caractères (je ne sais pas si c'est important dans ton cas) mais le risque de collision est faible et super simple à mettre en place.
# Hash
Posté par jemore . Évalué à 1.
Ce que tu veux faire ressemble à un hash, mais le MD5 ou SHA1 ne va pas te convenir car tu veux avoir quelque chose de court. Tu peux te baser sur un calcul de Checksum, genre CRC32.
Avec le code suivant, je génère plus de 8 millions de code différents, sans collisions (on doit pouvoir en générer plus, mais la memoire explose sur ma machine).
Le principe est de calculer un CRC32 d'une chaine (comprenant un salt), et de transformer ce CRC en chaine de caractère avec ton alphabet.
Tu trouvera l'implementation ici, qui contient un test pour vérifier les collisions.
https://pastebin.com/qUuHfKza
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.