前言

上周線上的一段排序的java代碼出現(xiàn)了一個(gè)Comparison method violates its general contract，在解決這個(gè)問題的途中學(xué)到了一些知識(shí)這里總結(jié)分享一下。

異常原因

這個(gè)排序?qū)е碌漠惓?huì)在java7以上的版本出現(xiàn)，所以如果你的JDK從6升級(jí)到了7或者8，那一定要小心此異常。

在java7的兼容列表中，就有對(duì)此排序不兼容的說明：

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(luò)ava7開始引入了Timsort的排序算法。我之前一直以為大部分標(biāo)準(zhǔn)庫的內(nèi)置排序算法都是快速排序?，F(xiàn)在才得知很多語言內(nèi)部都使用Timsort排序。隨后我在wiki百科上找到了這樣一句話：

t was implemented by Tim Peters in 2002 for use in the Python programming language.

所以這個(gè)排序自然是以他命名的。

隨后我又在網(wǎng)上找到了這樣一張圖排序比較的圖：

可以發(fā)現(xiàn)，Timsort在表現(xiàn)上比QuickSort還要好。

這篇博客不去詳細(xì)討論Timsort的實(shí)現(xiàn)（看上去這個(gè)算法還挺復(fù)雜的），我可能會(huì)寫另一篇博客單獨(dú)討論Timsort，簡(jiǎn)單來說Timsort結(jié)合了歸并排序和插入排序。這個(gè)算法在實(shí)現(xiàn)過程中明確需要：嚴(yán)格的單調(diào)遞增或者遞減來保證算法的穩(wěn)定性。

• 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
  

看上去很像離散數(shù)學(xué)課中學(xué)習(xí)的集合的對(duì)稱性，傳遞性的關(guān)系。

所以異常的原因是因?yàn)榕判蛩惴ú粔驀?yán)謹(jǐn)導(dǎo)致的，實(shí)際上業(yè)務(wù)上的代碼經(jīng)常不如純技術(shù)上的嚴(yán)謹(jǐn)。比如對(duì)于這樣一個(gè)算法：

選出航班中的最低價(jià)

那如果兩個(gè)相等低價(jià)同時(shí)存在，按照尋找最低價(jià)的邏輯如果這么寫：

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

那低價(jià)這個(gè)位置就是“先到先得”了。

但如果這么實(shí)現(xiàn):

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

那后面的低價(jià)就會(huì)覆蓋前面的，變成了“后來者居上”。編程中經(jīng)常遇到先到先得和后來者居上這兩個(gè)問題。

所以對(duì)于上面那個(gè)需要提供嚴(yán)謹(jǐn)?shù)呐袛啻笮”容^函數(shù)實(shí)現(xiàn)。所以如果是這樣的：

return x > y ? 1 : -1;

那么就不符合此條件。

不過我們邏輯要比這個(gè)復(fù)雜，其實(shí)是這樣一個(gè)排序條件。按照：

• 價(jià)格進(jìn)行排序，如果價(jià)格相等則起飛時(shí)間靠前的先排。
• 如果起飛時(shí)間也相等，就會(huì)按照：
• 非共享非經(jīng)停>非經(jīng)停>非共享>經(jīng)停的屬性進(jìn)行優(yōu)先級(jí)選擇，如果這些屬性都全部相等，才只能算是相等了。

所以這個(gè)判斷函數(shù)的問題是：

public compareFlightPrice(flightPrice o1, flightPrice o2){
 // 非經(jīng)停非共享
 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;
  }
  }
 }
 }
}

這個(gè)函數(shù)有明顯的先到先得的問題，比如對(duì)于compareFlightPrice(a, b) ，如果ab都是非共享非經(jīng)停，那么這個(gè)就會(huì)把a(bǔ)排到前面，但如果調(diào)用compareFlightPrice(b, a) ，b又會(huì)排到前面，所以必須判斷a是非共享非經(jīng)停且b不是非共享非經(jīng)停，才能讓a排在前面。

當(dāng)然除了改比較函數(shù)，還有一個(gè)解決方式是：給jvm添加啟動(dòng)參數(shù)。

-Djava.util.Arrays.useLegacyMergeSort=true

還需要注意的是，并不一定你的集合中存在相等的元素，并且比較函數(shù)不符合上面的嚴(yán)謹(jǐn)定義，就一定會(huì)穩(wěn)定浮現(xiàn)此異常，實(shí)際上我們?cè)谏a(chǎn)環(huán)境出現(xiàn)此異常的概率很小，畢竟java并不會(huì)蠢到先去把整個(gè)數(shù)組都校驗(yàn)一遍，實(shí)際上它是在排序的過程中發(fā)現(xiàn)你不符合此條件的。所以有可能某種集合順序讓你剛好繞過了此判斷。

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來一定的幫助，如果有疑問大家可以留言交流，謝謝大家對(duì)腳本之家的支持。

最新評(píng)論