我怎樣才能逃避不及時比較器？

我有下面的比較功能Comparator<Foo>：我怎樣才能逃避不及時比較器？

float d = o1.bar - o2.bar; 
if (Math.abs(d) <= 0.001) { 
    return 0; 
} else { 
    return d < 0 ? -1 : 1; // inline Math.copySign 
}

本質上講，這應該是比較基於他們bar等兩項Foo小號除非值足夠接近，在這種情況下，他們應該被宣佈相等。（這很重要，因爲我在此之後做了另一個排序，在不同的屬性上。）

顯然，這不是一個傳遞式比較器。如果有Foo小號f1，f2和f3與作爲1.999，2.000和2.001的bar值，分別的話，按照我的比較，f1==f2和f2==f3但f1 != f3。

調用sort(myListOfFoo, myFooComparator)給出了「比較方法違反其總合約！」錯誤很少，但確定性。

如何在不產生此錯誤的情況下使用Collections.sort(List, Comparator)這種比較器？

另外，有沒有什麼方法可以存儲我的數據，這將允許比較器正常工作？在施工時將每個浮動量調整到最接近的0.001將是最簡單的解決方案，除了Foo.bar字段實際上是基於任意距離度量計算的，所以並不那麼簡單。

實際的代碼是：

float d = metric.distance(vertex, o1) 
     - metric.distance(vertex, o2); 
if (Math.abs(d) < threshold) { 
    return 0; 
} else { 
    return d < 0 ? -1 : 1; // inline Math.copySign 
}

其中o1，o2，和vertex是class Point { float x; float y; }和metric實例是interface DistanceMetric { float distance(Point p1, Point p2); }一個實例。值得注意的是，即使在標準的歐幾里德度量上，這也是失敗的。

來源

2014-02-18 wchargin

您的解決方案也不適用。 Supose threshold = 0.5：2.1被舍入到2.0，2.4被舍入到2.5。按照你的規則，它們應該是平等的，但現在2.1比2.4小。同樣適用於小屋或地板。 – Cristopher

@Cristopher謝謝。這是真的，也是一個好點。但它不起作用的主要原因仍然是因爲這些值是不恆定的。 – wchargin

如果你只是想對'Point'進行排序，閾值的意義何在？你需要在相同的距離去除點，或類似的東西？因爲，否則，您可以使用基於距離的「正常」排序，並且「相同」距離處的所有點將被正確排序，並且將在排序列表中依次排列。 –

恐怕Java 7排序實現不會容忍展現不靈活性的比較器。如果你想使用標準的Java SE排序API，那麼你無能爲力。

但是，實際上，在排序中使用閾值比較實際上在數學上是不正確的。

比較浮點值時的問題是它們往往不準確，並且計算然後通常將進一步的小錯誤引入到結果中。當兩個結果足夠接近時，累積誤差可能會大於這些值之間的差異......這意味着我們無法確定理想數字（沒有錯誤）是否小於，等於或大於每個錯誤。我們通過將「接近平等」視爲「平等」來處理這個問題，通過比較使用閾值。

當我們對值進行排序（即按順序排列）時，值中的錯誤問題需要以不同的方式處理。假設

我們有兩個數字v1 ± e1和v2 ± e2，並且
當我們使用門檻比較比較數字，閾值大於mod(e1) + mod(e2)

如果事實證明， v1和v2已經夠接近了，mod(v1 - v2) < (mod(e1) + mod(e2))然後沒關係如果我們在排序中v2 ± e2之前或之後輸入v1 ± e1。如果我們使用閾值進行比較觀察兩個數字（排序完成後）的順序，他們將顯示爲「平等」，這曾經爲了我們把他們進來。

因此，如果我們忽略的錯誤和只需使用精確比較對數字進行排序，就我們可以看出何時使用基於閾值的比較而言，我們不會將任何一對數字放在不正確的順序中。

現在假設我們有v1 ± e1，v2 ± e2和v3 ± e3 ...和 mod(e1) + mod(e3)是大於我們的門檻：

如果我們爲上述順序（採用精確的比較），我們仍然會結束與數字以正確的順序排列。
如果我們用「與閾值的比較」責令值（和類型的實現允許的！），我們可以在訂單v3 ± e3，v2 ± e2和v1 ± e1與數字結束。我們有{v1 ± e1, v2 ± e2}和{v2 ± e2, v3 ± e3}兩兩相等，但我們也可能有{v1 ± e3, v3 ± e3}錯誤地排序，即使我們使用基於閾值的比較進行比較！

底線是，你應該簡單實現你Comparator（排序的目的！）使用精確的比較。在這種情況下，閾值比較是錯誤的。這適用於sort算法是如何編碼的...

來源

2014-02-18 16:15:48

感謝您的回答和解釋。 – wchargin

我想你真正想要做的是刪除重複值（按你的門檻），然後對其餘的進行排序。爲什麼不先根據非舍入值進行自然排序，然後根據閾值進行過濾。

來源

2014-02-18 13:47:24 Zilvinas

我怎樣才能逃避不及時比較器？

回答

相關問題