Sollte `Vector <float> .Equals` reflexiv sein oder sollte es der IEEE 754-Semantik folgen?

9

Beim Vergleich von Gleitkommawerten auf Gleichheit gibt es zwei verschiedene Ansätze:

  • NaNnicht gleich sich selbst sein, was der IEEE 754- Spezifikation entspricht.
  • NaNGleichheit mit sich selbst, die die mathematische Eigenschaft der Reflexivität liefert, die für die Definition einer Äquivalenzbeziehung wesentlich ist

Die eingebauten IEEE-Gleitkommatypen in C # ( floatund double) folgen der IEEE-Semantik für ==und !=(und den relationalen Operatoren wie <), gewährleisten jedoch die Reflexivität für object.Equals, IEquatable<T>.Equals(und CompareTo).

Betrachten Sie nun eine Bibliothek, die Vektorstrukturen über float/ bereitstellt double. Ein solcher Vektortyp würde ==/ !=und object.Equals/ überschreiben IEquatable<T>.Equals.

Alle sind sich einig, dass ==/ !=sollte der IEEE-Semantik folgen. Die Frage ist, Equalsob eine solche Bibliothek die Methode (die von den Gleichheitsoperatoren getrennt ist) auf eine Weise implementiert , die reflexiv ist oder der IEEE-Semantik entspricht.

Argumente für die Verwendung der IEEE-Semantik für Equals:

  • Es folgt IEEE 754
  • Es ist (möglicherweise viel) schneller, weil es SIMD-Anweisungen nutzen kann

    Ich habe eine separate Frage zum Stapelüberlauf gestellt, wie Sie die reflexive Gleichheit mithilfe von SIMD-Anweisungen und deren Auswirkungen auf die Leistung ausdrücken würden: SIMD-Anweisungen für den Gleitkomma-Gleichheitsvergleich

    Update: Es scheint möglich zu sein, die reflexive Gleichheit mithilfe von drei SIMD-Anweisungen effizient zu implementieren.

  • Die Dokumentation für Equalserfordert keine Reflexivität, wenn Gleitkomma verwendet wird:

    Die folgenden Aussagen müssen für alle Implementierungen der Equals (Object) -Methode zutreffen. In der Liste x, yund zObjektreferenzen darstellen , die nicht null sind.

    x.Equals(x)Gibt zurück true, außer in Fällen, in denen Gleitkommatypen verwendet werden. Siehe ISO / IEC / IEEE 60559: 2011, Informationstechnologie - Mikroprozessorsysteme - Gleitkomma-Arithmetik.

  • Wenn Sie Floats als Wörterbuchschlüssel verwenden, leben Sie in einem Zustand der Sünde und sollten kein vernünftiges Verhalten erwarten.

Argumente für Reflexivität:

  • Es ist im Einklang mit dem bestehenden Typen, einschließlich Single, Double, Tupleund System.Numerics.Complex.

    Ich kenne keinen Präzedenzfall in der BCL, in Equalsdem IEEE folgt, anstatt reflexiv zu sein. Gegenbeispiele sind Single, Double, Tupleund System.Numerics.Complex.

  • Equalswird hauptsächlich von Containern und Suchalgorithmen verwendet, die auf Reflexivität beruhen. Für diese Algorithmen ist ein Leistungsgewinn irrelevant, wenn sie nicht funktionieren. Opfern Sie nicht die Korrektheit für die Leistung.
  • Es bricht alle Hash - basierte Sets und Wörterbücher, Contains, Find, IndexOfauf verschiedenen Sammlungen / LINQ, Satz basiert LINQ - Operationen ( Union, Exceptusw.) , wenn die Daten enthält NaNWerte.
  • Code, der tatsächliche Berechnungen durchführt, bei denen die IEEE-Semantik akzeptabel ist, funktioniert normalerweise mit konkreten Typen und Verwendungen ==/ !=(oder wahrscheinlicher Epsilon-Vergleichen).

    Sie können derzeit keine Hochleistungsberechnungen mit Generika schreiben, da Sie dafür arithmetische Operationen benötigen, diese sind jedoch nicht über Schnittstellen / virtuelle Methoden verfügbar.

    Eine langsamere EqualsMethode würde sich also nicht auf die meisten Hochleistungscodes auswirken.

  • Es ist möglich, eine IeeeEqualsMethode oder eine IeeeEqualityComparer<T>für die Fälle bereitzustellen, in denen Sie entweder die IEEE-Semantik oder einen Leistungsvorteil benötigen.

Meiner Meinung nach sprechen diese Argumente stark für eine reflexive Umsetzung.

Das CoreFX-Team von Microsoft plant die Einführung eines solchen Vektortyps in .NET. Im Gegensatz zu mir bevorzugen sie die IEEE-Lösung , hauptsächlich aufgrund der Leistungsvorteile. Da eine solche Entscheidung nach einer endgültigen Veröffentlichung sicherlich nicht geändert wird, möchte ich Feedback von der Community erhalten, was ich für einen großen Fehler halte.

CodesInChaos
quelle
1
Ausgezeichnete und zum Nachdenken anregende Frage. Für mich (zumindest) macht das keinen Sinn ==und Equalswürde unterschiedliche Ergebnisse liefern. Viele Programmierer gehen davon aus und tun dasselbe . Darüber hinaus rufen Implementierungen der Gleichheitsoperatoren im Allgemeinen die EqualsMethode auf. Sie haben argumentiert, dass man eine einschließen könnte IeeeEquals, aber man könnte es auch umgekehrt machen und eine Methode einschließen ReflexiveEquals. Der Vector<float>Typ kann in vielen leistungskritischen Anwendungen verwendet werden und sollte entsprechend optimiert werden.
Die Maus
@diemaus Einige Gründe, warum ich das nicht überzeugend finde: 1) für float/ doubleund einige andere Typen ==und Equalssind bereits unterschiedlich. Ich denke, eine Inkonsistenz mit vorhandenen Typen wäre noch verwirrender als die Inkonsistenz zwischen ==und EqualsSie müssen sich immer noch mit anderen Typen befassen. 2) Nahezu alle generischen Algorithmen / Sammlungen verwenden Equalsund verlassen sich auf ihre Funktionsreflexivität (LINQ und Wörterbücher), während konkrete Gleitkomma-Algorithmen normalerweise dort verwendet werden, ==wo sie ihre IEEE-Semantik erhalten.
CodesInChaos
Ich würde Vector<float>ein anderes "Biest" in Betracht ziehen als ein einfaches floatoder double. Durch diese Maßnahme kann ich den Grund Equalsoder den ==Betreiber nicht erkennen , die Standards von ihnen einzuhalten. Sie sagten selbst: "Wenn Sie Floats als Wörterbuchschlüssel verwenden, leben Sie in einem Zustand der Sünde und sollten kein vernünftiges Verhalten erwarten." Wenn man NaNin einem Wörterbuch speichert , dann ist es ihre eigene verdammte Schuld, schreckliche Praktiken anzuwenden. Ich denke kaum, dass das CoreFX-Team dies nicht durchdacht hat. Ich würde mit einem ReflexiveEqualsoder ähnlichem gehen, nur um der Leistung willen.
Die Maus

Antworten:

5

Ich würde argumentieren, dass das IEEE-Verhalten korrekt ist. NaNs sind in keiner Weise gleichwertig; Sie entsprechen schlecht definierten Bedingungen, unter denen eine numerische Antwort nicht angemessen ist.

Abgesehen von den Leistungsvorteilen, die sich aus der Verwendung der IEEE-Arithmetik ergeben, die die meisten Prozessoren nativ unterstützen, gibt es meines Erachtens ein semantisches Problem, wenn dies gesagt isnan(x) && isnan(y)wird x == y. Zum Beispiel:

// C++
double inf = std::numeric_limits<double>::infinity();
double x = 0.0 / 0.0;
double y = inf - inf;

Ich würde argumentieren, dass es keinen sinnvollen Grund gibt, warum man dies für xgleich halten würde y. Man kann kaum schlussfolgern, dass es sich um äquivalente Zahlen handelt; Sie sind überhaupt keine Zahlen, daher scheint es nur ein völlig ungültiges Konzept zu sein.

Aus Sicht des API-Designs ist es außerdem sinnvoll, die branchenweit typischste Gleitkommasemantik zu verwenden, wenn Sie an einer Allzweckbibliothek arbeiten, die von vielen Programmierern verwendet werden soll. Das Ziel einer guten Bibliothek ist es, Zeit für diejenigen zu sparen, die sie nutzen. Daher ist das Einbauen von nicht standardisiertem Verhalten reif für Verwirrung.

Jason R.
quelle
3
Das NaN == NaNsollte false zurückgeben ist unbestritten. Die Frage ist, was die .EqualsMethode tun soll. Wenn ich NaNbeispielsweise als Wörterbuchschlüssel verwende, kann der zugehörige Wert nicht mehr abgerufen werden, wenn NaN.Equals(NaN)false zurückgegeben wird.
CodesInChaos
1
Ich denke, Sie müssen für den allgemeinen Fall optimieren. Der häufigste Fall für einen Zahlenvektor ist die numerische Berechnung mit hohem Durchsatz (häufig optimiert mit SIMD-Anweisungen). Ich würde argumentieren, dass die Verwendung eines Vektors als Wörterbuchschlüssel ein äußerst seltener Anwendungsfall ist und es kaum wert ist, Ihre Semantik zu entwerfen. Das Gegenargument, die ich am sinnvollsten erscheint ist Konsistenz, da die bestehenden Single, Doubleusw. Klassen bereits die reflexiven Verhalten haben. IMHO, das war zunächst nur die falsche Entscheidung. Aber ich würde nicht zulassen, dass Eleganz der Nützlichkeit / Geschwindigkeit im Wege steht.
Jason R
In der Regel werden jedoch numerische Berechnungen verwendet, ==die immer IEEE gefolgt sind, sodass sie den schnellen Code erhalten, unabhängig davon, wie er Equalsimplementiert ist. IMO ist der springende Punkt bei der Verwendung einer separaten EqualsMethode die Verwendung in Algorithmen, die sich nicht um den konkreten Typ kümmern, wie z. B. die Distinct()Funktion von LINQ .
CodesInChaos
1
Ich verstehe das. Aber ich würde gegen eine API argumentieren, die einen ==Operator und eine Equals()Funktion hat, die unterschiedliche Semantik haben. Ich denke, Sie zahlen aus Entwicklersicht die Kosten potenzieller Verwirrung ohne wirklichen Nutzen (ich lege keinen Wert darauf zu, einen Zahlenvektor als Wörterbuchschlüssel verwenden zu können). Es ist nur meine Meinung; Ich glaube nicht, dass es eine objektive Antwort auf die vorliegende Frage gibt.
Jason R
0

Es gibt ein Problem: IEEE754 definiert relationale Operationen und Gleichheit auf eine Weise, die für numerische Anwendungen gut geeignet ist. Es ist nicht gut zum Sortieren und Hashing geeignet. Wenn Sie also ein Array nach numerischen Werten sortieren oder einem Satz numerische Werte hinzufügen oder diese als Schlüssel in einem Wörterbuch verwenden möchten, erklären Sie entweder, dass NaN-Werte nicht zulässig sind, oder Sie verwenden IEEE754 nicht eingebaute Operationen. Ihre Hash-Tabelle müsste sicherstellen, dass alle NaNs mit demselben Wert übereinstimmen, und gleich miteinander vergleichen.

Wenn Sie Vektor definieren, müssen Sie die Entwurfsentscheidung treffen, ob Sie ihn nur für numerische Zwecke verwenden möchten oder ob er mit Sortieren und Hashing kompatibel sein soll. Ich persönlich denke, dass der numerische Zweck viel wichtiger sein sollte. Wenn Sortieren / Hashing erforderlich ist, können Sie eine Klasse mit Vector als Mitglied schreiben und Hashing und Gleichheit in dieser Klasse nach Ihren Wünschen definieren.

gnasher729
quelle
1
Ich stimme zu, dass numerische Zwecke wichtiger sind. Aber wir haben bereits die ==und !=Operatoren für sie. Nach meiner Erfahrung wird die EqualsMethode so ziemlich nur von nicht numerischen Algorithmen verwendet.
CodesInChaos