Rapport de tri Java : la méthode de comparaison viole sa solution générale d'exception contractuelle

Cet article vous présente principalement la solution à l'exception du rapport de tri en Java : la méthode de comparaison viole son contrat général. L'introduction dans l'article est très détaillée et a une certaine valeur de référence et d'apprentissage pour tous les amis qui en ont besoin. venez nous rejoindre.

Préface

Un Comparison method violates its general contract est apparu dans un morceau de code Java de tri en ligne la semaine dernière, et je l'ai appris en résolvant ce problème. Certains les connaissances sont résumées et partagées ici.

Raison de l'exception

L'exception provoquée par ce tri apparaîtra dans les versions supérieures à java7, donc si votre JDK est de 6 Si vous passez à la version 7 ou 8, vous devez faire attention à cette exception.

Dans la liste de compatibilité de java7, il y a une description de l'incompatibilité de ce type :

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

J'ai lu dans les informations que java7 a commencé à introduire l'algorithme de tri Timsort . J'ai toujours pensé que la plupart des algorithmes de tri intégrés à la bibliothèque standard étaient des tris rapides. Maintenant, j'ai appris que de nombreux multi-langues utilisent Timsort en interne. Ensuite, j'ai trouvé cette phrase sur Wikipédia :

t a été implémenté par Tim Peters en 2002 pour être utilisé dans le langage de programmation Python.

Ce classement est donc naturellement nommé d'après lui.

Ensuite, j'ai trouvé cette comparaison de tri d'images sur Internet :

On peut constater que Timsort est plus performant que QuickSort.

Ce blog ne discutera pas de l'implémentation de Timsort en détail (il semble que cet algorithme soit assez compliqué). Je pourrais écrire un autre blog pour discuter de Timsort séparément. En termes simples, Timsort combine le tri par fusion et le tri par insertion. Cet algorithme nécessite clairement une augmentation ou une diminution monotone stricte lors de la mise en œuvre pour garantir la stabilité de l'algorithme.

• 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
  

Cela ressemble beaucoup à la symétrie et aux relations transitives des ensembles apprises dans les cours de mathématiques discrètes.

La raison de l'exception est donc que l'algorithme de tri n'est pas assez rigoureux. En fait, le code commercial n'est souvent pas aussi rigoureux que la technologie pure. Par exemple, pour un algorithme comme celui-ci :

Sélectionner le prix le plus bas parmi les vols

Puis si deux prix bas égaux existent en même temps, selon la logique de trouver le prix le plus bas prix, s'il est écrit comme ceci :

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

Alors la position des prix bas est "premier arrivé, premier servi".

Mais si cela est réalisé :

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

Alors les prix bas ultérieurs couvriront les précédents, et cela deviendra un « retardataire vient en premier ». La Programmation rencontre souvent les deux problèmes du premier arrivé, premier servi et du dernier arrivé, premier.

Donc pour celui ci-dessus, il est nécessaire de fournir un jugement rigoureux et une implémentation de la fonction de comparaison de taille. Donc si cela ressemble à ceci :

return x > y ? 1 : -1;

alors cette condition n'est pas remplie.

Mais notre logique est plus compliquée que cela. Il s'agit en fait d'une telle condition de tri. Trier par :

• prix Si les prix sont égaux, celui avec l'heure de départ la plus précoce sera classé en premier.

• Si les horaires de départ sont également égaux, les règles seront les suivantes :

• Non-partagé non-stop>non-stop> non partagé> Les attributs de l'arrêt sont sélectionnés selon la priorité Si ces attributs sont tous égaux, ils ne peuvent être considérés que comme égaux.

Le problème avec cette fonction de jugement est donc :

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;
  }
  }
 }
 }
}

Cette fonction a un problème évident de premier arrivé, premier servi. Par exemple, pour , si ab est les deux S'il s'agit d'un non-stop non partagé, alors a sera classé en premier, mais si compareFlightPrice(a, b) est appelé, b sera classé en premier, il faut donc juger que a est un non-partagé non-stop et b n'est pas un non-stop non partagé, donc a est devant. compareFlightPrice(b, a)

Bien sûr, en plus de changer la fonction de comparaison, il existe une autre solution : ajouter des paramètres de démarrage à la jvm.

-Djava.util.Arrays.useLegacyMergeSort=true

Il convient également de noter que cela ne signifie pas nécessairement qu'il y a des éléments égaux dans votre collection, et que la fonction de comparaison ne répond pas à la définition stricte ci-dessus, cette exception apparaîtra certainement de manière stable. , nous produisons La probabilité que cette exception se produise dans l'environnement est très faible. Après tout, Java n'est pas assez stupide pour vérifier d'abord l'ensemble du tableau. En fait, il constate que vous ne remplissez pas cette condition pendant le processus de tri. Il est donc possible qu'une sorte d'ordre de recouvrement vous permette simplement de contourner ce jugement.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!