Ich habe den folgenden Code, der eine Liste in absteigender Reihenfolge sortiert
%Vor%Das Ergebnis ist
%Vor%Jetzt weiß ich, dass ich y-x nicht schreiben sollte, weil es Überlaufprobleme verursachen kann.
Aber die Frage ist, warum ist das Ergebnis? Ich glaubte, die Ausgabe wäre [2147483647, -1] , weil -1 - Integer.MAX_VALUE ist -2147483648 , immer noch eine negative ganze Zahl, und die Operation scheint nicht von Überlaufproblem betroffen sein.
Was habe ich falsch gemacht?
Wie Sie in Oracles Object Ordening Java Tutorial im unteren Bereich des Seite:
Sie könnten versucht sein, die endgültige Rückgabeanweisung in der Vergleicher mit dem einfacheren:
%Vor%Tu es nicht, wenn du absolut bist sicher niemand wird jemals eine negative mitarbeiter nummer haben! Dieser Trick funktioniert funktioniert im Allgemeinen nicht, weil der vorzeichenbehaftete Integer-Typ nicht groß genug ist um die Differenz zweier beliebiger vorzeichenbehafteter Ganzzahlen darzustellen. Wenn ich es ist eine große positive ganze Zahl und j ist eine große negative ganze Zahl, i - j wird Überlauf und gibt eine negative Ganzzahl zurück. Der resultierende Vergleicher verstößt gegen eine der vier technischen Beschränkungen, über die wir reden (Transitivität) und produziert schreckliche, subtile Bugs. Das ist kein rein theoretisches Anliegen; Leute werden dadurch verbrannt.
Die hier beschriebene Situation ist, was der OP begegnet: Der Unterschied zwischen den beiden ganzen Zahlen ist mehr als Integer.MAX_VALUE und wird daher während des Vergleichs überlaufen, was zu einer unerwarteten Sortierung führt.
Ich habe gerade getan, was @Robin Topper genau gesagt hat.
%Vor%Und ich habe
%Vor% Und das können wir sehen
Liste # sort (Vergleicher) wendet Werte auf angegebene Comparator in umgekehrter Reihenfolge an.
Comparator , -1 und 2147483647 gilt, (y - x) -Teil ( 2147483647 - -1 ) ist als -2147483648 übergelaufen, was negativ ist, -1 kleiner ist als 2147483647 . Hier sind die Quellcodes.
%Vor% %Vor% Bevor wir beginnen, müssen Sie wissen, dass der Vergleicher das Paar (x, y) so betrachtet, wie es nach seinem Design geordnet ist, wenn compare(x,y) < 0
(genau wie für natürliche (aufsteigende) Reihenfolge: wenn x<y dann x-y<0 ).
Ganzzahlüberlauf
Wenn in der mathematischen Welt x und y in Paaren (x, y) in aufsteigender Reihenfolge stehen, können wir sie als x<y schreiben, was auch als x-y<0 umgeschrieben werden kann. Die absteigende Reihenfolge kann als x>y dargestellt werden, die als x-y>0 neu geschrieben werden kann.
Aber solches Umschreiben ist nur in der mathematischen Welt möglich. In der IT-Welt haben numerische Typen wie int ihre Min- und Max-Werte, und wenn wir versuchen, Werte aus diesem Bereich zu berechnen, werden wir Integerüberlauf . Ihr Beispiel ist einer dieser Fälle. Wenn x = -1 und y = 2147483647 , gibt der Komparator, der y-x berechnet, -2147483648
anstelle von positivem 2147483648 .
Aus diesem Grund wird falsches (und negatives) Ergebnis zurückgegeben, wodurch der Sortieralgorithmus "denkt", dass Werte von x und y in richtige Bestellung.
Warte, wenn das Ergebnis ein Fehler war, wie haben wir als Ergebnis Elemente in aufsteigender Reihenfolge [-1, 2147483647] ? Sollte diese "falsche" Reihenfolge nicht fallen?
Nein, weil der Komparator, der y-x zurückgibt, die absteigende Reihenfolge beschreibt. Schau mal. Die Elemente x und y , die in einem Comparator.compare(x,y) verwendet werden, werden in der richtigen Reihenfolge betrachtet, wenn Comparator.compare(x,y)<0 . Wenn wir den Code unseres Komparators verwenden, erhalten wir y-x<0 , in der Reihenfolge Wörter y<x (oder einfacher x>y ).
Es kann auch leicht beobachtet werden, wenn wir ein paar Elemente in der Liste ändern
%Vor%wo nach dem Sortieren wir
bekommen %Vor%Kurz gesagt:
-1 und 2147483647 zu ändern, damit sie an ihren Positionen bleiben. Tags und Links java overflow comparator