Java-Sortierbericht: Die Vergleichsmethode verstößt gegen ihre allgemeine Vertragsausnahmelösung

Dieser Artikel stellt Ihnen hauptsächlich die Lösung für die Ausnahme beim Sortieren von Berichten in Java vor: Die Einführung im Artikel ist sehr detailliert und hat einen gewissen Referenz- und Lernwert für alle Freunde, die sie benötigen Kommen Sie vorbei und schauen Sie vorbei.

Vorwort

A Comparison method violates its general contract erschien letzte Woche in einem Stück Java-Code zum Sortieren online, und ich habe es gelernt, als ich dieses Problem gelöst habe Einige Wissen wird hier zusammengefasst und geteilt.

Ausnahmegrund

Die durch diese Sortierung verursachte Ausnahme erscheint in Versionen über Java7, also wenn Ihr JDK von 6 If ist Wenn Sie ein Upgrade auf 7 oder 8 durchführen, müssen Sie auf diese Ausnahme achten.

In der Kompatibilitätsliste von Java7 gibt es eine Beschreibung der Inkompatibilität dieser Art:

Area: API: Utilities
Synopsis: Updated sort behavior for Arrays and Collections may throw an IllegalArgumentException
Description: The sorting algorithm used by java.util.Arrays.sort and (indirectly) by java.util.Collections.sort has been replaced. The new sort implementation may throw an IllegalArgumentException if it detects a Comparable that violates the Comparable contract. The previous implementation silently ignored such a situation.
If the previous behavior is desired, you can use the new system property, java.util.Arrays.useLegacyMergeSort, to restore previous mergesort behavior.
Nature of Incompatibility: behavioral
RFE: 6804124

Ich habe aus den Informationen gelesen, dass Java7 mit der Einführung des Timsort-Sortieralgorithmus begonnen hat . Ich hatte immer gedacht, dass die meisten integrierten Sortieralgorithmen in der Standardbibliothek eine schnelle Sortierung ermöglichen. Jetzt habe ich erfahren, dass viele Mehrsprachen Timsort intern verwenden. Dann habe ich diesen Satz auf Wikipedia gefunden:

t wurde 2002 von Tim Peters für den Einsatz in der Programmiersprache Python implementiert.

Dieses Ranking ist also natürlich nach ihm benannt.

Dann habe ich diesen Bildsortierungsvergleich im Internet gefunden:

Man kann feststellen, dass Timsort besser abschneidet als QuickSort.

In diesem Blog wird die Implementierung von Timsort nicht im Detail besprochen (es scheint, dass dieser Algorithmus ziemlich kompliziert ist, um Timsort separat zu diskutieren). Dieser Algorithmus erfordert eindeutig eine strikte monotone Zunahme oder Abnahme während der Implementierung, um die Stabilität des Algorithmus sicherzustellen.

• sgn(compare(x, y)) == -sgn(compare(y, x))

• ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0

• compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z
  

Sieht stark nach der Symmetrie und den transitiven Beziehungen von Mengen aus, die im diskreten Mathematikunterricht gelernt wurden.

Der Grund für die Ausnahme ist also, dass der Sortieralgorithmus nicht streng genug ist. Tatsächlich ist Geschäftscode oft nicht so streng wie reine Technologie. Beispiel für einen Algorithmus wie diesen:

Wählen Sie den niedrigsten Preis unter den Flügen

Wenn dann zwei gleich niedrige Preise gleichzeitig existieren, gemäß der Logik, den niedrigsten Preis zu finden Preis, wenn es so geschrieben wird:

if (thisPrice < lowPrice){
 lowPrice = thisPrice;
}

Dann ist die Niedrigpreisposition „Wer zuerst kommt, mahlt zuerst“.

Aber wenn dies erreicht wird:

if(thisPrice <= lowPrice){
 lowPrice = thisPrice;
}

Dann überdecken die späteren Tiefstpreise die vorherigen und es kommt zu einem „Nachzügler kommt zuerst“. Beim Programmieren stößt man häufig auf die beiden Probleme „Wer zuerst kommt, mahlt zuerst“ und „Wer zuerst kommt, mahlt zuerst“.

Für das oben Gesagte ist es daher notwendig, eine strenge Beurteilung und Implementierung der Größenvergleichsfunktion bereitzustellen. Wenn es also so aussieht:

return x > y ? 1 : -1;

dann ist diese Bedingung nicht erfüllt.

Aber unsere Logik ist komplizierter. Es handelt sich tatsächlich um eine solche Sortierbedingung. Sortieren nach:

• Preis Bei gleichen Preisen wird derjenige mit der früheren Abfahrtszeit zuerst gereiht.

• Wenn auch die Abfahrtszeiten gleich sind, gelten folgende Regeln:

• Nicht gemeinsamer Nonstop>Nonstop> nicht geteilt> Die Attribute des Stopps werden nach Priorität ausgewählt. Wenn diese Attribute alle gleich sind, können sie nur als gleich angesehen werden.

Das Problem mit dieser Beurteilungsfunktion ist also:

public compareFlightPrice(flightPrice o1, flightPrice o2){
 // 非经停非共享
 if (o1.getStopNumber() == 0 && !o1.isShare()) {
 return -1;
 } else if (o2.getStopNumber() == 0 && !o2.isShare()) {
 return 1;
 } else {
 if (o1.getStopNumber() == 0) {
  return -1;
 } else if (o2.getStopNumber() == 0) {
  return 1;
 } else {
  if (!o1.isShare()) {
  return -1;
  } else if (!o2.isShare()) {
  return 1;
  } else {
  if (o1.getStopNumber() > 0) {
   return -1;
  } else if (o2.getStopNumber() > 0) {
   return 1;
  } else {
   return 0;
  }
  }
 }
 }
}

Diese Funktion hat ein offensichtliches „Wer zuerst kommt, mahlt zuerst“-Problem, zum Beispiel für compareFlightPrice(a, b) , wenn ab sowohl nicht geteilt als auch ununterbrochen ist, wird a an erster Stelle gereiht, aber wenn compareFlightPrice(b, a) aufgerufen wird, wird b an erster Stelle gereiht, sodass beurteilt werden muss, dass a nicht geteilt ist und non-stop und b ist nicht non-shared und non-stop, so dass a vorne liegt.

Natürlich gibt es neben der Änderung der Vergleichsfunktion noch eine andere Lösung: Startparameter zur JVM hinzufügen.

-Djava.util.Arrays.useLegacyMergeSort=true

Es sollte auch beachtet werden, dass dies nicht unbedingt bedeutet, dass Ihre Sammlung gleiche Elemente enthält und die Vergleichsfunktion nicht der oben genannten strengen Definition entspricht. Diese Ausnahme wird definitiv stabil angezeigt , wir produzieren Die Wahrscheinlichkeit, dass diese Ausnahme in der Umgebung auftritt, ist sehr gering. Schließlich ist Java nicht dumm genug, zuerst das gesamte Array zu überprüfen. Tatsächlich stellt es fest, dass Sie diese Bedingung während des Sortiervorgangs nicht erfüllen. Es ist also möglich, dass eine Art Inkassoauftrag es Ihnen ermöglicht, dieses Urteil einfach zu umgehen.

Das obige ist der detaillierte Inhalt vonJava-Sortierbericht: Die Vergleichsmethode verstößt gegen ihre allgemeine Vertragsausnahmelösung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!