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

23

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.

geai
la source
31
Garanti au sens strict du terme? Je veux dire, même Guids commencera à un moment donné à se répéter. Nous ne vivons peut-être plus, mais c'est garanti. Et au fait, un ID de processus est loin d'être unique .
JensG
7
@CodesInChaos - C'est une hypothèse assez terrible, étant donné qu'il est trivial dans certains systèmes d'exploitation de changer votre adresse mac.
Telastyn
7
"Supposons que cette fonction sera accessible simultanément par plusieurs machines" - honnêtement, cela pourrait signifier "le code s'exécute sur chaque machine individuellement, sans communication entre les machines", ou "il y a une machine centrale / base de données centrale où la fonction est fourni pour les autres machines, disponibles sur le réseau ". Vous devriez commencer par clarifier cela en premier.
Doc Brown
28
C'était une question piège? Par exemple, une fonction contenant une boucle infinie ne retournera jamais deux fois la même valeur.
Brendan
8
Peut-être recherchaient-ils un programmeur qui pose des questions sur les exigences douteuses, plutôt que de faire des hypothèses et de fonctionner avec lui :)
theMayer

Réponses:

60

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?

Telastyn
la source
7
C'est une bonne réponse, car l'intervieweur ne pose jamais de questions pour obtenir une réponse claire. Ils veulent que vous donniez une réponse où vous pouvez justifier vos décisions. Si vous comprenez le domaine, presque toutes les réponses conviendront si vous pouvez le justifier.
7
Comment est-ce censé fonctionner si le code s'exécute sur différentes machines (donc évidemment dans des processus différents)? Chaque processus aura une copie différente de x. Et je pense que sans une explication sur le type de mécanisme de verrouillage que vous avez en tête, cette réponse est assez vague.
Doc Brown
7
@DocBrown "auquel plusieurs machines accèdent simultanément" semble impliquer que plusieurs machines accèdent à une seule fonction sur un seul serveur. Sinon, il devrait être libellé "Plusieurs machines exécuteront une copie de cette fonction en même temps"
Falco
3
@LightnessRacesinOrbit: Je suppose que c'est censé être C #, et la System.Threading.Interlockedclasse, qui fournit des incréments atomiques. Mais vous pouvez également lire ceci comme une sorte de pseudo-code.
Doc Brown
3
Si j'étais la personne qui demandait, je serais très mécontent de cette proposition. Commencer à mettre en œuvre quelque chose sans même savoir quelles sont les exigences est un gros drapeau rouge. Je m'attendrais à ce que vous demandiez.
JensG
25

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.

Mason Wheeler
la source
Le problème avec les GUID v4 est qu'ils sont très probablement uniques, non garantis uniques. Pas un gros problème dans la pratique, mais ne répond pas aux exigences si l'intervieweur les prend à la lettre.
CodesInChaos
En particulier, si le mécanisme GUID standard ne répond pas aux exigences de l'intervieweur, alors expliquez les différences d'exigences entre l'intervieweur et un utilisateur ordinaire de GUID. Un intervieweur sensé posant ce genre de question ("comment faites-vous <une chose standard connue peut-être avec une légère variation par rapport aux exigences habituelles>") devrait s'attendre à des types de réponses très différents de la part des candidats qui connaissent l'état de l'art pour les GUID et les candidats qui inventent quelque chose à partir de zéro.
Steve Jessop
C'est probablement la réponse la plus simple, en supposant des exigences flexibles.
theMayer
9
+1 parce que c'est essentiellement le problème que les guides résolvent. Produire un Guid en double, quel que soit son format, est la loterie la plus difficile de la planète. Apparemment, beaucoup de gens n'ont pas de sens pour la ressemblance exponentielle des collisions.
usr
3
Oh, et si vous offrez la réponse «utiliser une fonction standard» à une telle question, attendez-vous à une question de suivi «et comment la fonction standard est-elle mise en œuvre?». À quoi vous pourriez très bien répondre "Je ne sais pas, mais je chercherais certainement plutôt que d'essayer d'inventer quelque chose", qui est une réponse tout à fait exacte qui ne parvient pas à maintenir la suspension attendue de l'incrédulité dans les conditions de l'entretien, que vous auriez jamais faire quoi que ce soit d' important sans la recherche d'abord ;-)
Steve Jessop
22

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.

Brian
la source
12
Ou renvoyez simplement l'heure UTC quel que soit le fuseau horaire du demandeur. Comme l'UTC n'est pas localisé, il ne sera pas affecté par les changements d'heure d'été.
Mauro
1
System.currentTimeNanos () :-)
Falco
1
À moins que vous ne retourniez la date et l'heure dans un format lisible par l'homme, votre valeur ne devrait en aucun cas contenir d'informations de fuseau horaire.
Courses de légèreté avec Monica
12
La plus petite quantité de temps va encore produire des collisions si elle est appelée assez fréquemment / simultanément. Il produira également des collisions en raison de la dérive de synchronisation de l'horloge, de la manipulation malveillante de l'horloge et, si vous n'y faites pas attention, de l'heure d'été.
Telastyn
1
Très créatif, au moins. S'appuyer sur une horloge qui va être ajustée de temps en temps n'est toujours pas une si bonne idée, à mon humble avis. Le décalage ne vous sauvera pas des collisions.
JensG
15

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.
rwong
la source
Je pense que c'est la meilleure réponse. Les autres sont des solutions sans exigences.
Jack Aidley
À propos de votre troisième question - il semble que la compétence soit une hypothèse sûre, ou du moins non pertinente. Si une entreprise n'a pas fourni d'intervieweur compétent, le processus de sélection entraînera probablement des défauts plus importants. S'ils l'ont fait, alors il / elle appréciera les questions.
theMayer
1
Pourquoi la «question 3» ne pourrait-elle pas être abordée en posant quelque chose du genre: «Avons-nous besoin d'unicité vraiment garantie ou simplement d'une très, très faible probabilité de collisions? »et« Dans quelle mesure cela doit-il être sécurisé? Devons-nous supposer qu'un attaquant tentera de briser le mécanisme? De quels types d'attaques sommes-nous préoccupés? Les réponses à ces questions devraient préciser si le demandeur comprend ces problèmes et ce qu'il attend.
jpmc26
12

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.

theMayer
la source
5

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.

ChaosPandion
la source
Je pense que l'hypothèse selon laquelle le code ne sera utilisé que pendant moins de cinq cents ans est une hypothèse valide. Si vous renvoyez simplement des valeurs croissantes dans le stockage 64 bits, tout va bien pendant un bon moment. À 1 appel par personne, dans 584555 ans.
Mooing Duck
1
Au moins en Java, c'est 2 ^ 63 valeurs (donc la moitié de cette longueur). Encore plus longtemps que la race humaine existera probablement étant donné notre tendance à s'entre-tuer. Quoi qu'il en soit, j'ai adopté une approche plus théorique. En réalité, 64 (ou 63) bits devraient suffire.
1
@Snowman: QUOI?!? Votre solution n'est valable que pendant 250 000 ans?!?!? PROCHAIN ​​CANDIDAT !!!!!! :-)
Bob Jarvis - Réintègre Monica
0

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.

thespratty
la source
-1
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.

techExplorer
la source
Les programmeurs concernent les questions conceptuelles et les réponses sont censées expliquer les choses. Lancer des vidages de code au lieu d'explications, c'est comme copier du code de l'IDE vers le tableau blanc: cela peut sembler familier et parfois même compréhensible, mais cela semble bizarre ... juste bizarre. Le tableau blanc n'a pas de compilateur
GNAT
Merci moucher pour l'avoir signalé, prendra soin d'expliquer la solution de la prochaine fois
techExplorer