Gleichheit ganzer Zahlen prüfen:O(1) in C, aber O(log n) in Python 3?

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

Frage

Betrachten Sie diese äquivalenten Funktionen in C und Python 3.Die meisten Entwickler würden sofort behaupten, dass beides der Fall ist $O(1)$.

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

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

Aber bedenken Sie, was unter der Oberfläche passiert.Ganzzahlen sind nur binäre Zeichenfolgen und um die Gleichheit festzustellen, vergleichen beide Sprachen die Zeichenfolgen Stück für Stück.In beiden Fällen ist dieser Scan der Fall $O(b)$ Wo $b$ ist die Anzahl der Bits.Da ganze Zahlen in C eine konstante Größe in Bits haben, ist dies einfach $O(1)$.

BEARBEITEN:C vergleicht nicht Stück für Stück siehe diese Antwort

In Python 3 gilt dies jedoch für ganze Zahlen nicht haben eine feste Größe und der Scan bleibt bestehen $O(b)$ für die Anzahl der Bits in der Eingabe, oder $O(\log a)$ Wo $a$ ist der Wert der Eingabe zur Basis 10.

Wenn Sie also Code in Python analysieren, begeben Sie sich jedes Mal, wenn Sie zwei Ganzzahlen vergleichen, auf eine überraschend komplexe Reise von $O(\log n)$ in Bezug auf den Basis-10-Wert einer der beiden Zahlen.

Für mich wirft das mehrere Fragen auf:

  1. Ist das richtig?Ich habe noch niemanden gesehen, der behauptet, dass Python Ints in der Protokollzeit vergleicht.
  2. Sollten Sie im Zusammenhang mit der Durchführung eines Vorstellungsgesprächs bemerken oder sich darum kümmern, wenn ein Kandidat dies anruft? $O(1)$?
  3. Sollten Sie diesen Unterschied in der realen Welt bemerken oder sich darum kümmern?

BEARBEITEN:Es ist leicht zu verifizieren (und intuitiv), dass Python nicht beliebig große Ints in konstanter Zeit vergleichen kann.Eine bessere Möglichkeit, Frage 1 oben zu stellen, könnte also lauten: „Was (falls vorhanden) ist die Rechtfertigung für den Aufruf dieser Operation?“ $O(1)$?Weil es pragmatisch ist?Konventionell?Impliziert das RAM-Modell?

War es hilfreich?

Lösung 7

tl; DR: Es gibt ein CS-Übereinkommen, um diese Art von Betrieb als $ O (1) $ zu beschreiben, wodurch in extremen Fällen für Python zusammenbrechen. Diese Fälle sind extrem selten, um mit dem Übereinkommen von $ o (1) $ ein negatives Dienstprogramm zu brechen. Diese Art von Pragmatismus ist normal in großer $ o $ .

Es gibt viele sehr gute Antworten auf diese Frage und ich ermutige Sie, sie zu lesen. Aber ich glaube nicht, dass einer von ihnen meine Fragen voll beantwortet. Also hier ist eine Synthese.

ist das richtig? Ich habe noch nicht gesehen, dass Python die Ints in der Protokollzeit vergleicht.

Dies ist überraschend nuanciert. Es ist true , dass Python sehr große Ints in $ O (\ \ log n) $ Runtime vergleicht. Aber ist es korrekte , um diesen Vorgang als $ O (\ \ \ \ log n) $

zu beschreiben

Ich bin letztendlich von diesem von @tomvanderzanden am meisten überredet:

Wenn Sie gesagt haben, dass die C- oder PYTHON-Version $ O (1) $ war, sollte jeder Interviewer vollkommen glücklich sein. Wenn Sie es gesagt haben (die Python-Version) war $ O (\ \ \ log n) $ Sie würden wahrscheinlich immer noch glücklich sein, aber denken Sie, Sie sind eine ziemlich pedantische Person, die nicht tut t Folgen Sie normalen Konventionen.

und

Wenn ich ein Interviewer war, würde ich interessieren, ob Sie die echten Beschränkungen dessen wissen, was Sie tun, und wissen, was theoretisch angeht, wann und dass Sie sie gegebenenfalls mitbringen, wenn sie und nur gegebenenfalls.

Ich akzeptiere jedoch nicht das als Antwort, denn ich denke, der erste Absatz ist derzeit irreführend (glücklich zu ändern).

letztendlich ist dieses Argument pragmatisch. Durch die strikte Definition von Big $ o $ Python Int-Vergleich ist immer noch nachweislich $ O (\ \ \ \ log n) $ . Aber es ist nicht nützlich, es so zu behandeln, also solltest du nicht. Ich würde dazu hinzufügen, dass er streng über große $ o $ ist, um den Punkt der großen $ o $ zu verpassen Analyse.

Andere Tipps

Ganzzahlen sind nur binäre Saiten und, um Gleichheit zu ermitteln, werden beide Sprachen das Bit-Bit-Bit mit den Saiten vergleichen.

nicht ganz. Cints sind maschinenförmig und verglichen mit einem einzigen Maschinenanweisung; Pythonints sind in Basis $ 2 ^ {30} $ (siehe zB https://rusheer.com/blog/python-inter-implementation/ ) und verglich Zigit-by-digit in dieser Basis. Die relevante Basis des Logarithmus ist also $ 2 ^ {30} $ .

Wenn mindestens ein von Zahlen von $ 2 ^ {30d} $ für beliebig begrenzt werden kann $ D $ , der Vergleich ist $ O (1) $ (da die Anzahl der Ziffern zuerst verglichen wird ), und wenn sie nicht können, sind andere Operationen wahrscheinlich viel mehr Anliegen als Gleichheitsvergleich. In der Praxis würde ich sagen, dass es sehr unwahrscheinlich ist, und wenn Sie es wissen, wissen Sie (und nutzen Sie nicht generationspflichtig GNU Multiple Precision Arithmetic Library auch in c).

Komplexität ist relativ zu einem Berechnungsmodell definiert.P und NP beispielsweise sind in Bezug auf Turing-Maschinen definiert.

Betrachten Sie zum Vergleich das Wort RAM-Modell.In diesem Modell ist der Speicher in Worte unterteilt, auf Wörter können in konstanter Zeit aufgerufen werden, und die Größe des Problems kann mit $ O (1) $ Wörter dargestellt werden.

Wenn Sie beispielsweise beispielsweise einen Vergleichsbasierten Sortiervorgang analysieren, gehen wir davon aus, dass die Anzahl der Elemente $ n $ in $ O (1) $ Wörter, sodass es konstante Zeit benötigt, um eine Zahl zwischen $ 1 $ und $ n $ .

ist das richtig? Ich habe noch nicht gesehen, dass Python die Ints in der Protokollzeit vergleicht.

nein (und ein bisschen ja). Betrachten Sie das folgende Nachdenken (jedoch nicht wirklich wahr). Anspruch: Ein Computer kann nur eine endliche Menge an Speicher haben (begrenzt durch die Anzahl der Atome im Universum), so dass die Python-Version auch $ O (1) $ .

Das Problem ist, dass wir versuchen, eine Aussage über Asymptotika (in Bezug auf das, was in der Unendlichkeit gehört) über einen endlichen Zustandsmaschine (Computer) vorzunehmen. Wenn wir die Komplexität des Codes analysieren, analysieren wir den Code selbst nicht, da er auf einem Computer ausgeführt wird, wir analysieren ein idealisiertes Modell des Codes.

Angenommen, ich habe Sie gebeten, einen Sortieralgorithmus in C analysieren, der in C. Sie können analysieren ^ {31} -1 $ . Wenn wir jedoch einen solchen Code analysieren, geben wir vor, dass es willkürlich große Arrays umgehen könnte. Natürlich sagen wir nicht, dass C-Integer-Vergleich $ O (1) $ ist, weil nur 32-Bit-Nummern umgehen kann. .

Im Zusammenhang mit der Durchführung eines Interviews sollten Sie feststellen oder sorgen, wenn ein Kandidat dieses O (1) anruft (1)?

normalerweise nicht. Angenommen, ich führe ein Interview und bittet Sie, ein C- oder Python-Computerprogramm zu schreiben, das die Anzahl der in der Mitarbeiterdatenbank erscheinenden weiblichen Mitarbeiter zählt.

Es wäre unglaublich pedantic, wenn ich mich beklagte, dass Ihr C-Programm falsch war, da er nur bis zu $ 2 ^ {31} -1 $ .

Wir gehen in der Regel davon aus, dass Zahlen klein genug sind, dass sie in ein Wort / integer passen können. Wir gehen davon aus, dass die Zugabe (oder eine andere Nummernoperation) in $ O (1) $ erfolgen kann, da es sehr nervig wäre, $ O (\ \ \ \ \ log n) $ überall und es würde alles nicht lesbar machen, auch wenn $ \ log n $ so klein ist sowieso nicht wirklich wichtig.

Wenn Sie gesagt haben, dass die C- oder PYTHON-Version $ O (1) $ war, sollte jeder Interviewer vollkommen glücklich sein. Wenn Sie es gesagt haben (die Python-Version) war $ O (\ \ \ log n) $ Sie würden wahrscheinlich immer noch glücklich sein, aber denken Sie, Sie sind eine ziemlich pedantische Person, die nicht tut t Folgen Sie normalen Konventionen.

Solltest du diese Unterscheidung in der realen Welt bemerken oder kümmern?

ja! Es beginnt mit der Angelegenheit, wenn Zahlen so groß werden, dass die Annahme, dass sie klein sind, verletzt wird. Nehmen wir an, Sie interviewten für Google, und sie haben Sie gebeten, die Anzahl der Suchanfragen, die von weiblichen Anwendern im vergangenen Jahr durchgeführt wurden, berechnen. Der Interviewer wäre ziemlich gerechtfertigt, um sich zu beschweren, wenn Sie ein C-Programm mit Ints schrieb.

Sie könnten auf die Verwendung von Longs wechseln und immer noch berechtigt sein, es aufzurufen, um ihn aufzurufen $ O (1) $ , und in ähnlicher Weise, die Python-Version $ o (1) $ ist ebenfalls gerechtfertigt. Der $ o (1) $ v.s. $ o (\ log n) $ ding beginnt nur zu egal, wenn die Zahlen sehr lang werden. Wenn Sie beispielsweise ein Programm schreiben, das Ziffern von $ \ PI $ oder eine ähnliche Aufgabe berechnet. Wenn Sie ein Python-Programm für diese Aufgabe geschrieben haben und die Besonderheiten der Komplexität nicht erwähnt haben, würde der Interviewer sich darum kümmern.

Wenn ich ein Interviewer war, würde ich interessieren, ob Sie die echten Beschränkungen dessen wissen, was Sie tun, und wissen, was theoretisch angeht, wann und dass Sie sie gegebenenfalls mitbringen, wenn sie und nur gegebenenfalls.

wann solltest du kümmern?

Bisher bin ich etwas vage über "große" und "kleine" Zahlen gewesen. Im häufig verwendeten RAM-Modell können Sie angenommen werden, dass Integer-Operationen in $ O (1) $ bei Nummern erfolgen können, die höchstens $ o (\ \ log n) $ Bits (wobei $ N $ die Länge des Eingangs ist). Die Rechtfertigung für diese Annahme ist, dass die Zeiger / Indizes in unserer Programmiersprache ein Input von Länge $ N $ haben, so lange genug sein, um die Gesamter Eingaberaum. Wenn also im RAM-Modell die Eingabe binärer Anzahl der $ N $ (binäre) Ziffern ist, ist die Komplexität der Überprüfung der Gleichheit $ O (\ frac {n} {\ log n}) $ Da wir die Gleichheit einer Gruppe von $ o (\ \ log n) $ <überprüfen können < / span> Bits in einer $ o (1) $ Betrieb.

Obwohl dies trivial erscheinen mag, ist Ihr erster Satz falsch. Die Funktionen sind nicht gleichwertig.Um sie äquivalent zu machen, sollte die C-Funktion GMP (oder ähnliches) verwenden, um Arithmetik mit beliebiger Genauigkeit zu implementieren.Der Grund, warum diese Beobachtung nicht trivial ist, liegt darin, dass die Aussage, dass die beiden äquivalent sind, genau in dem Maße vernünftig ist, in dem man sagen kann, dass der Python-Code zeitkonstant ist!Das heißt, wenn wir ignorieren, dass Pythons Ganzzahlen Bignums sind, können (und sollten) wir sie konsequent als feste Größen behandeln.

Betrachten Sie analog die C-Funktion int is_equal(char a, char b) { return a == b; } und die Python-Funktion def is_equal(a: str, b: str) -> bool: return a == b.Es ist jetzt offensichtlicher, dass die Funktionen nicht gleichwertig sind, aber der Grund dafür ist genau der gleiche wie der Grund, warum dies bei Ihnen nicht der Fall ist.Wir gehen einfach davon aus, dass wir in Python ständig massive Strings sehen werden, erwarten aber nicht wirklich massive Ints, obwohl wir natürlich wissen, dass sie möglich sind.Meistens ignorieren wir also die Tatsache, dass Pythons Ganzzahlen groß sind, und analysieren, als ob sie eine feste Größe hätten.In den seltenen Fällen, in denen uns der Zeitpunkt von Bignum-Operationen wichtig ist, können Sie die „echten“ Komplexitäten verwenden.Und natürlich nutzen Sie auch GMP in Ihrem C-Code.

Das alles heißt:Obwohl Sie es nicht bemerkt haben, kennen Sie bereits die Antwort auf Ihre neu formulierte Version Ihrer Frage am Ende, und die Antwort lautet: „Die gleiche Begründung, mit der Sie diese Funktionen als gleichwertig beschrieben haben“.Das Besondere an Python ist, dass es keinen Integer-Typ mit fester Größe hat (also keinen, den die Leute normalerweise verwenden:Es ist natürlich möglich, eines zu schreiben, und es ist eines drin numpy).Aus pragmatischen Gründen möchten wir jedoch nicht, dass uns dies davon abhält, die „übliche“ Komplexitätsanalyse von Algorithmen durchzuführen, die ganze Zahlen verarbeiten, und die „üblichen“ Antworten zu erhalten.Es ist selten notwendig, den Vorbehalt zu berücksichtigen, dass der Vergleich eine Weile dauern kann, wenn wir ein paar 10-GB-Ganzzahlen übergeben, die nahezu gleich sind.

In manchen Fällen könnten Sie dies formalisieren (wenn Sie es wirklich brauchen), indem Sie sagen, dass Sie Ihre Analyse auf kleine ganze Zahlen beschränken.Dann könnten Sie die Komplexität eines Algorithmus anhand der Größe eines Arrays von Ganzzahlen betrachten und alle arithmetischen Operationen als O(1) behandeln.Wenn Sie Algorithmen in Betracht ziehen, die tatsächlich linear oder schlechter in der Größenordnung der ganzen Zahl sind, könnten Sie dies formalisieren, indem Sie sagen, dass Sie den Log-Faktor ignorieren, da es Ihnen eigentlich nur darum geht, ob die Komplexität näher bei liegt linear oder quadratisch, da O(n log n) für Ihre Zwecke so gut wie linear ist.Allerdings ist es fast immer nicht nötig, die Komplexität von Algorithmen zu formalisieren in Python.Wenn man an dem Punkt angelangt ist, eine Programmiersprache zu spezifizieren, betreibt man eigentlich keine abstrakte Informatik mehr ;-)

Im Zusammenhang mit der Durchführung eines Interviews sollten Sie bemerken oder sich darum kümmern, ob ein Kandidat dies nennt $O(1)$?

Hängt vermutlich vom Vorstellungsgespräch ab, aber als Softwareprofi, der in den letzten 10 Jahren hauptsächlich mit Python gearbeitet hat, würde ich das in einem Vorstellungsgespräch nicht danach fragen.Wenn ich eine Frage stellen würde, in der die Komplexität des Ganzzahlvergleichs verborgen ist (z. B. „Was ist die Komplexität dieses Sortieralgorithmus?“), würde ich eine Antwort akzeptieren, die das gesamte Problem ignoriert.Ich würde auch eine akzeptieren, die sich damit befasst.Ich denke schon, dass es sich lohnt, Komplexität im Rahmen der praktischen Programmierung zu verstehen und zu berechnen, ich halte sie nur nicht für so wichtig zum Programmieren Seien Sie sehr vorsichtig, wenn Sie formell angeben, dass es sich um Ganzzahlen angemessener Größe handelt.

Ich würde auch niemals eine Frage stellen, in der ich möchte, dass der Kandidat die Information anbietet, dass Python-Ganzzahlen willkürliche Genauigkeit haben, wenn dies aus irgendeinem Grund, der mit den beteiligten Daten zusammenhängt, offensichtlich nicht für die Frage relevant ist.Wenn die Frage impliziert, dass die beteiligten Zahlen höher als 2 sein können64 Dann möchte ich, dass der Kandidat in einem C-Interview merkt, dass es sich um ein Problem handelt, mit dem er sich befassen muss, und in einem Python-Interview möchte ich, dass der Kandidat weiß, dass dies nicht der Fall ist, aber das würde ich nicht erwarten sich alle Mühe zu geben, es zu sagen.In einem Vorstellungsgespräch bleibt nicht die Zeit, jede noch so kleine Tatsache darzulegen, die etwas unproblematisch macht.

Wenn ich das Verständnis der Komplexität in einem Interview überprüfen wollte, würde ich höchstwahrscheinlich zunächst nach Code für ein Problem fragen, bei dem es eine wirklich einfache „naive“ Lösung mit geringer Komplexität und mindestens eine weniger einfache Lösung mit angemessener Komplexität gibt unter Verwendung bekannter Techniken.Wenn der Kandidat die naive Lösung anbietet, können Sie fragen, wie komplex die Lösung ist und wie sie den Code ändern würden, um ihn zu verbessern.Wenn der Kandidat eine bessere Lösung anbietet, können Sie die naive Lösung beschreiben, darauf hinweisen, wie wenige Codezeilen es sind, und fragen, was daran falsch ist (vielleicht indem Sie fragen: „Wenn Sie den Code von jemandem überprüft haben und er Ihnen das gegeben hat, was?“) würden Sie dazu sagen“?).Für die meisten praktischen Zwecke interessiert Sie nur, ob sie den Unterschied zwischen linear, quadratisch und schlechter als quadratisch erkennen können.O(n log n) erscheint ebenfalls, aber hauptsächlich aufgrund von Sortierungen oder Datenstrukturen, bei denen es um die Komplexität in Bezug auf die Anzahl der Vergleiche geht.Die Kosten jedes Vergleichs werden normalerweise als irrelevant angesehen, da der Algorithmus-Designer normalerweise keine Kontrolle darüber hat (sie werden vom Benutzer des Algorithmus oder der Datenstruktur bereitgestellt).

Für den erstaunlich unwahrscheinlichen Fall, dass ich der Interviewer für eine Stelle als CS-Akademiker wäre, der sich mit Arithmetik mit beliebiger Genauigkeit befasst, würde ich mir auf jeden Fall wünschen, dass die Kandidaten die Komplexität verschiedener Algorithmen für verschiedene Operationen kennen und tatsächlich den Stand der Technik kennen die nicht-trivialen.

Ist das richtig?Ich habe noch niemanden gesehen, der behauptet, dass Python Ints in der Protokollzeit vergleicht.Python hat tatsächlich ein Ganzzahlformat mit beliebiger Genauigkeit.Allerdings müssen wir hier einen fairen Vergleich anstellen.Wenn wir die Teilmenge der ganzen Zahlen an der Grenze von betrachten $[0,2^{64}]$, Wir stellen fest, dass die Python-Operation eine konstante Zeit ist.

Was Sie sehen, ist eine der Grenzen bei der Messung der Rechenkomplexität mithilfe der Big-Oh-Notation.Es beschreibt, was passiert, wenn sich n der Unendlichkeit nähert, eignet sich jedoch nicht unbedingt zum Vergleich des Verhaltens bei kleineren Zahlen.Wir sehen dies bekanntlich in Matrixmultiplikationsalgorithmen.Es gibt einige Algorithmen, die im Großen und Ganzen effizienter sind, in der Praxis jedoch tatsächlich langsamer sind, bis man gigantische Matrizen erreicht.

Sollten Sie im Zusammenhang mit der Durchführung eines Vorstellungsgesprächs bemerken oder sich darum kümmern, wenn ein Kandidat dies als O(1) bezeichnet?

Hängt davon ab, wofür Sie sie einstellen.Für die überwiegende Mehrheit der Jobs sollte es in Ordnung sein, es O(1) zu nennen.Tatsächlich neigen wir dazu, es in der Schule so zu lehren.Wenn Sie daraus eine nützliche Gelegenheit machen möchten, mehr über Ihren Kandidaten zu erfahren, könnten Sie ihn fragen, warum er die Addition für eine konstante Zeit hält (worauf die Antwort lautet, dass das Modell, das sie zur Bestimmung von big-oh verwendet haben, davon ausgegangen ist ...was eine gültige Antwort ist)

Wenn Sie jemanden einstellen, der nach Dingen wie Exploits in Ihrem Code sucht, möchten Sie möglicherweise noch weiter voranschreiten.Eine durch Ihren eigenen Code erstellte Bignum ist eine Sache, aber darf der Benutzer die Nummer seiner Wahl eingeben?Wenn ja, können sie möglicherweise Timing-Angriffe und DOSs erstellen, indem sie die Tatsache ausnutzen, dass dieser Zusatz furchtbar langsam sein kann.Es könnte Teil ihrer Aufgabe sein, dieses Risiko zu erkennen.

Sollten Sie diesen Unterschied in der realen Welt bemerken oder sich darum kümmern?

Praktisch gesprochen:NEIN.Erst wenn Sie tatsächlich darauf stoßen und das Problem im Debug beheben.Python macht ein viel von Dingen, die „im Allgemeinen sicher“ und sehr effizient sind.Aus diesem Grund hat es sich zu einer der beliebtesten Sprachen der Welt entwickelt.

Für eine äquivalente Situation:wie schnell ist x.y in Python?Wir betrachten es als O(1), aber es gibt dort tatsächlich eine Hash-Suche.Diese Hash-Suche verwendet einen bekannten Prüfmechanismus und die resultierende Suche ist tatsächlich O(n).Sie werden dies im normalen Code nie sehen.Aber in Code, in dem ein Angreifer Ihr Wörterbuch mit seinem eigenen Inhalt füllen kann, kann er absichtlich Schlüssel erstellen, die auf diese Weise kollidieren.

Ich habe noch nie einen Text angetroffen, der "regelmäßige" ganzzahlige Operationen als alles außer konstanten Zeit behandelt hat, mit der impliziten Annahme, dass die Größe eine angemessene endliche Obergrenze (z. B. 64 Bit) hatte.Vielleicht wäre es genauer, die Annahme anzusprechen, aber auf ein CS-Publikum, denke ich, dass es implizit ist.

würde also viel Komplexität in Diskussionen von im Wesentlichen nicht zusammenhängenden Themen einführen.BigINT-Implementierungen werden typischerweise nicht mit Bit implementiert, sondern in der Basis- (Maschinenwortgröße), so dass O (B)> o (1) ein Problem nur für fabelhaft große Zahlen eintrifft.

persönlich, während ich jemanden interviewt habe, könnte ich die Rigorin und die Breite des Wissens schätzen, das mit dem Kenntnis der Python-Ganzzahlen in der beliebigen Länge waren, aber alles, was über die Annahme hinausgibt, dass alle Mathematiken o (1) extrem pedantisch fühlen würde.Wenn die Analyse begann, zu weit von der Arithmetik zu weit weg zu kommen, und vergeudete Zeit, würde ich diesen ein schlechter Kandidat betrachten.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange
scroll top