Как я могу убежать с непереходным компаратором?

Question

У меня есть 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 
} 

По существу, это, как предполагается сравнить два Foo сек в зависимости от их bar имущества, если эти значения не достаточно близки, и в этом случае они должны быть объявлены равными. (Это важно, потому что после этого я делаю другой вид, по другому свойству.)

Очевидно, что это не транзитивный компаратор. Если есть Foo s f1, f2 и f3 со значениями bar как 1.999, 2.000 и 2.001, соответственно, то, по моему компаратор, 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); }. Возможно, стоит отметить, что это не соответствует даже стандартной евклидовой метрике.

Answer 1

Я боюсь, что реализация сортировки Java 7 не будет терпеть компаратора, который проявляет непереходность. Вы ничего не можете с этим сделать ... если вы хотите использовать стандартные API-интерфейсы сортировки Java SE.

---

Но на самом деле использование порогового сравнения в сортировке на самом деле математически неверно.

Проблемы при сравнении значений с плавающей запятой состоят в том, что они часто неточны для начала, а вычисления затем обычно вносят дополнительные небольшие ошибки в результаты. Когда два результата достаточно близки, накопленная ошибка может превышать разницу между значениями ... что означает, что мы не можем определить, являются ли идеальные числа (без ошибок) меньше, равны или больше каждой ошибки. Мы имеем дело с этим, рассматривая «близко к равным» как «равную», сравнивая использование порога.

Когда мы сортируем значения (т. Е. Размещаем их в порядке), вопрос об ошибках в значениях должен обрабатываться по-разному.Предположим, что

• мы имеем два числа v1 ± e1 и v2 ± e2 и

• при сравнении чисел с использованием порогового сравнения, порог больше mod(e1) + mod(e2)

Если выясняется, что v1 и v2 достаточно близки к тому, что mod(v1 - v2) < (mod(e1) + mod(e2)) затем не имеет значения если мы класть v1 ± e1 до или после v2 ± e2 в заказе. Если мы наблюдаем заказы двух чисел (после сортировки), сравнивая их с помощью порога, они будут отображаться как «равные», которые когда-либо заказывали, мы их вставляем.

Так что если мы проигнорировали ошибки и просто упорядочивая числа с использованием точных сравнений, мы не будем вводить какие-либо пары чисел в неверно, насколько мы можем различить, когда мы используем сравнение на основе пороговых значений.

Теперь предположим, что мы имеем v1 ± e1, v2 ± e2 и v3 ± e3 ... и mod(e1) + mod(e3) является GREATER, что наш порог:

• Если мы заказываем, как описано выше (с использованием точного сравнения), мы по-прежнему в конечном итоге с номера в правильном порядке.

• Если бы мы использовали «сравнение с порогами» заказать значение (и реализацию сортировки допускал, что!), Мы могли бы в конечном итоге с числами в порядке v3 ± e3, v2 ± e2 и v1 ± e1. У нас есть {v1 ± e1, v2 ± e2} и {v2 ± e2, v3 ± e3} попарно равны, но мы также могли бы неправильно упорядочить {v1 ± e3, v3 ± e3}, даже если сравнивать с использованием сравнений на основе пороговых значений!

---

Суть заключается в том, что вы должны просто реализовать ваши Comparator (для сортировки целей!) Использовать точные сравнения. Пороговое сравнение неверно для этого контекста. Это применимо независимо от того, как кодируется алгоритм sort ...

Answer 2

Я предполагаю, что вы действительно хотите удалить дубликаты значений (по вашему порогу), а затем отсортировать остальные. Почему бы вам не сделать естественную сортировку сначала на основе не округленных значений, а затем использовать фильтрацию на основе вашего порогового значения.