2015-06-29 2 views
7

Das Problem der Verwendung von Doppelpunkten als Schlüssel in Karten/Sets ist Gleitkomma-Genauigkeit.Möglichkeiten mit einem Doppel als Schlüssel in einem Std-Set/Karte

Einige Leute haben vorgeschlagen, ein Epsilon in Ihrer Vergleichsfunktion hinzuzufügen, aber das bedeutet, dass Ihre Schlüssel nicht mehr die strikt schwache Reihenfolge Kriterium erfüllen. Dies bedeutet, dass Sie abhängig von der Reihenfolge des Einfügens Ihrer Elemente ein anderes Set/Map erhalten.

In dem Fall, in dem Sie Daten basierend auf doppelten Werten aggregieren/kombinieren/zusammenführen und bereit sind, ein gewisses Maß an Rundung/epsilon zuzulassen (klar, müssen Sie), ist die folgende Lösung ein gutes Idee?

alle Konvertieren Sie die Doppel (wo wir als Schlüssel bestimmt) in ganze Zahlen von ihnen durch die Präzision Faktor (zB 1e8) und Rundung auf die nächste ganze Zahl (int)i+0.5 (wenn i> 0) multipliziert wird, dann einen Satz/Karte, die Schlüssel erstellen aus diesen ganzen Zahlen. Wenn Sie die endgültigen Werte der Schlüssel extrahieren, teilen Sie die Werte durch den Präzisionsfaktor, um den doppelten Wert zurückzuerhalten (wenn auch gerundet).

+0

Vielleicht verwenden Sie einfach eine willkürliche Genauigkeit Bibliothek (wie GMP) Datentyp als Schlüsseltyp? – PaulMcKenzie

+0

Warum betrachten Sie Gleitkommapräzision als ein Problem, wenn Sie Doubletten als Schlüssel in einer Baum- oder Hashtabellenstruktur verwenden? Es funktioniert, solange Sie keine NaNs als Schlüssel verwenden, und es funktioniert sogar genau so, wie Sie es erwarten. – tmyklebu

+0

Ich frage mich, welche Art von Problem möglicherweise Fließkommawerte in Sätzen oder Karten erfordern könnte. Sätze und Zuordnungen sind eine natürliche Anpassung für diskrete Daten, Gleitkommawerte sind gut für kontinuierliche Daten. –

Antwort

3

„Convert alle Doppelzimmer (wo wir als Schlüssel bestimmt) in ganze Zahlen von ihnen durch die Genauigkeit Faktor multipliziert wird (zB 1e8) und Rundung auf die nächste ganze Zahl (int)i+0.5 (wenn i> 0), dann einen Satz erstellen/map, die diese Ganzzahlen abtastet. Wenn Sie die endgültigen Werte der Schlüssel extrahieren, teilen Sie die Ints durch den Genauigkeitsfaktor, um den doppelten Wert zurückzuerhalten (wenn auch gerundet). "

I empfehlen Integer-Typ Tasten (z.B. long long) für die Karte in den ersten Platz, und schneiden sie für double Darstellung für die Teilung eine feste Genauigkeit verwenden.

Aber das hängt davon ab, ob Sie fix point math für Ihren tatsächlichen Anwendungsfall anwenden können. Wenn Sie einen großen Bereich von Wertegenauigkeiten abdecken müssen (wie z. B. + -1e-7 - + -1e7), wird ein solcher Ansatz nicht funktionieren.

+0

danke für den Vorschlag, aber wie genau ist es anders als meine Lösung (Entschuldigung, dass ich es nicht verstanden habe). Sie schlagen vor, Integer-Schlüssel (skaliert und abgerundet, wie ich es vorgeschlagen habe?) in der Karte zu verwenden und durch die gleiche Skala zu dividieren, um die doppelten Werte zurück zu bekommen? – zhaomin

+0

@zhaomin Es gibt keinen großen Unterschied zu dem, was du beschrieben hast, ich wollte dich nur ermutigen, in diese Richtung zu gehen. Beachten Sie auch, dass feste Gleitkommawerte leicht in eine Klasse eingekapselt werden können. Es gibt sogar eine Standardimplementierung dafür: ['std :: ratio'] (http://en.cppreference.com/w/cpp/numeric/ratio) –

+0

danke. Leider suche ich diese Zahlen während der Laufzeit, so dass std :: ratio nicht funktioniert. aber danke für den Vorschlag – zhaomin

1

all Konvertieren Sie die Doppel (wo wir als Schlüssel bestimmt) in ganzen Zahlen von ihnen durch die Präzision Faktor (zB 1e8) und Rundung auf die nächste ganze Zahl (int) i 0,5 + multipliziert (wenn i> 0) Erstellen Sie dann einen Satz/eine Karte, die aus diesen ganzen Zahlen ausschließt. Beim Extrahieren der endgültigen Werte der Schlüssel teilen Sie die Ints mit dem Präzisionsfaktor, um den doppelten Wert zurück (wenn auch gerundet) zu erhalten.

Statt durch die Präzision Faktor der Aufteilung die Doppel zurück, einfach speichern die doppelten zusammen mit dem zugehörigen Wert in einer Struktur zu erhalten, und setzt diese Struktur im Wörterbuch als „Wert“ für den Integer-Schlüssel. Auf diese Weise ist der Original Doppelwert immer noch vorhanden und kann für Berechnungen verwendet werden. Nur nicht für die Schlüsselsuche.

Wenn Sie jedoch mit leicht gerundeten Werten leben können (weil Sie einfach eine ganze Zahl durch ein Epsilon teilen), ist Ihr vorgeschlagener Ansatz bereits gut genug.

Wie die andere Antwort sagt, hängt es sehr von der Bandbreite der Werte ab. Wenn einige extrem groß sind und andere extrem klein sind, funktioniert Ihr Ansatz, um Integer-Schlüssel zu erhalten, nicht. Wenn sie nur ein paar Ziffern voneinander entfernt sind, dann könnte es sein.

+0

danke für den Vorschlag. Ich würde es sogar vorziehen, den gerundeten Wert zu verwenden, da dieser besser die Menge der Doppelpunkte darstellt, die gerundet werden, anstatt das erste Double zu wählen, das in das Set gelegt wurde. – zhaomin