Warum funktioniert die Python-hash der Unendlichkeit haben die Ziffern von π?

Den hash der Unendlichkeit in Python hat digits matching pi:

>>> inf = float('inf')
>>> hash(inf)
314159
>>> int(math.pi*1e5)
314159

Ist das nur Zufall oder ist es gewollt?

  • Nicht sicher, aber meine Vermutung wäre, dass es als absichtlich, als hash(float('nan')) wird 0.
  • Hmm, keine Erwähnung darüber, dass in sys.hash_info. Easter egg?
  • Scheint, wie jemand in eine Frivole Stimmung eines Tages. Aber-warum nicht?
  • Fragen Sie Tim Peters. Hier ist die commit-wo er eingeführt, diese Konstante, die vor 19 Jahren: github.com/python/cpython/commit/.... Ich behielt diese Besondere Werte, wenn ich überarbeitet der numerischen hash in bugs.python.org/issue8188
  • Danke. Es sieht aus wie Tim kann auch verwendet die Ziffern von e für hash -inf ursprünglich.
  • Ah ja, stimmt. Und anscheinend habe ich geändert, um -314159. Ich hatte vergessen, dass.
  • Wussten Sie testen diese in python-Implementierungen andere als CPython? PyPy, Jython? Wenn nicht, sollten Sie diesem tag mit der entsprechenden Laufzeit, wie es wahrscheinlich ist, spezifisch für die Umsetzung (ob absichtlich oder nicht).
  • Ja, habe ich. Dieses Ergebnis ist dasselbe in CPython, PyPy und Jython.
  • Bitte Bearbeiten Sie die Frage, weil die Antworten nicht erklären, warum andere Laufzeiten das gleiche zu tun.
  • Der genaue Wert der hash nicht dokumentiert; die docs nur Zustand es ist gespeichert in sys.hash_info.inf, so ist es eindeutig nicht eine Sprache, die standard-und daher muss eine Implementierung detail. Diese Informationen haben sollten, kommen, um Licht in Ihre Forschung, was bedeutet, es gehört in die Frage.
  • Ich bin glücklich, mit der Frage in der aktuellen form, aber jeder hat Schreibrechte - wenn Sie denken, dass etwas fehlt (in der Frage oder den Antworten) nur gehen Sie vor und Bearbeiten.

InformationsquelleAutor wim | 2019-05-20
  1. 44

    _PyHASH_INF ist als Konstante definiert gleich 314159.

    Kann ich nicht finden, jede Diskussion über dieses oder Kommentare Angabe von Gründen. Ich denke, es wurde gewählt, mehr oder weniger willkürlich. Ich kann mir vorstellen, dass, solange Sie nicht die gleichen sinnvollen Wert für die anderen hashes, sollte es keine Rolle.

    • Kleiner nitpick: es ist fast unvermeidlich, per definition, dass der gleiche Wert verwendet werden, für die anderen hashes, z.B. in diesem Fall hash(314159) ist auch 314159. Versuchen Sie auch, in Python 3, hash(2305843009214008110) == 314159 (dieser Eingang ist 314159 + sys.hash_info.modulus) etc.
    • Ich meinte nur, dass, solange Sie nicht wählen Sie diesen Wert, um den hash von anderen Werten per definition, wählen Sie dann einen sinnvollen Wert, wie dies nicht erhöhen die Wahrscheinlichkeit von hash-Kollisionen
    • Ah ok, das macht Sinn (so etwas wie: solange Sie nicht den gleichen Wert als hash für andere sinnvolle Werte... oder so ähnlich). Inzwischen hatte ich Spaß, darüber nachzudenken, wie finden alle numerischen Werte, dass hash, um den gleichen Wert; Sie haben die Antwort auf die einzige Frage, die ich finden konnte, hier. 🙂
    InformationsquelleAutor Patrick Haugh
  2. 212

    Fazit: Es ist kein Zufall; _PyHASH_INF ist fest als 314159 in der Standard CPython-Implementierung von Python, und wurde ausgewählt, als ein willkürlicher Wert (offensichtlich von der stellen von π) von Tim Peters im Jahr 2000.

    Den Wert hash(float('inf')) ist eine der system-dependent-Parameter der eingebaute hash-Funktion für numerische Typen, und ist auch verfügbar als sys.hash_info.inf in Python 3:

    >>> import sys
>>> sys.hash_info
sys.hash_info(width=64, modulus=2305843009213693951, inf=314159, nan=0, imag=1000003, algorithm='siphash24', hash_bits=64, seed_bits=128, cutoff=0)
>>> sys.hash_info.inf
314159

    (Gleiche Ergebnisse mit PyPy zu.)

    In Bezug auf code, hash ist eine integrierte Funktion. Berufung auf eine Python-float-Objekt, ruft die Funktion auf, deren Zeiger ist gegeben durch die tp_hash - Attribut der built-in-Typ float (PyTypeObject PyFloat_Type), die ist die float_hash Funktion, definiert als return _Py_HashDouble(v->ob_fval), die wiederum hat

        if (Py_IS_INFINITY(v))
        return v > 0 ? _PyHASH_INF : -_PyHASH_INF;

    wo _PyHASH_INF ist definiert als 314159:

    #define _PyHASH_INF 314159

    In Bezug auf die Geschichte, die erste Erwähnung von 314159 in diesem Zusammenhang in der Python-code ein (Sie finden diese mit git bisect oder git log -S 314159 -p) wurde Hinzugefügt von Tim Peters im August 2000, in dem, was ist jetzt Begehen 39dce293 in der cpython git-repository.

    Die commit-Nachricht sagt:

    Fix für http://sourceforge.net/bugs/?func=detailbug&bug_id=111866&group_id=5470.
    Das war eine irreführende Fehler -- der wahre "Fehler" war, dass hash(x) gab einen Fehler
    zurück, wenn x ist ein infinity. Behoben, dass. Neue Py_IS_INFINITY makro
    pyport.h. Neu geordnet code zu verringern, zunehmende überschneidungen mit der Vermischung von float und
    komplexe zahlen, schob Trents früheren stab an, dass eine logische Schlussfolgerung.
    Feste überaus seltenen Fehler, bei dem hashing der Schwimmer könnten -1 zurück, auch wenn es
    war das nicht ein Fehler (nicht Zeit verschwenden, um zu konstruieren, ein Testfall, es war einfach
    offensichtlich aus dem code, dass es könnte passieren). Verbesserte complex hash, so dass
    hash(complex(x, y)) nicht systematisch gleich hash(complex(y, x)) mehr.

    Insbesondere In diesem Begehen, er Riss sich den code von static long float_hash(PyFloatObject *v) im Objects/floatobject.c und machte es nur return _Py_HashDouble(v->ob_fval); und in der definition von long _Py_HashDouble(double v) im Objects/object.c fügte er die Zeilen:

            if (Py_IS_INFINITY(intpart))
            /* can't convert to long int -- arbitrary */
            v = v < 0 ? -271828.0 : 314159.0;

    Also wie erwähnt, es war eine willkürliche Wahl. Beachten Sie, dass 271828 wird gebildet aus den ersten paar Nachkommastellen von e.

    Verwandte später begeht:

    • Die Wahl der -271828 für -Inf beseitigt alle Zweifel, die der pi-Verein war zufällig.
    • Nein, aber es macht es ungefähr eine Millionen mal weniger wahrscheinlich 😉
    • Nun, es war kein Zweifel in meinem Kopf jedenfalls, nachdem er "314159" in der source code 🙂 ich meine, die Wahrscheinlichkeit P(Programmierer wollte etwas willkürlich und nahm ein paar Ziffern bekannte Konstante) >> P(Programmierer tippte einige Ziffern nach dem Zufallsprinzip) * P(es passiert zu sein eine bestimmte Folge von sechs Ziffern), wo der zweite Faktor ist 1/1000000 aber auch der erste Faktor ist wahrscheinlich kleiner als die LS schon! (Ich habe viele Male geschrieben, "zufällige" zahlen wie 123456 oder 314159, aber nie überprüft, zufällige Zeichenfolgen von Ziffern.) Aber sicher sehen das andere konstant ist auch ganz nett.
    • Sagen wir einfach "entfernt jeden vernünftigen Zweifel" und nennen es einen Tag.
    • Warum haben Sie nicht rufen Sie einfach durch, um _Py_HashBytes(&v, sizeof(v))?!? Also ich meine, in diesem speziellen Fall, Handhabung, Entnahme des Exponenten, etc. habe zu teuer sein - warum das Rad neu erfinden und die Gefahr ungleichmäßigen Auswirkungen der verschiedenen bits der Gleitkomma-Zahl?
    • Siehe den Abschnitt oben, wo es heißt Mai 2010, nämlich die Dokumentation auf Vermischung von numerischen Typen und Problem 8188 — die Idee ist, dass wir wollen, dass hash(42.0) die gleichen sein wie hash(42) auch das gleiche wie hash(Decimal(42)) und hash(complex(42)) und hash(Fraction(42, 1)). Die Lösung (von Mark Dickinson) ist ein elegantes IMO: definieren einer mathematischen Funktion, die funktioniert für beliebige rationale Zahl, und mit der Tatsache, dass floating-point-zahlen sind die rationalen zahlen auch.
    • Ah, danke. Während ich würde nicht darum gekümmert zu garantieren, diese Gleichheit, es ist gut zu wissen, dass es eine gute, solide und logische Erklärung für die scheinbar komplexen code 🙂
    • Eigentlich ist das eine Notwendigkeit. Hashable Objekte, die vergleichen gleich, müssen den gleichen hash-Wert.
    • Die hash-Funktion für Ganzzahlen ist einfach hash(n) = n % M wobei M = (2^61 - 1). Das ist verallgemeinert für rationale n hash(p/q) = (p/q) mod M mit der division interpretiert wird modulo M (in anderen Worten: hash(p/q) = (p * inverse(q, M)) % M). Der Grund, warum wir wollen, dass diese: wenn in einem dict d wir setzen d[x] = foo und dann haben wir x==y (z.B. 42.0==42) aber d[y] ist nicht das gleiche wie d[x], dann hätten wir ein problem. Die meisten der scheinbar komplexen code ergibt sich aus der Natur der floating-point-format selbst, um sich zu erholen die Fraktion richtig und in speziellen Fällen für inf und NaN-Werte.

    InformationsquelleAutor ShreevatsaR
  3. 11

    In der Tat,

    sys.hash_info.inf

    zurück 314159. Der Wert wird nicht generiert, es ist integriert in den source code.
    In der Tat,

    hash(float('-inf'))

    zurück -271828 oder rund -e, in python 2 (es ist -314159 jetzt).

    Die Tatsache, dass die beiden berühmtesten irrationalen zahlen aller Zeit verwendet werden, da die hash-Werte macht es sehr unwahrscheinlich, dass ein Zufall sein.

    InformationsquelleAutor Alec Alameddine
Schreibe einen Kommentar