Compareto c как работает

Пишите компараторы правильно

В Java для введения порядка среди определённых объектов можно написать компаратор — класс, содержащий функцию compare , которая сравнивает два объекта. Альтернативой компаратору является естественный порядок объектов: объект реализует интерфейс Comparable , который содержит метод compareTo , позволяющий сравнить этот объект с другим. Сравнивающая функция должна вернуть 0, если объекты равны, отрицательное число (обычно -1), если первый объект меньше второго, и положительное число (обычно 1), если первый больше. Обычно реализация такой функции не представляет сложностей, но имеется один случай, о котором многие забывают.

Сравнение используется различными алгоритмами от сортировки и двоичного поиска до поддержания порядка в сортированных коллекциях вроде TreeMap . Эти алгоритмы завязаны на три важных свойства сравнивающей функции: рефлексивность (сравнение элемента с самим собой всегда даёт 0), антисимметричность (сравнение A с B и B с A должны дать разный знак) и транзитивность (если сравнение A с B и B с C выдаёт одинаковый знак, то и сравнение A с C должно выдать такой же). Если сравнивающая функция не удовлетворяет этим свойствам, алгоритм может выдать совершенно непредсказуемый результат. Причём скорее всего вы не получите никакого исключения, просто результат будет неверный.

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

Предположим, у нас имеется класс с полем типа double, и мы хотим упорядочивать объекты этого класса в зависимости от значения поля. Нередко можно встретить такой код:

public class DoubleHolder implements Comparable  < double d; public DoubleHolder(double d) < this.d = d; >@Override public int compareTo(DoubleHolder o) < return d >o.d ? 1 : d == o.d ? 0 : -1; > @Override public String toString() < return String.valueOf(d); >>

У приведённого метода compareTo есть две проблемы. Первая — незначительная — он не различает +0.0 и -0.0: new DoubleHolder(-0.0).compareTo(new DoubleHolder(+0.0)) вернёт 0. Иногда это нестрашно, но в случае сортировки элементы с +0.0 и -0.0 расположатся в произвольном порядке, что будет смотреться некрасиво. Тем не менее, всё это мелочи по сравнению с NaN. Число NaN (как в типе double, так и во float) — это довольно специфичная вещь. Оно не больше, не меньше и не равно никакому другому числу. В результате мы сразу получаем нарушение свойств сравнения:

DoubleHolder nan = new DoubleHolder(Double.NaN); DoubleHolder zero = new DoubleHolder(0.0); System.out.println("nan.compareTo(nan): "+nan.compareTo(nan)); System.out.println("nan.compareTo(zero): "+nan.compareTo(zero)); System.out.println("zero.compareTo(nan): "+zero.compareTo(nan));

nan.compareTo(nan): -1 nan.compareTo(zero): -1 zero.compareTo(nan): -1

Ни рефлексивности, ни антисимметричности не наблюдается. Можно встретить и такую реализацию сравнения:

public int compareTo(DoubleHolder o) < return d >o.d ? 1 : d

Здесь все три предыдущих сравнения выдадут ноль, то есть как будто бы свойства соблюдаются. Но, конечно, радоваться рано:

DoubleHolder nan = new DoubleHolder(Double.NaN); DoubleHolder zero = new DoubleHolder(0.0); DoubleHolder one = new DoubleHolder(1.0); System.out.println("zero.compareTo(nan): "+zero.compareTo(nan)); System.out.println("nan.compareTo(one): "+nan.compareTo(one)); System.out.println("zero.compareTo(one): "+zero.compareTo(one)); 

zero.compareTo(nan): 0 nan.compareTo(one): 0 zero.compareTo(one): -1

Здесь нарушается транзитивность: первый объект равен второму, второй равен третьему, но первый третьему не равен.

Чем же это грозит простому обывателю? Чтобы понять это, создадим простой список и попробуем его перемешать и посортировать несколько раз:

List data = new ArrayList<>(); for(int i=1; i data.add(new DoubleHolder(Double.NaN)); for(int i=0; i

Вывод в каждом запуске отличается и может выглядеть, например, так:

[NaN, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [NaN, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [1.0, NaN, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [NaN, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, NaN] [2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, NaN, 1.0, 9.0, 10.0] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 10.0, NaN, 9.0] [NaN, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [NaN, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [1.0, NaN, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0]

Или для второй реализации compareTo :

[1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 8.0, 9.0, NaN, 7.0, 10.0] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, NaN] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, NaN] [1.0, 2.0, 9.0, 10.0, NaN, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, NaN] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, NaN] [2.0, 6.0, NaN, 1.0, 3.0, 4.0, 5.0, 7.0, 8.0, 9.0, 10.0] [2.0, 4.0, NaN, 1.0, 3.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [1.0, 3.0, NaN, 2.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, NaN]

Примерно в половине случаев элемент с NaN прибивается к началу или концу сортируемого списка, а в других случаях начинает блуждать, портя порядок окружающих элементов.

С коллекциями, использующими DoubleHolder в качестве ключа, тоже ничего хорошего не произойдёт. Возьмём, к примеру, TreeSet . Со второй реализацией compareTo всё довольно просто: так как элемент, содержащий NaN, равен любому другому, то в непустое множество вставить его не получится, потому что оно решит, что такой элемент уже есть. Но берегитесь, если вы вставили NaN-элемент первым: после этого во множество не выйдет добавить ничего другого.

Первый вариант сравнивающей функции психоделичнее. Напишем, например, такой тест:

Set set = new TreeSet<>(); for(int i=0; i System.out.println(set);

Мы вставили по пять элементов, содержащих NaN, и по пять элементов, содержащих каждую цифру от 1 до 9. В результате имеем следующее:

[NaN, NaN, 1.0, 2.0, 3.0, NaN, NaN, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, NaN]

Вполне ожидаемо увидеть пять раз NaN: ведь они не равны друг другу. Но из-за неправильных сравнений и некоторые другие элементы вставились по нескольку раз. Можете сами посмотреть, что случится с TreeMap. Заметьте, что один случайно попавший NaN может испортить всю коллекцию, причём это не всегда легко отладить: коллекция может долго существовать в некорректном состоянии и делать вид, что всё нормально.

Что любопытно, этой проблемы вообще не должно существовать. Ещё в JDK 1.4 появились специальные статические методы Float.compare и Double.compare, которые сделают всё за вас, корректно обработав специальные случаи. Надо лишь написать:

public int compareTo(DoubleHolder o)

Видимо, сказывается обманчивая простота алгоритма сравнения: порой программист считает, что проще написать самому, чем искать в документации стандартный способ сделать это.

Примеры неправильного сравнения double/float в различных открытых проектах: JTS, Batik, Hadoop, Hudson, ICU4J, Lucene. Трудно определить, в каких случаях это может привести к проблемам, но это тот случай, когда я бы исправлял безусловно: правильный и надёжный вариант обычно при этом ещё и короче неправильного.

Чтобы изменить ситуацию, я написал маленький детектор для FindBugs, который находит некорректно реализованные функции сравнения и предлагает использовать Float.compare/Double.compare.

Вообще для всех примитивных типов есть подобные методы. Если вам надо сравнить несколько полей по очереди, можно написать так:

public class MyObject implements Comparable  < double d; int i; String s; char c; @Override public int compareTo(MyObject o) < int result; result = Double.compare(d, o.d); if(result != 0) return result; result = Integer.compare(i, o.i); if(result != 0) return result; result = s.compareTo(o.s); if(result != 0) return result; result = Character.compare(c, o.c); return result; >>

Смотрится лучше, чем куча веток с больше и меньше. А если вы пользуетесь Guava или чем-то подобным, тогда так:

@Override public int compareTo(MyObject o)

Объясните как работает compare() в порядке возрастания и убывания

Почему если в методе compare() возвращать return aStr.compareTo(bStr); то коллекция будет сортироваться в порядке возрастания, а если return bStr.compareTo(aStr); , то в порядке убывания?

Отслеживать
задан 20 авг 2021 в 20:09
teoretik_eugene teoretik_eugene
59 4 4 бронзовых знака

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Потому что упрощено говоря aStr.compareTo(bStr) равно -bStr.compareTo(aStr). Т.е. если aStr.compareTo(bStr) возвращает 1, то bStr.compareTo(aStr) вернёт -1. Поэтому и сортировка производится в обратную сторону.

Пример на числах: допустим в функцию сравнения (не эту, но похожую) передается два числа a и b. Если функция возвращает 1, то мы первое число ставим перед вторым. Если же -1, то второе перед первым. В одном случае получится возрастающая сортировка, в другом убывающая.

Отслеживать
ответ дан 20 авг 2021 в 20:15
26.2k 7 7 золотых знаков 31 31 серебряный знак 48 48 бронзовых знаков

Т.е., если у нас значение будет >0, то сортировка будет производиться в порядке возрастания, если же < 0 - то наоборот?

20 авг 2021 в 20:28
Вообще не совсем так, но для простоты пусть будет так.
20 авг 2021 в 20:31

Метод compareTo() уже и сравнивает, какая из строк «больше». А как этот результат дальше применяется из этого кода не видно.

Compareto c как работает

Большинство встроенных в .NET классов коллекций и массивы поддерживают сортировку. С помощью одного метода, который, как правило, называется Sort() можно сразу отсортировать по возрастанию весь набор данных. Например:

int[] numbers = new int[] < 97, 45, 32, 65, 83, 23, 15 >; Array.Sort(numbers); foreach (int n in numbers) Console.WriteLine(n); // 15 23 32 45 65 83 97

Однако метод Sort по умолчанию работает только для наборов примитивных типов, как int или string. Для сортировки наборов сложных объектов применяется интерфейс IComparable . Он имеет всего один метод:

public interface IComparable

Метод CompareTo предназначен для сравнения текущего объекта с объектом, который передается в качестве параметра object? o . На выходе он возвращает целое число, которое может иметь одно из трех значений:

• Меньше нуля. Значит, текущий объект должен находиться перед объектом, который передается в качестве параметра
• Равен нулю. Значит, оба объекта равны
• Больше нуля. Значит, текущий объект должен находиться после объекта, передаваемого в качестве параметра

Например, имеется класс Person:

class Person : IComparable < public string Name < get;>public int Age < get; set; >public Person(string name, int age) < Name = name; Age = age; >public int CompareTo(object? o) < if(o is Person person) return Name.CompareTo(person.Name); else throw new ArgumentException("Некорректное значение параметра"); >>

Здесь в качестве критерия сравнения выбрано свойство Name объекта Person. Поэтому при сравнении здесь фактически идет сравнение значения свойства Name текущего объекта и свойства Name объекта, переданного через параметр. Если вдруг объект не удастся привести к типу Person, то выбрасывается исключение.

var tom = new Person("Tom", 37); var bob = new Person("Bob", 41); var sam = new Person("Sam", 25); Person[] people = < tom, bob, sam>; Array.Sort(people); foreach (Person person in people) < Console.WriteLine($"- "); >

И в данном случае мы получим следующий консольный вывод:

Bob - 41 Sam - 25 Tom - 37

Интерфейс IComparable имеет обобщенную версию, поэтому мы могли бы сократить и упростить его применение в классе Person:

class Person : IComparable  < public string Name < get;>public int Age < get; set; >public Person(string name, int age) < Name = name; Age = age; >public int CompareTo(Person? person) < if(person is null) throw new ArgumentException("Некорректное значение параметра"); return Name.CompareTo(person.Name); >>

Аналогичным образом мы можем сравнивать по возрасту:

class Person : IComparable  < public string Name < get;>public int Age < get; set; >public Person(string name, int age) < Name = name; Age = age; >public int CompareTo(Person? person) < if(person is null) throw new ArgumentException("Некорректное значение параметра"); return Age - person.Age; >>

Применение компаратора

Кроме интерфейса IComparable платформа .NET также предоставляет интерфейс IComparer:

public interface IComparer

Метод Compare предназначен для сравнения двух объектов o1 и o2. Он также возвращает три значения, в зависимости от результата сравнения: если первый объект больше второго, то возвращается число больше 0, если меньше — то число меньше нуля; если оба объекта равны, возвращается ноль.

Создадим компаратор объектов Person. Пусть он сравнивает объекты в зависимости от длины строки — значения свойства Name:

class PeopleComparer : IComparer  < public int Compare(Person? p1, Person? p2) < if(p1 is null || p2 is null) throw new ArgumentException("Некорректное значение параметра"); return p1.Name.Length - p2.Name.Length; >> class Person < public string Name < get;>public int Age < get; set; >public Person(string name, int age) < Name = name; Age = age; >>

В данном случае используется обобщенная версия интерфейса IComparer, чтобы не делать излишних преобразований типов. Применение компаратора:

var alice = new Person("Alice", 41); var tom = new Person("Tom", 37); var kate = new Person("Kate", 25); Person[] people = < alice, tom, kate>; Array.Sort(people, new PeopleComparer()); foreach (Person person in people) < Console.WriteLine($"- "); >

Объект компаратора указывается в качестве второго параметра метода Array.Sort() . При этом не важно, реализует ли класс Person интерфейс IComparable или нет. Правила сортировки, установленные компаратором, будут иметь больший приоритет. В начале будут идти объекты Person, у которых имена меньше, а в конце — у которых имена длиннее:

Tom - 37 Kate - 25 Alice - 41

Compareto c как работает

Денис Уровень 23

17 февраля 2022

Нужно пояснение.

 public int compareTo(User o) < int result = this.name.compareTo(o.name); //если имена одинаковые - сравниваем возраст, используя метод compareTo из класса Integer if (result == 0) < result = this.age.compareTo(o.age); //сравнили возраст, получили какой-то результат >return result; //вернули результат в compareTo, а дальше то что? > 

Что происходит дальше после возвращения результата в compareTo, какой дальнейший алгоритм сортировки?

Wiun Уровень 16

30 марта 2021

не совсем понимаю, что такое

 //используем метод compareTo из класса String для сравнения имен int result = this.name.compareTo(o.name); 

мы сравниваем переменную name из класса с какой переменной name? какое имя будет подставляться в аргумент «о»? и дальше. мы метод compareTo нигде не вызываем, а пользуемся Collections.sort так зачем мы его описывали и переопределяли?

Viktor Korotkov Уровень 23