Как пишется компаратор

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

В 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<DoubleHolder> {
	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 < o.d ? -1 : 0;
}

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

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<DoubleHolder> data = new ArrayList<>();
for(int i=1; i<=10; i++) {
	data.add(new DoubleHolder(i));
}
data.add(new DoubleHolder(Double.NaN));

for(int i=0; i<10; i++) {
	Collections.shuffle(data);
	Collections.sort(data);
	System.out.println(data);
}

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

[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<DoubleHolder> set = new TreeSet<>();
for(int i=0; i<50; i++) {
	set.add(new DoubleHolder( i%10==0 ? Double.NaN : i%10 ));
}
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) {
	return Double.compare(d, o.d);
}

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

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

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

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

public class MyObject implements Comparable<MyObject> {
	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) {
	return ComparisonChain.start()
			.compare(d, o.d)
			.compare(i, o.i)
			.compare(s, o.s)
			.compare(c, o.c)
			.result();
}

В этом посте будет обсуждаться, как сортировать список объектов с помощью Comparator в Java.

А Comparator — это функция сравнения, которая упорядочивает наборы объектов, которые не имеют естественного порядка. Разработчик этого класса должен переопределить абстрактный метод compare() определено в java.util.Comparator, который сравнивает два своих аргумента для порядка. Значение, возвращаемое compare() метод определяет положение первого объекта относительно второго объекта.

 
Есть несколько способов реализовать компараторы в Java:

1. Передайте компаратор в качестве аргумента sort() метод

Компараторы, если они передаются методу сортировки (например, Collections.sort (а также Arrays.sort), позволяют точно контролировать порядок сортировки. В следующем примере мы получаем Comparator что сравнивает Person предметы по возрасту.

Скачать  Выполнить код

результат:

[{name=’Joe’, age=10}, {name=’John’, age=15}, {name=’Will’, age=20}, {name=’Dan’, age=20}, {name=’Sam’, age=25}]

 
С Comparator является функциональным интерфейсом, его можно использовать в качестве цели назначения для лямбда-выражения или ссылки на метод. Следовательно,

можно переписать как:

 
Java 8 представила несколько улучшений для Comparator интерфейс. Теперь Comparator имеет статические методы, такие как comparing(), который может легко создавать компараторы для сравнения некоторых конкретных значений объектов. Например, для получения Comparator что сравнивает Person объектов по их возрасту, мы можем сделать:

 
Приведенный выше код будет сортировать список людей только по age поле. Если два человека имеют одинаковый возраст, их относительный порядок в отсортированном списке не является фиксированным. Таким образом, предпочтительно сравнивать объекты, используя несколько полей, чтобы избежать таких случаев.

Как сравнить объекты с несколькими полями?

1. Мы можем легко отсортировать список людей сначала по age а затем name, как показано ниже. Теперь для лиц одного возраста порядок определяется по имени человека.

Скачать  Выполнить код

 
Обратите внимание, что мы просто уменьшили значение int примитивный тип age друг от друга, а для объекта String встроенный метод сравнения compareTo() используется. Как правило, эта цепочка может продолжаться и дальше, включая и другие свойства.

 
2. Мы также можем сделать это с лямбда-выражениями, используя .thenComparing() метод, который эффективно объединяет два сравнения в одно:

Скачать  Выполнить код

 
3. Мы также можем использовать Guava ComparisonChain для выполнения оператора цепного сравнения, как показано ниже:

Скачать код

 
Возвращаемое значение compare() будет иметь тот же знак, что и первый ненулевой результат сравнения в цепочке, или будет равен нулю, если все результаты сравнения были равны нулю. Обратите внимание, что ComparisonChain прекращает вызывать свои входы compareTo а также compare методы, как только один из них возвращает ненулевой результат.

 
4. Мы также можем использовать CompareToBuilder класса библиотеки Apache Commons Lang, чтобы помочь в реализации Comparator.compare() метод. Чтобы использовать этот класс, напишите следующий код:

Скачать код

 
Значения сравниваются в том порядке, в котором они добавляются к построителю. Если какое-либо сравнение возвращает ненулевой результат, то это значение будет возвращено функцией toComparison(), и все последующие сравнения пропускаются.

Мы можем даже реализовать Comparator в отдельный класс, а затем передать экземпляр этого класса в sort() метод. Это показано ниже:

Скачать  Выполнить код

результат:

[{name=’Joe’, age=10}, {name=’John’, age=15}, {name=’Dan’, age=20}, {name=’Will’, age=20}, {name=’Sam’, age=25}]

3. Передать компаратор в List.sort() метод

Java 8 представила несколько улучшений для List интерфейс. В настоящее время List имеет собственный метод сортировки sort() который сортирует список в соответствии с порядком, индуцированным указанным Comparator. Это показано ниже:

Скачать  Выполнить код

результат:

[{name=’Joe’, age=10}, {name=’John’, age=15}, {name=’Dan’, age=20}, {name=’Will’, age=20}, {name=’Sam’, age=25}]

4. Передать компаратор в Stream.sorted() метод

Мы также можем передать наш компаратор в sorted() метод Stream класс, который возвращает поток, состоящий из элементов этого потока, отсортированных в соответствии с предоставленным Comparator. Вот рабочий пример:

Скачать  Выполнить код

результат:

[{name=’Joe’, age=10}, {name=’John’, age=15}, {name=’Dan’, age=20}, {name=’Will’, age=20}, {name=’Sam’, age=25}]

Это все, что касается сортировки списка объектов с помощью Comparator в Java.

 
Продолжить чтение:

Сортировка списка объектов с помощью Comparable в Java

Привет, дорогие читатели! Этот урок посвящен встроенной сортировке C++ и ее учителю — компаратору.

• sort для вектора
• sort для списка
• sort для массива
• Что такое компаратор

Что такое функция sort

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

Принцип работы построен на алгоритме быстрой сортировки (quicksort), так что за быстроту можно не волноваться.

Также в C++ имеется другая сортировка — qsort, но она работает значительно медленнее текущей.

Чтобы нам оперировать данной функцией понадобится для начала подключить библиотеку — <algorithm>.

Многие языки не могут похвастаться такой гибкостью. Например, Pascal, там придется самостоятельно писать алгоритм сортировки (который составляет несколько десятков строк !).

Функция sort для вектора

Вот как выглядит конструкция вызова:

• <начало> — здесь мы должны указать стартовую точку сортировки, необязательно это должно быть начало.
• <конец> — тут аналогично, только уже указываем конец.
• <компаратор> —  его использовать в аргументах функции не обязательно. Подробнее о нем мы поговорим ниже.

• В строках 14 — 17: добавляем элементы в вектор vec.
• В строке 25: сортируем последовательность.
• В строке 32: нашей стартовой точкой стала n / 2, а также мы применили компаратор, из-за которого смогли поменять сторону сортировки (по не возрастанию). vec.begin() + n / 2 — так прибавлять к итератору можно только для вектора и массива, для других контейнеров нельзя. Подробнее почитайте про итераторы здесь.

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

Функция sort для списка

Для списка list, функция sort() превращается в префиксный метод:

Функция sort для массива (array)

Чтобы отсортировать массив нам нужно использовать схему ниже:

Имя массива указывает на первую ячейку —[0].

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

Так, например можно:

• Отсортировать только первую половину массива, если укажем (... , <имя массива> + n / 2) (n — размер массива).
• Или начать сортировку со второй ячейки (<имя массива> + 2, ...).

Что такое компаратор

Компаратор — это функция, которая как бы учит сортировать sort. Так например можно сортировать по:

• Кратности на 3.
• Четности или нечетности.
• Изменить сторону сортировки на — по убыванию.

sort передает элементы компаратору, а компаратор проверяет их по вашему алгоритму и передает true или false.

Обычно его используют когда имеется например — vector < vector <pair <int, int> > >  vec и нужно отсортировать вектора по второму элементу первой ячейки (vec[i][0].second).

Как создать компаратор

Самого начала создаём функцию, которая и будет компаратором.

1. <первый и второй аргумент> — здесь нужно быть аккуратным, потому что если мы укажем неправильно аргументы — никакая сортировка не произойдет.
2. return — эта строчка является основной в этом коде, так как именно она изменяет сортировку.

В аргументах нужно всего лишь указать имя компаратора.

Как правильно создавать компаратор чтобы он работал

Чтобы правильно создать компаратор нужно знать это:

1. Когда вызывается компаратор ему передается тип сортируемого объекта.

Давайте разберем пример, который был выше — vector < vector < pair <int, int> > >. Для него этим типом будет — vector < pair <int, int> >.

Этот компаратор будет сортировать вектора по второму элементу первой ячейки (по неубыванию).

Для массивов «типом сортируемого объекта» и будет тип массива. Например pair <int, int> p[20] -> ... (pair <int, int> a, ...) {

По неубыванию означает, что элемент arr[i] может быть равным arr[i — 1] (а по убыванию означает что каждый последующий элемент будет меньше предыдущего). Тоже самое с сортировкой по невозрастанию.

компаратор

Синонимы:

Стандартная сортировка

Функция sort по умолчанию приводит элементы массива к строкам, а затем сортирует.

[1,-8,90,32,0,0,5,92,900].sort()
// [-8, 0, 0, 1, 32, 5, 90, 900, 92]

Если массив состоит из чисел, то такое поведение является нежелательным.

Использование компаратора

Функция sort может принимать аргумент — компаратор.

Компаратор — это функция, которая принимает 2 аргумента и возвращает отрицательное число, если первый меньше, положительное, если второй меньше и 0, если они равны.

Для чисел достаточно распространено использование вычитания в качестве компаратора:

[1,-8,90,32,0,0,5,92,900].sort(function(a, b) {
  return a-b;
})
// [-8, 0, 0, 1, 5, 32, 90, 92, 900]

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

Компаратор на основе сравнения

Можно вспомнить, что во многих языках true приводится к 1, а false — к 0.

Воспользуемся этой возможностью. Только одно из условий a<b и b<a истинно, поэтому разность (b<a) - (a<b) замечательно подходит на роль компаратора:

[1,-8,90,32,0,0,5,92,900].sort(function(a, b) {
  return (b<a) - (a<b);
})
// [-8, 0, 0, 1, 5, 32, 90, 92, 900]

Какие тут плюсы? Помимо невозможности переполнения, такое сравнение можно использовать не только с числами. Например, строки вычитать мы не можем, а сравнивать можем.

Для сортировки по убыванию надо просто поменять сравнения местами:

[1,-8,90,32,0,0,5,92,900].sort(function(a, b) {
  return (a<b) - (b<a);
})
// [900, 92, 90, 32, 5, 1, 0, 0, -8]

Сортировка по нескольким полям

При сравнении по нескольким полям требуется, чтобы следующее поле сравнивалось только когда предыдущие равны. Это значит, что часть компаратора, выполняющая сравнение тех полей при вычислении даёт 0.

Таким образом, для объединения сравнений полей замечательно подходит оператор ||, возвращающий первое истинное (в нашем случае ненулевое) значение, либо самое последнее (в нашем случае 0), если все ложны. Таким способом можно объединить любое количество полей.

Отсортируем массив по имени и id:

[{name:"John", id:7}, {name:"John",id:4}, {name:"Adam",id:3}, {name:"Adam",id:30}, {name:"Rose",id:1}].sort(function(a, b) {
  return (b.name<a.name) - (a.name<b.name) || (b.id<a.id) - (a.id<b.id);
})
// [{"name":"Adam","id":3},{"name":"Adam","id":30},{"name":"John","id":4},{"name":"John","id":7},{"name":"Rose","id":1}]