Fonction garantie de ne jamais retourner deux fois la même valeur [fermé]

C'est une question qui m'a été posée lors d'un entretien d'embauche, et je ne peux pas trouver la réponse qu'ils recherchaient, alors j'espère que quelqu'un ici pourrait avoir des idées. Le but est d'écrire une fonction qui est garantie de ne jamais retourner deux fois la même valeur. Supposons que cette fonction sera accessible simultanément par plusieurs machines.

Mon idée était d'attribuer à chaque machine un identifiant unique et de transmettre cette valeur à la fonction de générateur de valeur unique:

var i = 0;
function uniq(process_id, machine_id) {
   return (i += 1).toString() + machine_id + "-" + process_id;
}

Cela éviterait les retombées des conditions de concurrence, car même si deux ou plusieurs processus lisent la même valeur i, chaque valeur de retour est étiquetée comme une combinaison unique d'ID de processus et d'ID d'ordinateur. Cependant, mon interlocuteur n'a pas aimé cette réponse car mettre une autre machine en ligne implique de lui attribuer un identifiant.

Alors, quelqu'un peut-il penser à une autre façon de résoudre ce problème qui n'implique pas de configurer chaque machine pour avoir un identifiant unique? J'aimerais avoir une réponse au cas où cette question reviendrait. Merci.

Ne soyez pas fantaisiste, lancez simplement un compteur simple (threadsafe) derrière un point de terminaison de communication (WCF, service Web, peu importe):

   long x = long.MinValue;
   public long ID(){
       return Interlocked.Increment(ref x);
   }

Oui, il finira par déborder. Oui, il ne gère pas les redémarrages. Oui, ce n'est pas aléatoire. Oui, quelqu'un pourrait exécuter cela sur plusieurs serveurs.

C'est la chose la plus simple qui satisfait aux exigences pratiques. Ensuite, laissez- les être ceux qui font le suivi de ces problèmes (pour vous assurer qu'ils comprennent les limites, pensent -ils vraiment que vous avez besoin de plus de 2 ^ 64 identifiants), afin que vous puissiez ensuite demander quels compromis sont corrects. Doit-il survivre aux redémarrages? Qu'en est-il de la défaillance du disque dur? Et la guerre nucléaire? Doit-il être aléatoire? Comment aléatoire?

Si on me posait cette question, et ils ont clairement indiqué qu'elle doit être unique entre les redémarrages et les différentes machines, je leur donnerais une fonction qui appelle le mécanisme standard de création d'un nouveau GUID, quoi qu'il arrive dans la langue utilisée.

L'intervieweur a déclaré que la méthode sera appelée simultanément, pas en parallèle; il suffit de ramener la date / l'heure à autant de décimales que possible.

Pourquoi est-ce que tout le monde y réfléchit trop? Vous serez mort longtemps avant que toute finitude ne soit dépensée et vous n'avez aucune chance de collision.

Si vous craignez qu'il ne revienne en même temps, ajoutez un délai pour la durée minimale mesurable.

Si vous vous inquiétez de remettre une horloge à l'heure d'été (une fois deux fois), ajoutez une constante à l'heure de la deuxième fois.

Tout d'abord, vous voudrez poser deux questions à l'intervieweur.

Question 1.

si l'intervieweur s'attend à ce qu'une ou plusieurs "machines centrales" soient utilisées pour attribuer des numéros uniques ou des blocs de numéros uniques.

Question 2.

Que l'intervieweur s'attende à un mécanisme de détection des collisions ou accepte plutôt le risque calculé d'une minuscule chance de collision sans les détecter explicitement.

Il y a aussi l'approche de défense en profondeur, dans laquelle on incorpore une partie de l'ID utilisateur dans le caractère aléatoire (donc pas entièrement aléatoire). La probabilité qu'un même utilisateur rencontre une collision au sein du contenu créé par ce même utilisateur est donc réduite.

Il y a une question implicite 3, ...

Mais c'est celui que vous devrez vous mesurer sans demander, car il est extrêmement impoli de demander à votre intervieweur.

Si l'intervieweur suppose la connaissance des probabilités, des risques et de quelques techniques simples employées dans les systèmes cryptographiques et de sécurité de l'information.

Le premier type de connaissances garantit que vous n'essayez pas de convaincre une personne non scientifique d'accepter un concept scientifique qu'elle n'acceptera pas.

Le deuxième type de connaissances garantit que vous répondez à des préoccupations qui s'ajoutent à la simple probabilité. En d'autres termes, comment se défendre contre les "assaillants" qui veulent briser intentionnellement votre schéma de randomisation, en manipulant la ou les machines ou leurs hôtes virtuels pour forcer deux machines à générer la même valeur.

Pourquoi demander.

La raison en est que si l'intervieweur l'attend d'une manière ou d'une autre, essayer de répondre avec l'approche opposée ne le rendra jamais heureux.

La raison la plus profonde est que certaines personnes n'aiment pas l'idée de dire, une 1.0e-20chance d'échouer. (J'essaierai de ne pas susciter ici d'arguments philosophiques ou religieux.)

Tout d'abord, "l'espace de noms" des nombres aléatoires est transformé en une hiérarchie, avec un certain nombre de bits alloués à une source de randomisation, et l'autre nombre de bits alloués à d'autres manières, etc.

L'approche centralisée s'appuie sur une autorité centrale pour attribuer de manière unique le premier niveau de bits. Ensuite, les autres machines peuvent remplir le reste des bits.

Il existe plusieurs approches décentralisées:

• Il suffit de générer des nombres aléatoires aussi bons que possible et d'accepter la chance pratiquement nulle d'échouer justifiée par des calculs.
• Utilisez des moyens cryptographiques pour générer des valeurs aléatoires à partir d'une source déterministe, disons, une incrémentation de valeurs.

Donc, en gardant à l'esprit qu'il s'agit d'une question d'entrevue et non d'un scénario réel, je pense que la bonne approche (et probablement ce que l'intervieweur recherche) est de poser une question de clarification ou d'écrire "Cela ne peut pas être fait "et passer à autre chose. Voici pourquoi.

Ce que l'intervieweur demande:

Écrivez une fonction qui est garantie de ne jamais retourner deux fois la même valeur. Supposons que cette fonction sera accessible simultanément par plusieurs machines.

Ce dont l'enquêteur a besoin:

Ce candidat évalue-t-il efficacement les exigences et cherche-t-il des commentaires supplémentaires au besoin?

N'assume jamais.

Lorsqu'un ingénieur reçoit une exigence (via un EDT ou un cahier des charges ou un autre document d'exigences), certains vont de soi et d'autres sont totalement flous. Ceci est un parfait exemple de ce dernier. Comme l'ont montré les réponses précédentes, il n'y a aucun moyen de répondre à cette exigence sans faire plusieurs hypothèses majeures soit (a) quant à la nature de la question ou (b) quant à la nature du système, parce que l'exigence ne peut être satisfaite tel qu'écrit (c'est impossible).

La plupart des réponses tentent d'une manière ou d'une autre de résoudre le problème via une série d'hypothèses. On recommande spécifiquement de le faire rapidement et de laisser le client s'en soucier si c'est faux.

C'est vraiment une mauvaise approche. En tant que client, si je donne une exigence peu claire et que l'ingénieur part et me construit une solution qui ne fonctionne pas, je vais être contrarié qu'ils soient allés travailler et ont dépensé mon argent sans prendre la peine de me demander d'abord. Ce type de prise de décision cavalière démontre un manque de travail d'équipe, une incapacité à penser de manière critique et un mauvais jugement. Cela peut entraîner toute sorte de conséquences négatives, y compris la perte de vie dans un système critique pour la sécurité.

Pourquoi poser la question?

Le point si cet exercice est qu'il est coûteux et long de construire selon des exigences ambiguës. Dans le cas du PO, on vous a confié une tâche impossible. Votre première action devrait être de demander des clarifications - qu'est-ce qui est requis? Quel degré d'unicité est nécessaire? Que se passe-t-il si une valeur n'est pas unique? La réponse à ces questions pourrait être la différence entre plusieurs semaines et quelques minutes. Dans le monde réel, l'un des principaux facteurs de coût des systèmes complexes (y compris de nombreux systèmes logiciels) réside dans les exigences peu claires et mal comprises. Cela conduit à des bogues coûteux et chronophages, à des restructurations, à la frustration des clients et des équipes et à une couverture médiatique embarrassante si le projet est suffisamment important.

Que se passe-t-il lorsque vous supposez?

Étant donné mes antécédents dans l'industrie aérospatiale et en raison de la nature très visible des défaillances aérospatiales, j'aime citer des exemples de ce domaine pour illustrer des points importants. Examinons une paire de missions échouées sur Mars - Mars Climate Orbiter et Mars Polar Lander. Les deux missions ont échoué en raison de problèmes logiciels - parce que les ingénieurs ont émis des hypothèses invalides en raison, en partie, d'exigences peu claires et mal communiquées.

Mars Climate Orbiter - ce cas est généralement cité comme ce qui se passe lorsque la NASA tente de convertir l'anglais en unités métriques. Cependant, c'est une représentation trop simpliste et médiocre de ce qui s'est réellement passé. Certes, il y avait un problème de conversion, mais il était dû à des exigences mal communiquées dans la phase de conception et à un schéma de vérification / validation incorrect. De plus, lorsque deux ingénieurs différents ont remarqué le problème parce qu'il était évident à partir des données de trajectoire de vol, ils n'ont pas soulevé le problème au niveau approprié car ils ont supposé qu'il s'agissait d'une erreur de transmission. Si l'équipe des opérations de la mission avait été informée du problème, il y aurait eu suffisamment de temps pour le corriger et sauver la mission. Dans ce cas, il y avait une condition logique impossible qui n'était pas reconnue pour ce qu'elle était, conduisant à l'échec de la mission coûteuse.

Mars Polar Lander- ce cas est un peu moins connu, mais peut-être plus embarrassant en raison de sa proximité temporelle avec la panne de Mars Climate Orbiter. Dans cette mission, le logiciel a contrôlé la descente assistée par un propulseur de la fusée dans la surface martienne. À un point situé à 40 mètres au-dessus de la surface, les jambes de l'atterrisseur se sont déployées en préparation de l'atterrissage. Il y avait également un capteur sur les jambes qui détectait le mouvement (pour signaler quand ils avaient eu un impact) pour dire au logiciel d'arrêter le moteur. La meilleure supposition de la NASA sur ce qui s'est passé (car il y a plusieurs défaillances possibles et des données incomplètes) est que des vibrations aléatoires dans les jambes en raison de leur déploiement simultanément et ont incorrectement déclenché le mécanisme d'arrêt à 40 m au-dessus de la surface, entraînant le crash et la destruction du 110 $ Vaisseau spatial M. Cette possibilité a été évoquée lors du développement, mais n'a jamais été abordé. En fin de compte, l'équipe du logiciel a fait des hypothèses invalides sur la façon dont ce code devait fonctionner (une de ces hypothèses est qu'un signal parasite serait trop éphémère pour être capté, malgré des tests montrant le contraire), et ces hypothèses n'ont jamais été remises en question avant le fait.

Considérations supplémentaires

Interviewer et évaluer des personnes est une entreprise délicate. Il y a plusieurs dimensions d'un candidat qu'un enquêteur voudra peut-être explorer, mais l'une des plus importantes est la capacité d'un individu à penser de manière critique. Pour diverses raisons, dont la moindre n'est pas que la pensée critique est mal définie, nous avons beaucoup de mal à évaluer les capacités de pensée critique.

En tant que professeur d'ingénierie, l'une de mes façons préférées d'évaluer la capacité d'un étudiant à penser de manière critique était de poser une question quelque peu ambiguë. Les élèves les plus pointus retiendraient la prémisse défectueuse de la question, la noteraient et répondraient à la prémisse ou refuseraient de répondre complètement. En règle générale, je pose une question similaire à la suivante:

Vous prenez un dessin de votre pile de travaux. Le dessin contient une variété de légendes différentes, mais le plus important pointe vers une surface horizontale et dit "parfaitement plat". La surface mesure 5 "de large par 16" de long et la pièce est en aluminium. Comment usinerez-vous la pièce pour créer cette fonction?

(Soit dit en passant, vous seriez choqué de voir à quelle fréquence une telle spécification médiocre apparaît sur le lieu de travail.)

Je m'attends à ce que les élèves reconnaissent qu'il n'est pas possible de créer une fonctionnalité parfaite et qu'ils l'indiqueront dans leur réponse. J'attribuerais généralement un point bonus s'ils disent qu'ils reviendront au concepteur et demanderont des éclaircissements avant de faire la pièce. Si un élève continue de me dire comment il va atteindre une planarité de 0,001 ou une autre valeur composée, je n'accorde aucun point. Cela m'aide à faire remarquer à mes élèves qu'ils doivent penser à une vue d'ensemble.

Bottom Line

Si j'interroge un ingénieur (ou une profession similaire), je recherche quelqu'un qui peut réfléchir de manière critique et remettre en question ce qui a été placé devant lui. Je veux quelqu'un qui pose la question "Est-ce que cela a du sens?" .

Il n'est pas logique de demander une pièce parfaitement plate, car la perfection n'existe pas. Il n'est pas logique de demander une fonction qui ne renvoie jamais une valeur en double, car il est impossible de faire une telle garantie. Dans la programmation, nous entendons souvent l'expression «ordures entrantes, ordures sortantes». Si l'on vous remet des ordures pour les exigences, il est de votre responsabilité éthique de vous arrêter et de poser toute question qui vous aidera à obtenir la véritable intention. Si j'interroge un candidat et que je lui donne une exigence peu claire, je vais m'attendre à des questions de clarification.

Il est difficile de garantir l'unicité car les ordinateurs n'ont pas de variables infiniment grandes. Aucune machine de Turing du monde réel ne le peut.

Selon moi, il y a deux problèmes ici, et les deux ont des solutions bien établies.

• Accès simultané. Plusieurs machines peuvent avoir besoin d'une valeur en même temps. Heureusement, les processeurs modernes ont une concurrence intégrée et certains langages offrent des fonctionnalités conviviales aux développeurs pour en tirer parti.
• Unicité. Bien que impossible de l' unicité de la garantie, nous pouvons avoir des variables arbitrairement grandes qui peuvent contenir des valeurs si grand qu'un système monde réel aurait un très moment difficile épuisant toutes les valeurs uniques

Voici ma solution en Java:

public class Foo {
  private static BigInteger value = BigInteger.ZERO;
  private static final Lock lock = new ReentrantLock();

  public static BigInteger nextValue() {
    try {
      lock.lock();
      value = value.add(BigInteger.ONE);
      return value;
    }
    finally {
      lock.unlock();
    }
  }
}

BigInteger est un type entier de taille arbitraire. Il peut croître pour contenir des valeurs assez grandes, même si elles ne sont pas infinies. Le verrou garantit la simultanéité, de sorte que la même valeur ne peut pas être renvoyée deux fois par deux demandes simultanées traitées par des threads distincts.

J'exposerais la fonction via un port sur le serveur; pour appeler la fonction, la machine demandeuse demande une connexion et en obtient une, tout en se voyant attribuer un code d'identification (numéro séquentiel pour plus de simplicité). Chaque fois qu'un message est envoyé au port demandant la valeur unique, la valeur est générée en concaténant le hachage MD5 de la date et de l'heure actuelles avec le hachage MD5 du code d'identification.

S'ils veulent une solution plus à l'épreuve des balles, ils devraient spécifier leurs besoins réels plutôt que d'être flous sur les choses.

string uniq(string machine_id) 
{
   static long u = long.MinValue;
   Interlocked.Increment(ref u);

   //Time stamp with millisecond precison
   string timestamp = DateTime.UtcNow.ToString("yyyy-MM-dd HH:mm:ss.fff",
                                            CultureInfo.InvariantCulture);

   return machine_id + "-" + timestamp + "-" + u;
}

De la manière ci-dessus, nous pouvons nous assurer que la valeur de retour est différente même s'il y a redémarrage ou même si elle est appelée simultanément à partir de différentes machines.