Что произойдет, если я поставлю нетранзитивный Comparator в Collections.sort? Можно ли запустить бесконечный цикл?
Небольшой тест, который я написал, дал результат, но я хочу убедиться, что это всегда будет так.
Проблема в том, что в некоторых случаях мой компаратор может создавать циклы, и в этом случае я просто хочу убедиться, что он не будет запущен в бесконечный цикл. Меня не волнует фактический результат.
Java docs говорят, что вы должны убедиться, что ваш компаратор транзитивен. Если вы поставляете компаратор, который не придерживается того, что было запрошено, все ставки отключены. Он может работать для данной реализации, но может ужасно рухнуть (std::sort в С++) в другом.
Короче говоря, вы не должны полагаться на это, даже если это делается для некоторых или других примеров.
Так как Java 7 Collections.sort использует TimSort. Использование нетранзитивного компаратора для сортировки в Java >= 7 приведет к следующему исключению:
java.lang.IllegalArgumentException: Comparison method violates its general contract!
Collections.sort() основан на mergesort.
В объединении есть итерации O (logn) в целом, потому что размер массива ВСЕГДА делится, поэтому sort() должен заканчиваться, несмотря на то, что Компаратор не является транзитивным, поэтому бесконечный цикл не будет возникать.
Тем не менее, нет никаких гарантий по приведенному порядку списка.
Поведение Collections.sort в этом случае зависит от реализации. Реализация Java 6 SE использует комбинацию Mergesort и Insertionsort, которые являются детерминированными с нетранзитивными компараторами, но в Java 7 алгоритм Timsort используется, а другие реализации могут использовать Quicksort или что-то еще, поэтому вы не можете быть уверены, что он будет работать со всеми реализациями.
Прежде всего, я предлагаю вам подумать о сравнении - отношение действительности к сочувствию действительно эквивалентно. Если вы согласны с тем, что это не так, и это должно быть - отслеживать сравниваемые объекты в некоторой локальной переменной. Эта локальная переменная может быть сопоставлена объектами или локальной переменной потока. Эта переменная может представлять собой совокупность пар объектов. Внутри вызова метода сравнения проверьте, была ли эта пара посещена - если это правда, решите, что делать. Но возьмите автомобиль о множестве посещенных объектов - он должен действительно содержать что-то вроде хэша или идентификатора объекта, потому что вы можете пойти в бесконечность другим способом. А также учитывать, что сохранение сравниваемой пары в локальной переменной является потребляемой памятью.