Vérification de l'égalité des entiers :O(1) en C mais O(log n) en Python 3 ?

https://cs.stackexchange.com/questions/127939

29-09-2020
|

Question

Considérez ces fonctions équivalentes en C et Python 3.La plupart des développeurs affirmeraient immédiatement que les deux sont $O(1)$.

def is_equal(a: int, b: int) -> bool:
  return a == b

int is_equal(int a, int b) {
  return a == b;
}

Mais considérez ce qui se passe sous la surface.Les entiers ne sont que des chaînes binaires et, pour déterminer l’égalité, les deux langages compareront les chaînes bit par bit.Dans les deux cas, cette analyse est $O(b)$ où $b$ est le nombre de bits.Puisque les entiers ont une taille constante en bits en C, c'est simplement $O(1)$.

MODIFIER:C ne compare pas petit à petit voir cette réponse

En Python 3 cependant, les entiers font pas ont une taille fixe et le scan reste $O(b)$ pour le nombre de bits dans l'entrée, ou $O(\log a)$ où $un$ est la valeur de l'entrée en base 10.

Ainsi, si vous analysez du code en Python, chaque fois que vous comparez deux entiers, vous vous lancez dans un voyage étonnamment complexe de $O(\log n)$ par rapport à la valeur en base 10 de l’un ou l’autre nombre.

Pour moi, cela soulève plusieurs questions :

Est-ce correct?Je n'ai vu personne d'autre affirmer que Python compare les entiers en temps de journalisation.
Dans le cadre d'un entretien, devriez-vous remarquer ou vous inquiéter si un candidat appelle cela $O(1)$?
Devriez-vous remarquer ou vous soucier de cette distinction dans le monde réel ?

MODIFIER:Il est facilement vérifié (et intuitif) que Python ne peut pas comparer des entiers arbitrairement grands en temps constant.Une meilleure façon de poser la question 1 ci-dessus pourrait être : « Quelle est la justification (le cas échéant) de l'appel de cette opération ? $O(1)$?Parce que c'est pragmatique ?Conventionnel?Implicite par le modèle RAM ?

La solution 7

TL; DR: Il existe une convention CS de décrire ce type d'opération comme $ O (1) $ qui se décompose dans des cas extrêmes pour Python. Ces cas sont extrêmement rares, afin de rompre avec la convention de $ O (1) $ a une utilité négative. Ce type de pragmatisme est normal dans Big $ o $ .

Il y a beaucoup de très bonnes réponses à cette question et je vous encourage à les lire. Mais je ne pense pas que personne d'entre eux réponde pleinement mes questions. Alors voici une synthèse.

est-ce correct? Je n'ai pas vu quelqu'un d'autre affirmer que Python compare les INT dans le temps de journalisation.

Ceci est étonnamment nuancé. Il est vrai que Python compare de très grandes intens dans $ o (\ journal n) $ runtime. Mais est-ce corriger pour décrire cette opération comme $ o (\ log n) $ ?

En fin de compte, je suis le plus persuadé par cette prise de @tomvanderzanden:

Si vous avez dit que la version C ou Python était $ o (1) $ tout intervieweur devrait être parfaitement heureux. Si vous l'avez dit (la version Python) était $ o (\ journal n) $ ils seraient probablement toujours heureux, mais pensez que vous êtes une personne plutôt pédant qui ne fait pas " t Suivre les conventions normales.

et

Si j'étais un intervieweur, je me soucierais de savoir si vous connaissez les limitations du monde réel de ce que vous faites et que vous savez ce que la théorie concerne la matière quand et que vous les apportez si et seulement le cas échéant.

Cependant, je n'accepte pas cela comme la réponse, car je pense que le premier paragraphe est actuellement trompeur (heureux de changer).

En fin de compte, cet argument est pragmatique. Par la définition stricte de Big $ o $ o $ Python int comparaison est toujours vérifiable $ o (\ journal n) $ . Mais il n'est pas utile de le traiter de cette façon, de sorte que vous ne devriez pas. J'ajouterais que pour être strict à propos de Big $ o $ est de rater le point de Big $ o $ analyse.

Autres conseils

Les entiers ne sont que des chaînes binaires et, pour déterminer l’égalité, les deux langages compareront les chaînes bit par bit.

Pas assez.C intles s sont de la taille d'un mot machine et comparés à une seule instruction machine ;Python intles s sont représentés en base $2^{30}$ (voir par ex. https://rushter.com/blog/python-integer-implementation/) et comparé chiffre par chiffre dans cette base.La base pertinente du logarithme est donc $2^{30}$.

Si au moins un des nombres peuvent être délimités par 2 $^{30d}$ pour n'importe lequel fixé $d$, la comparaison est $O(1)$ (car le nombre de chiffres est comparé en premier), et s'ils ne le peuvent pas, d'autres opérations sont probablement beaucoup plus préoccupantes que la comparaison d'égalité.Donc, en pratique, je dirais que cela a très peu d'importance et si c'est le cas, vous le saurez (et n'utiliserez pas ints mais quelque chose comme le Bibliothèque arithmétique à précisions multiples GNU en C également).

La complexité est définie par rapport à un modèle de calcul.P et NP, par exemple, sont définis en termes de machines de Turing.

Pour la comparaison, considérez le modèle Word RAM.Dans ce modèle, la mémoire est divisée en mots, des mots peuvent être accessibles en temps constant, et la taille du problème peut être représentée à l'aide de $ o (1) $ mots.

Donc, par exemple, lors de l'analyse d'une opération de tri basée sur la comparaison, nous supposons que le nombre d'éléments $ n $ peut être stocké dans $ O (1) $ mots, donc il faut du temps constant pour lire ou écrire un numéro entre $ 1 $ et N $ N $ .

est-ce correct? Je n'ai pas vu quelqu'un d'autre affirmer que Python compare les INT dans le temps de journalisation.

Non (et un peu oui). Considérez la réclamation suivante qui provoquant la pensée (mais pas vraiment vraie): un ordinateur ne peut avoir qu'une quantité finie de mémoire (limitée par le nombre d'atomes dans l'univers), de sorte que la version Python est également $ O (1) $ .

Le problème est que nous essayons de faire une déclaration sur Asymptotics (concernant ce qui se passe à l'infini) sur une machine à états finie (un ordinateur). Lorsque nous analysons la complexité du code, nous ne analysons pas réellement le code lui-même comme il fonctionnerait sur un ordinateur, nous analysons un modèle idéalisé du code.

Supposons que je vous ai demandé d'analyser un algorithme de tri écrit dans C. Vous pourriez indiquer qu'il utilise des INTS pour indexer la matrice, de sorte qu'il ne pouvait donc trier que la taille de la taille jusqu'à 2 $ ^ {31} -1 $ . Pourtant, lorsque nous analysons un tel code, nous prétendons que cela puisse gérer des tableaux arbitrairement importants. Clairement, nous ne disons pas que c Integer Comparaison est $ O (1) $ car il ne peut gérer que des nombres 32 bits.

Dans le contexte de la conduite d'une interview, devriez-vous remarquer ou soin si un candidat appelle ceci O (1)?

généralement, pas. Supposons que je conduise une interview et vous demande d'écrire un programme informatique C ou Python qui compte le nombre d'employés qui figurent dans la base de données des employés.

Ce serait incroyablement pédants si je me suis plaint que votre programme C était incorrect car il ne pouvait que compter jusqu'à $ 2 ^ {31} -1 $ .

Nous supposons généralement que les chiffres sont suffisamment petits qu'ils peuvent s'adapter à un mot / entier. Nous supposons que l'addition (ou toute autre opération de numéro) peut être effectuée dans $ o (1) $ , car il serait très gênant de devoir écrire $ o (\ journal n) $ partout et il suffirait de tout rendre illisible même si $ \ journal n $ est si petit N'aime pas vraiment de toute façon.

Si vous avez dit que la version C ou Python était $ o (1) $ tout intervieweur devrait être parfaitement heureux. Si vous l'avez dit (la version Python) était $ o (\ journal n) $ ils seraient probablement toujours heureux, mais pensez que vous êtes une personne plutôt pédant qui ne fait pas " t Suivre les conventions normales.

Devriez-vous remarquer ou vous souciez de cette distinction dans le monde réel?

Oui! Cela commence à compter quand les chiffres deviennent si importants l'hypothèse qu'ils sont petites est violée. Disons que vous interviewez pour Google et ils vous ont demandé de calculer le nombre de requêtes de recherche effectuées par des utilisateurs de femmes au cours de la dernière année. L'intervieweur serait tout à fait justifié de se plaindre si vous avez écrit un programme C à l'aide d'INTS.

Vous pouvez passer à l'aide de LIPS et toujours être justifié de l'appeler $ O (1) $ , et de même, appelant la version Python $ o (1) $ est également justifié. La $ O (1) $ v.s.s. $ o (\ journal n) $ La chose ne commence que lorsque les chiffres deviennent très longs. Par exemple, si votre tâche consiste à écrire un programme qui calcule des chiffres de $ \ pi $ ou une tâche similaire. Si vous avez écrit un programme Python pour cette tâche et que vous n'avez pas mentionné les particularités de la complexité lorsqu'on la demande, l'intervieweur s'en soucierait.

Si j'étais un intervieweur, je me soucierais de savoir si vous connaissez les limitations du monde réel de ce que vous faites et que vous savez ce que la théorie concerne la matière quand et que vous les apportez si et seulement le cas échéant.

Quand devriez-vous vous en soucier?

Jusqu'à présent, j'ai été un peu vague sur "grand" et "petit" chiffres. Dans le modèle RAM couramment utilisé, vous êtes autorisé à supposer que les opérations entier peuvent être effectuées dans $ o (1) $ sur des chiffres qui ont au plus $ O (\ journal n) $ bits (où $ n $ est la longueur de l'entrée). La justification de cette hypothèse est que si nous avons une entrée de longueur $ n $ , les pointeurs / indices de notre langage de programmation doivent être suffisamment nécessaires pour pouvoir résoudre le problème espace d'entrée complet. Donc, dans le modèle de RAM, si l'entrée est un nombre binaire de N $ N $ (binaire), la complexité de la vérification de l'égalité est $ O (\ frac {n} {\ journal n}) $ car nous pouvons vérifier l'égalité d'un groupe de $ o (\ journal n) $ < / span> bits en une $ o (1) $ opération.

Même si cela peut paraître trivial, votre première phrase est incorrecte. Les fonctions ne sont pas équivalentes.Pour les rendre équivalents, la fonction C doit utiliser GMP (ou similaire) pour implémenter une arithmétique de précision arbitraire.Maintenant, la raison pour laquelle cette observation n'est pas triviale, c'est que la mesure dans laquelle il est raisonnable de dire que les deux sont équivalents est précisément la mesure dans laquelle il est raisonnable de dire que le code Python est à temps constant !Autrement dit, si nous ignorons que les entiers de Python sont des grands nombres, nous pouvons (et devrions) les traiter systématiquement comme une taille fixe.

De manière analogue, considérons la fonction C int is_equal(char a, char b) { return a == b; } et la fonction Python def is_equal(a: str, b: str) -> bool: return a == b.Il est plus évident maintenant que les fonctions ne sont pas équivalentes, mais la raison en est exactement la même que la raison pour laquelle les vôtres ne le sont pas.Nous nous attendons simplement à voir des chaînes massives en Python tout le temps, mais ne nous attendons pas vraiment à des entiers massifs même si, bien sûr, nous savons qu'ils sont possibles.Ainsi, la plupart du temps, nous ignorons le fait que les entiers de Python sont grands et nous analysons comme s'ils étaient de taille fixe.Dans les rares cas où nous nous soucions du timing des opérations bignum, vous pouvez utiliser les « vraies » complexités.Et bien sûr, utilisez également GMP dans votre code C.

Tout cela pour dire :même si vous ne vous en êtes pas rendu compte, vous connaissez déjà la réponse à votre version reformulée de votre question à la fin, et la réponse est "la même justification par laquelle vous avez décrit ces fonctions comme équivalentes".Python a la particularité de ne pas avoir de type entier de taille fixe (enfin, pas celui que les gens utilisent couramment :il est possible d'en écrire un bien sûr, et il y en a un dans numpy).Mais par souci de pragmatisme, nous ne voulons pas que cela nous empêche de faire l’analyse de complexité « habituelle » des algorithmes qui calculent des nombres entiers et d’obtenir les réponses « habituelles ».Il est rarement nécessaire de préciser que si nous lui transmettons quelques entiers de 10 Go presque égaux, la comparaison peut prendre un peu de temps.

Dans certains cas, vous pouvez formaliser cela (si vous en avez vraiment besoin) en disant que vous limitez votre analyse à de petits nombres entiers.Ensuite, vous pouvez considérer la complexité d'un algorithme en termes de taille d'un tableau d'entiers, en traitant toutes les opérations arithmétiques comme O(1).Si vous envisagez des algorithmes qui sont vraiment linéaires ou pires en termes de grandeur de l'entier, alors vous pouvez le formaliser en disant que vous allez ignorer le facteur log, puisque tout ce qui vous importe vraiment est de savoir si la complexité est plus proche de linéaire ou quadratique, car O(n log n) est aussi bon que linéaire pour vos besoins.Mais presque toujours, il n’est pas nécessaire de formaliser la complexité des algorithmes. en Python.Si vous en êtes au point de spécifier un langage de programmation, vous ne faites plus vraiment d'informatique abstraite ;-)

Dans le contexte de la réalisation d'une entrevue, si vous remarquez ou vous souciez-vous d'un candidat appelle cela $O(1)$?

Cela dépend de l'entretien, je suppose, mais en tant que professionnel du logiciel, travaillant principalement en Python depuis 10 ans, je ne demanderais pas cela lors d'un entretien.Si je posais une question qui contenait la complexité de la comparaison d'entiers (comme, je ne sais pas, "quelle est la complexité de cet algorithme de tri?"), alors j'accepterais une réponse qui ignorerait tout le problème.J'en accepterais également un qui y répondrait.Je pense que cela vaut la peine de comprendre la complexité du calcul dans le cadre de la programmation pratique, je ne considère tout simplement pas cela si important pour la programmation être très prudent lorsque vous déclarez formellement que vous parlez d'entiers de taille raisonnable.

Je ne poserais jamais non plus de question dans laquelle je souhaite que le candidat fournisse l'information selon laquelle les entiers Python sont de précision arbitraire, alors que cela n'est pas évidemment pertinent pour la question pour une raison liée aux données impliquées.Si la question implique que les chiffres impliqués peuvent dépasser 2⁶⁴ puis dans un entretien en C, je voudrais que le candidat remarque qu'il s'agit d'un problème auquel il doit faire face, et dans un entretien en Python, je voudrais que le candidat sache que ce n'est pas le cas, mais je ne m'attendrais pas à lui faire tout leur possible pour le dire.Lors d'un entretien, on n'a pas le temps d'exposer chaque petit fait qui fait que quelque chose ne pose pas de problème.

Si je voulais vérifier la compréhension de la complexité lors d'un entretien, je commencerais probablement par demander du code pour un problème où il existe une solution "naïve" très simple avec une complexité médiocre, et au moins une solution moins simple avec une complexité décente. en utilisant des techniques bien connues.Si le candidat propose la solution naïve, vous pouvez alors demander quelle est la complexité et comment il modifierait le code pour l'améliorer.Si le candidat propose une meilleure solution, vous pouvez décrire la solution naïve, souligner le nombre de lignes de code et demander ce qui ne va pas (peut-être en demandant : « si vous révisiez le code de quelqu'un et qu'il vous a donné ceci, qu'est-ce que en diriez-vous"?).Pour des raisons plus pratiques, tout ce qui vous importe est de savoir s'ils peuvent faire la différence entre linéaire, quadratique et pire que quadratique.O(n log n) apparaît également, mais principalement à cause du tri ou des structures de données où vous parlez de complexité en termes de nombre de comparaisons.Le coût de chaque comparaison est généralement considéré comme non pertinent, car le concepteur de l'algorithme n'a généralement aucun contrôle sur celui-ci (il est fourni par l'utilisateur de l'algorithme ou de la structure de données).

Dans le cas étonnamment improbable où je serais l'intervieweur pour un poste d'universitaire CS couvrant l'arithmétique à précision arbitraire, alors je voudrais certainement que les candidats connaissent la complexité de divers algorithmes pour diverses opérations, et bien sûr connaissent l'état de l'art pour les non triviaux.

Est-ce correct?Je n'ai vu personne d'autre affirmer que Python compare les entiers en temps de journalisation.Python a en effet un format entier de précision arbitraire.Cependant, nous devons ici faire une comparaison équitable.Si l’on considère le sous-ensemble des entiers sur la limite de $[0,2^{64}]$, nous constatons que l’opération Python est à temps constant.

Ce que vous voyez est l'une des limites de la mesure de la complexité informatique à l'aide de la notation big-oh.Il décrit ce qui se passe lorsque n s'approche de l'infini, mais ne permet pas nécessairement de comparer correctement le comportement de nombres plus petits.Nous le voyons de manière célèbre dans algorithmes de multiplication matricielle.Il existe certains algorithmes qui sont plus efficaces dans un sens large, mais qui sont en réalité plus lents en pratique jusqu'à ce que vous arriviez à des matrices gargantuesques.

Dans le contexte de la conduite d'un entretien, devriez-vous remarquer ou vous soucier si un candidat appelle cela O(1) ?

Cela dépend de la raison pour laquelle vous les embauchez.Pour la grande majorité des emplois, l’appeler O(1) devrait convenir.En effet, c’est ainsi que nous avons tendance à l’enseigner à l’école.Si vous souhaitez en faire une opportunité utile pour en savoir plus sur votre candidat, vous pouvez lui demander pourquoi il pense que l'addition est un temps constant (à laquelle la réponse est que le modèle qu'il a utilisé pour déterminer big-oh l'a supposé...ce qui est une réponse valable)

Si vous embauchez quelqu'un pour rechercher des éléments tels que des exploits dans votre code, vous souhaiterez peut-être aller plus loin.Un bignum produit par votre propre code est une chose, mais l'utilisateur est-il autorisé à saisir le numéro de son choix ?Si tel est le cas, ils pourront peut-être créer des attaques temporelles et des DOS en utilisant le fait que cet ajout peut être terriblement lent.Détecter ce risque pourrait faire partie de leur travail.

Devriez-vous remarquer ou vous soucier de cette distinction dans le monde réel ?

Pratiquement parlant:Non.Pas tant que vous ne l'aurez pas rencontré et que vous aurez résolu le problème lors du débogage.Python fait un parcelle de choses qui sont « généralement sûres » et très efficaces.C’est pourquoi il est devenu l’une des langues les plus populaires au monde.

Pour une situation équivalente :à quelle vitesse est x.y en Python ?Nous le considérons comme O(1), mais il y a en fait une recherche de hachage.Cette recherche de hachage utilise un mécanisme de sondage connu et la recherche résultante est en réalité O(n).Vous ne verrez jamais cela dans le code normal.Mais dans le code où un adversaire remplit votre dictionnaire avec son propre contenu, il peut intentionnellement créer des clés qui entrent en collision de cette manière.

Je n'ai jamais rencontré de texte qui a traité des opérations entier "régulières" comme tout ce qui est en outre du temps constant, avec l'hypothèse implicite que la taille avait une limite supérieure finie raisonnable (par exemple 64 bits).Peut-être serait-il plus précis d'indiquer l'hypothèse, mais d'un public CS, je pense que c'est implicite.

Cela introduirait beaucoup de complexité dans les discussions de sujets essentiellement non liés.Les implémentations de BigintInty ne sont généralement pas mises en œuvre, mais dans la base (taille de mot de la machine), de sorte que le problème O (B)> O (1) ne chante que pour des nombres fabuleusement importants.

Personnellement tout en interviewant quelqu'un, j'apprécierais que la rigueur et la largeur des connaissances associées à la connaissance des entiers python étaient une longueur arbitraire, mais tout ce qui est au-delà indiquant l'hypothèse que tous les mathématiques sont O (1) se sentiraient extrêmement pédant.Si l'analyse a commencé à devenir trop éloignée avec arithmétique et temps perdu, je considérerais cela un mauvais candidat.

Licencié sous: CC-BY-SA avec attribution

Non affilié à cs.stackexchange