Nehmen Sie einen benutzerdefinierten IComparer, der zwei Doubles als gleich behandelt, wenn ihre Differenz kleiner ist als ein gegebenes Epsilon.
Was würde passieren, wenn dieser IComparer in einer OrderBy () verwendet wird. ThenBy () -Klausel?
Speziell denke ich an die folgende Implementierung:
%Vor% Nun ist diese Beziehung zwischen IComparern eindeutig nicht transitiv. ( if a ~ b and b ~ c then a ~ c )
Mit epsilon == 0.6:
Was passiert, wenn dieser IComparer in einer OrderBy-Abfrage wie folgt verwendet wird:
%Vor%Würde sich die Sortierung so verhalten, wie man es erwarten würde, indem man die Liste zuerst nach X und dann nach Y sortiert, während man ungefähr gleiche Werte als genau gleich behandelt? Würde es unter bestimmten Umständen explodieren? Oder ist diese ganze Art schlecht definiert?
Was genau sind die Konsequenzen eines IComparers ohne Transitivität?
(Ich weiß, dass dies höchstwahrscheinlich ein undefiniertes Verhalten der c # Sprache ist. Ich bin immer noch sehr an einer Antwort interessiert.)
Und gibt es eine alternative Möglichkeit, dieses Sortierverhalten zu erhalten?
(neben dem Runden der Werte, die Artefakte einbringen würden, wenn für zwei nahe Doppelte der eine aufgerundet wird und der andere runter)
Ein Online-Code in dieser Frage ist hier verfügbar:
Das Problem ist, dass die erste Sortierstufe (in X ) bereits zu anderen Aufträgen führen kann. Stellen Sie sich vor, dass alle Elemente innerhalb eines Epsilons voneinander sind. Dann stimmen alle Sortierreihenfolgen mit Ihrem Vergleich überein, weil es immer 0 zurückgibt. Der Sortieralgorithmus könnte Münzen umdrehen und dennoch eine "richtige" Antwort liefern. Nicht nützlich.
Wenn die erste Ebene beliebig sortiert ist, können Sie nicht erwarten, dass die 2. Sortierstufe funktioniert.
Natürlich ist die ganze Diskussion umstritten, weil Sie die Voraussetzung der Sortier-API verletzen. Selbst wenn es funktionieren sollte, konnten Sie nicht sicher sein, dass es auf a) allen Daten b) auf allen zukünftigen Versionen von .NET funktionieren würde.
Wie können Sie Ihr Ziel noch erreichen? Ihr Problem ist nur schlecht definiert, weil viele Lösungen möglich sind. Ich bekomme, was Sie erreichen wollen, aber es ist nicht möglich mit Ihrer aktuellen Definition des Problems.
Ich schlage vor: Sortiere alle Items nach X (ohne epsilon). Durchqueren Sie dann die sortierten Objekte von links nach rechts und fügen Sie die Elemente in Gruppen zusammen, die höchstens ein Epsilon breit sind. Das gibt Ihnen Gruppen von Elementen, deren X -Wert höchstens epsilon ist.
Sie können dann die Gruppennummer als erste Sortierstufe verwenden. Es ist nur eine einfache Ganzzahl, also kein Problem beim Sortieren. Für das Feld Y können Sie dann einen normalen Vergleich ohne epsilon verwenden (oder den gleichen Trick wiederholen).
Sehen Sie sich mein Code-Snippet hier an. Es ist nur für die Sortierung auf der ersten Ebene und nicht optimiert.
OrderBy und ThenBy verwenden einen allgemeinen Algorithmus. Sie müssen OrderBy und ThenBy mit einem speziellen Algorithmus wie meinem implementieren. dann kann es als OrderBy().ThenBy() funktionieren.
Detail des Algorithmus:
in einer sortierten Reihenfolge (x1 x2 x3 ...) unter Ihrem EpsilonComparer, wenn x4 & gt; x1, dann x5 & gt; x1. wenn x4 = x1, dann ist x3 = x1 und entweder x5 & gt; x1 oder x5 = x1.
mit epsilon (0.4), Eingabe folgende Zahlen: 0.1, 0.6, 1, 1.1, 1.6, 2, 2, 2.6, 3, 3.1, 3.6, 4, 4.1, 4.6, 5, 5.1, 5.6, 6, 6.1 , 6.6
Ergebnis: 0,1 0,6 1 1,1 (1,6 2 2) 2,6 3 3,1 3,6 4 4,1 4,6 (5 5,1) 5,6 (6 6,1) 6,6
(a, b, c) zeigt an, dass diese Zahlen gleich sind und die Reihenfolge der Zahlen nicht festgelegt ist. sie können (a, b, c), (c, a, b) und jede andere Reihenfolge sein.
a b zeigt ein & lt; b und Reihenfolge ist behoben.
%Vor%Tags und Links c# linq undefined-behavior sorting internals