Что такое компаратор в java
Comparable и Comparator
Два новых интерфейса java.lang.Comparable и java.util.Comparator были добавлены в версии Java 5. Использование данных интерфейcов в своих приложениях позволяет упорядочивать (сортировать) данные.
Интерфейс Comparable
В интерфейсе Comparable объявлен только один метод compareTo (Object obj), предназначенный для упорядочивания объектов класса. Данный метод удобно использовать для сортировки списков или массивов объектов.
Метод compareTo (Object obj) сравнивает вызываемый объект с obj. В отличие от метода equals, который возвращает true или false, compareTo возвращает:
Если типы объектов не совместимы при сравнении, то compareTo (Object obj) может вызвать исключение ClassCastException. Необходимо помнить, что аргумент метода compareTo имеет тип сравниваемого объекта класса.
Обычные классы Byte, Short, Integer, Long, Double, Float, Character, String уже реализуют интерфейс Comparable.
Пример реализации интерфейса Comparable
Результат выполнения программы:
В примере значения сортируются сначала по полю str (по алфавиту), а затем по num в методе compareTo. Это хорошо видно по двум строкам с одинаковыми значения str и различными num. Чтобы изменить порядок сортировки значения str (в обратном порядке), необходимо внести небольшие изменения в метод compareTo.
Интерфейс Comparator : compare, compareTo
В интерфейсе Comparator объявлен метод compare (Object obj1, Object obj2), который позволяет сравнивать между собой два объекта. На выходе метод возвращает значение 0, если объекты равны, положительное значение или отрицательное значение, если объекты не тождественны.
Метод может вызвать исключение ClassCastException, если типы объектов не совместимы при сравнении. Простой пример реализации интерфейса Comparator:
Результат выполнения программы:
Усложним пример, и реализуем несколько видов сортировки. Для этого создадим класс Product с полями name, price и quantity.
Создадим два класса (SortedByName, SortedByPrice), реализующих интерфейс Comparator для сортировки объектов по названию и по цене :
Пример использования Arrays.sort :
Результат выполнения программы:
Для сортировки объектов были реализованы два независимых компаратора по наименованию и по цене (SortedByName и SortedByPrice). Сортировка выполняется с помощью класса Arrays, у которого есть метод sort. Данный метод в качестве второго аргумента принимает тип компаратора.
Можно использовать также метод sort класса Collections, который в качестве первого входного аргумента принимает список объектов:
Отличие интерфейсов Comparator и Comparable
Интерфейс Comparable используется только для сравнения объектов класса, в котором данный интерфейс реализован. Т.е. interface Comparable определяет логику сравнения объекта определенного ссылочного типа внутри своей реализации (по правилам разработчика).
Comparator представляет отдельную реализацию и ее можно использовать многократно и с различными классами. Т.е. interface Comparator позволяет создавать объекты, которые будут управлять процессом сравнения (например при сортировках).
Пишите компараторы правильно
Как обнаружилось, несоблюдение этих свойств — не такая уж редкая ситуация. Проблема возникает при сравнении вещественных чисел — float или double.
Предположим, у нас имеется класс с полем типа double, и мы хотим упорядочивать объекты этого класса в зависимости от значения поля. Нередко можно встретить такой код:
Ни рефлексивности, ни антисимметричности не наблюдается. Можно встретить и такую реализацию сравнения:
Здесь все три предыдущих сравнения выдадут ноль, то есть как будто бы свойства соблюдаются. Но, конечно, радоваться рано:
Здесь нарушается транзитивность: первый объект равен второму, второй равен третьему, но первый третьему не равен.
Чем же это грозит простому обывателю? Чтобы понять это, создадим простой список и попробуем его перемешать и посортировать несколько раз:
Вывод в каждом запуске отличается и может выглядеть, например, так:
Или для второй реализации compareTo :
Примерно в половине случаев элемент с NaN прибивается к началу или концу сортируемого списка, а в других случаях начинает блуждать, портя порядок окружающих элементов.
Первый вариант сравнивающей функции психоделичнее. Напишем, например, такой тест:
Мы вставили по пять элементов, содержащих NaN, и по пять элементов, содержащих каждую цифру от 1 до 9. В результате имеем следующее:
Вполне ожидаемо увидеть пять раз NaN: ведь они не равны друг другу. Но из-за неправильных сравнений и некоторые другие элементы вставились по нескольку раз. Можете сами посмотреть, что случится с TreeMap. Заметьте, что один случайно попавший NaN может испортить всю коллекцию, причём это не всегда легко отладить: коллекция может долго существовать в некорректном состоянии и делать вид, что всё нормально.
Что любопытно, этой проблемы вообще не должно существовать. Ещё в JDK 1.4 появились специальные статические методы Float.compare и Double.compare, которые сделают всё за вас, корректно обработав специальные случаи. Надо лишь написать:
Видимо, сказывается обманчивая простота алгоритма сравнения: порой программист считает, что проще написать самому, чем искать в документации стандартный способ сделать это.
Примеры неправильного сравнения double/float в различных открытых проектах: JTS, Batik, Hadoop, Hudson, ICU4J, Lucene. Трудно определить, в каких случаях это может привести к проблемам, но это тот случай, когда я бы исправлял безусловно: правильный и надёжный вариант обычно при этом ещё и короче неправильного.
Чтобы изменить ситуацию, я написал маленький детектор для FindBugs, который находит некорректно реализованные функции сравнения и предлагает использовать Float.compare/Double.compare.
Вообще для всех примитивных типов есть подобные методы. Если вам надо сравнить несколько полей по очереди, можно написать так:
Смотрится лучше, чем куча веток с больше и меньше. А если вы пользуетесь Guava или чем-то подобным, тогда так:
Comparator, сортировка коллекций
— Сегодня будет небольшая, но интересная и полезная тема – сортировки коллекций.
— Сортировка? Я что-то про это слышал.
— Давным-давно каждый программист обязан был уметь писать сортировку. Умел и писал. Но те времена канули в лету. Сегодня написание своей сортировки считается дурным тоном, как и написание всего, что уже было придумано.
В Java (да и других языках программирования) сортировки уже реализованы. Твоя задача – научиться правильно пользоваться тем, что есть.
— У вспомогательного класса Collections есть статический метод sort, который используется для сортировки коллекций, а если точнее – списков. Элементы в коллекциях Map и Set не имеют порядка/номера, значит, и сортировать там нечего.
— Да, я вспомнил, я когда-то уже использовал этот метод для сортировки списка чисел.
— Отлично. Но этот метод гораздо мощнее чем, кажется на первый взгляд. Он может сортировать не только числа, но и любые объекты, по любым критериям. И помогают ему в этом два интерфейса: Comparable и Comparator.
Иногда бывает нужно отсортировать объекты, а не числа. Например, у тебя есть список людей, и ты хочешь отсортировать их по возрасту. Для этого есть интерфейс Comparable.
Давай я сначала покажу тебе пример, и все станет понятнее:
Чтобы объекты можно было сортировать, сначала нужно научиться их сравнивать. Для этого и используется Comparable. Интерфейс Comparable является generic’ом – т.е. типом с параметром. У него всего один generic-метод – compareTo(T o). В этом методе и происходит сравнение переданного объекта (o) и текущего (this). Т.е. надо переопределить этот метод в своем классе и сравнить в нем текущий объект (this) с переданным.
— А как работает compareTo? Я думал, что он будет возвращать true/false в зависимости от того – больше переданный объект или меньше.
— Тут все немного хитрее. Метод compareTo возвращает не true/false, а значение типа int. На самом деле так сделано для простоты.
Когда компьютеру нужно определить больше ли одно число, чем другое, он просто вычитает из первого числа второе, а потом смотрит, что получилось. Если 0 – числа равны, если получилось число меньше нуля, то второе число больше, а если результат больше нуля, то больше уже первое число.
Тут используется та же логика. Согласно спецификации метод compareTo должен вернуть ноль, если сравниваемые объекты равны. Если метод compareTo вернул число больше нуля, это значит, что наш (this) объект больше, чем переданный. Если метод compareTo вернул число меньше нуля, то объект this меньше чем переданный.
— Да, но если ты сравниваешь объекты просто по какому-то параметру-числу, то можешь просто вернуть разницу между ними – вычесть один из другого. Как это и сделано в примере выше.
— Вроде все понятно. Хотя может и не все. Но почти все.
— Отлично. Теперь рассмотрим более практическую задачу. Ты написал крутой сайт по пошиву женской одежды в Китае. Для описания своих пользователей ты используешь класс Woman. Ты даже сделал страницу с таблицей, где можешь посмотреть их всех. Но есть проблема…
Объект Woman содержит у тебя не только возраст, а еще целую кучу данных: имя, фамилию, рост, вес, количество детей, …
В таблице пользователей есть много колонок, и тут встает вопрос: а как сортировать пользователей по разным критериям? По весу, по возрасту, по фамилии?
— Гм. Действительно, часто вижу таблицы с сортировкой колонок. И как это сделать?
— А для этого есть второй интерфейс, о котором я хотел тебе сегодня рассказать – это интерфейс Comparator. И у него тоже есть метод сравнения, только он называется compare и принимает не один параметр, а два: int compare(T o1, T o2). Вот как это работает:
При использовании интерфейса Comparator, логика сравнения пары объектов не прячется внутрь класса/объекта, а реализуется в отдельном классе.
— Т.е. я могу сделать несколько классов, реализующих интерфейс Comparator, но в каждом из них сравнивать разные параметры? В одном – weight, в другом – age, в третьем – height?
— Да, это очень просто и удобно.
Мы просто вызываем метод Collections.sort, передаем туда список объектов и еще специальный объект во втором параметре, который реализует интерфейс Comparator и говорит, как правильно сравнивать пары объектов в процессе сортировки.
— Гм. Вроде все понятно. Дай-ка я сам попробую. Допустим, мне нужно отсортировать пользователей по весу, это будет так:
— Отлично. А если я хочу отсортировать в обратном порядке?
— А подумать? Ответ очень простой!
— А если я хочу сортировать по фамилии? Как сортировать строки, Билаабо?
— А у строк уже реализован метод compareTo, надо просто вызвать его:
— Это был отличный урок, Билаабо, спасибо тебе большое.
Выбор между Comparator и Comparable
Для реализации сортировки требуется, чтобы сортируемые объекты можно было сравнивать между собой на больше-меньше. Иначе говоря, чтобы было определено правило, которое позволит для любых двух объектов указать, какой из них в рамках данного контекста идет раньше, а какой позже.
В java эти правила определяются на уровне классов, к которым принадлежат объекты. Для примера возьмем класс для описания счета пользователя:
В зависимости от контекста сравнение счетов пользователя может происходить по разным правилам, например:
в приложении пользователь видит счета, отсортированные по currency, потом по value;
в админке счета всех пользователей отсортированы по дате изменения.
Для реализации сравнения на больше-меньше в java предусмотрено две возможности:
UserAccount реализует интерфейс Comparable В этом случае два объекта получают возможность сравнения между собой: acc1.compareTo(acc2)
Очевидно, что в некоторых случаях выбора между Comparable и Comparator нет. Если исходный класс нельзя модифицировать, или если требуются разные правила сравнения, то придется использовать Comparator. В остальных случаях, технически, можно использовать как Comparator, так и Comparable.
Согласно документации использование Comparable возможно, если для сравнения используется естественный порядок (class’s natural ordering). По ссылке есть представление разработчиков, что такое естественный порядок для стандартных классов (String, Date). Мне не удалось выяснить, что такое естественный порядок в общем случае. Выглядит, что это интуитивное представление разработчика о порядке в данном контексте. При этом даже для стандартных классов порядок может быть не интуитивен (в каком порядке должны идти значения BigDecimal с разной точностью, например 4.0 и 4.00?). Практика показывает, что «естественность» правил различается в понимании разных разработчиков и контекстов. Для меня необходимость опоры на интуицию является аргументом против использования Comparable.
При написании кода приходится лавировать между явностью и неявностью. Явность хороша тем, что для понимания участка кода требуется рассмотреть лишь узкий контекст его использования. В то же время неявность позволяет использовать одинаковые правила для всех участков кода. Разберем на примере: разработчику требуется отсортировать список счетов. Правила сравнения можно указать:
явно: Arrays.sort(accountsList, accountByValueComparator)
В случае явной передачи компаратора найти его использования элементарно. Я считаю это аргументом за использование компаратора. (Еще одним примером сложностей с поиском неявных использований может служить equals/hashCode, но альтернативы в виде «Equalator»-а для них нет).
Руководство по компаратору Java 8.сравнение()
Практическое руководство по статическим функциям и методам экземпляра сопоставимого интерфейса, которые были представлены в Java 8.
1. Обзор
2. Начало работы
2.1. Пример класса Бобов
Для примеров в этой статье давайте создадим Employee bean и будем использовать его поля для сравнения и сортировки:
2.2. Наши Данные Тестирования
Давайте также создадим массив сотрудников, который будет использоваться для хранения результатов нашего типа в различных тестовых случаях на протяжении всей статьи:
Первоначальное упорядочение элементов сотрудников будет:
На протяжении всей статьи мы будем сортировать выше Employee массив, используя различные функции.
Для тестовых утверждений мы будем использовать набор предварительно отсортированных массивов, которые мы сравним с нашими результатами сортировки (т. Е. массивом employees ) для различных сценариев.
Давайте объявим несколько из этих массивов:
Как всегда, не стесняйтесь обращаться к нашей ссылке GitHub для получения полного кода.
3. Использование компаратора.
В этом разделе рассматриваются варианты функции Comparator.comparing static.
3.1. Вариант выбора Ключа
Функция Comparator.comparing static принимает ключ сортировки Function и возвращает Comparator для типа, содержащего ключ сортировки:
Чтобы увидеть это в действии, давайте использовать поле name в Employee в качестве ключа сортировки и передадим ссылку на его метод в качестве аргумента типа Function. Компаратор , возвращенный из того же самого, используется для сортировки:
Как вы можете видеть, значения массива employees сортируются по имени в результате сортировки:
3.2. Выбор ключа и Вариант компаратора
Как вы можете видеть, результаты сортируются в порядке убывания по имени :
3.3. Использование компаратора.
Результаты сортируются в порядке убывания по имени :
3.4. Использование компаратора.
Давайте посмотрим, как упорядочиваются значения массива employees после сортировки:
3.5. Использование компаратора.
Давайте посмотрим, как упорядочиваются значения массива employees после сортировки с mobile в качестве ключа:
3.6. Использование компаратора.
Давайте посмотрим, как упорядочиваются значения массива employees после сортировки с зарплатой в качестве ключа сортировки:
4. Учет естественного порядка в компараторе
4.1. Использование Естественного порядка
Функция естественный порядок возвращает Компаратор для типа возврата, указанного в подписи:
Давайте посмотрим, как упорядочиваются значения массива employees после сортировки:
4.2. Использование Обратного Естественного Порядка
Давайте посмотрим, как упорядочиваются значения массива employees после сортировки:
5. Учет нулевых значений в компараторе
5.1. Сначала Рассмотрим Null
Давайте случайным образом вставим null значения в массив employees :
Давайте посмотрим, как упорядочиваются значения массива employees после сортировки:
5.2. Считать Нулевым Последнее
Давайте посмотрим, как упорядочиваются значения массива employees после сортировки:
6. Использование компаратора.
Функция thenComparing позволяет настроить лексикографическое упорядочение значений, предоставив несколько ключей сортировки в определенной последовательности.
Давайте рассмотрим другой массив класса Employee :
Рассмотрим следующую последовательность элементов в приведенном выше массиве:
Давайте запишем последовательность сравнений как возраст с последующим именем и посмотрим порядок этого массива:
Давайте посмотрим, как упорядочиваются значения массива employees после сортировки:
Аналогично, существуют функции then Comparing Long и then Comparing Double для использования long и double ключей сортировки.