Работает ли сортировка нетранзитивным компаратором?

Question

Что произойдет, если я поставлю нетранзитивный Comparator в Collections.sort?Можно ли запустить бесконечный цикл?

Небольшой тест, который я написал, дал вывод, но я хочу убедиться, что это всегда будет так.

Проблема в том, что в некоторых случаях мойКомпаратор может производить циклы, и в этом случае я просто хочу убедиться, что он не попадет в бесконечный цикл.Мне плевать на фактический результат.

Answer 1

Документы Java говорят, что вы должны убедиться, что ваш компаратор транзитивен.Если вы предоставите компаратор, который не соответствует требованиям, все ставки отменены.Он может работать для данной реализации, но может ужасно зависать (std::sort в C ++ работает) в другой.

Короче говоря, вы не должны полагаться на то, что он работает, даже если он работает для тех или иных примеров.

Answer 2

Поскольку Java 7 Collections.sort использует TimSort.Использование нетранзитивного компаратора для сортировки в Java> = 7 вызовет следующее исключение:

java.lang.IllegalArgumentException: Comparison method violates its general contract!

Answer 3

Collections.sort () основан на mergesort .

. У mergesort всего O (logn) итераций, поскольку размер массива ВСЕГДАразделить, так что sort () должен завершиться, независимо от того, что Comparator не является транзитивным, поэтому бесконечный цикл не произойдет.

Хотя в результирующем порядке List нет никаких гарантий.

Answer 4

Поведение Collections.sort в этом случае зависит от реализации. Реализация Java 6 SE использует комбинацию Mergesort и Insertionsort, которые оба являются детерминированными с нетранзитивными компараторами, но в Java 7 используется алгоритм Timsort, и другие реализации могут использовать Quicksort или что-то еще, так что вы не можете быть уверены, что он будет работать со всеми реализациями.

Answer 5

Прежде всего, я предлагаю вам подумать о сравнении - действительно ли операция сострадания отношение эквивалентности . Если вы принимаете, что это не так и должно быть - отслеживайте сравниваемые объекты в некоторой локальной переменной. Эта локальная переменная может сравнивать объекты или переменную Thread Local. Эта переменная может быть парой сравниваемых объектов. Внутри сравните проверка вызова метода, если эта пара была посещена - если это правда, решите, что делать. Но возьмите машину с множеством посещаемых объектов - она ​​должна действительно содержать что-то вроде хэша или идентификатора объекта, потому что вы можете пойти в бесконечность другим способом. А также учтите, что хранение сравниваемой пары в локальной переменной занимает много памяти.