Java 8 — мощное сравнение с Lambdas

8 августа 2021 г. · 7 мин. чтения

Задача: Медиана двух отсортированных массивов

Даны два отсортированных массива размерами n и m. Найдите медиану слияния этих двух массивов.
Временная сложность решения должна быть O(log(m + n)) ...

ANDROMEDA

1. Обзор

В этом руководстве мы впервые рассмотрим поддержку Lambda в Java 8, в частности, как использовать ее для написания Comparator и сортировки Collection .

Эта статья является частью серии «Java — Back to Basic» здесь, на ForEach.

Во-первых, давайте определим простой класс сущности:

public class Human {
    private String name;
    private int age;

    // standard constructors, getters/setters, equals and hashcode
}

2. Базовая сортировка без лямбда-выражений

До Java 8 сортировка коллекции включала создание анонимного внутреннего класса для Comparator , используемого при сортировке:

new Comparator<Human>() {
    @Override
    public int compare(Human h1, Human h2) {
        return h1.getName().compareTo(h2.getName());
    }
}

Это будет просто использоваться для сортировки списка человеческих сущностей :

@Test
public void givenPreLambda_whenSortingEntitiesByName_thenCorrectlySorted() {
    List<Human> humans = Lists.newArrayList(
      new Human("Sarah", 10), 
      new Human("Jack", 12)
    );
    
    Collections.sort(humans, new Comparator<Human>() {
        @Override
        public int compare(Human h1, Human h2) {
            return h1.getName().compareTo(h2.getName());
        }
    });
    Assert.assertThat(humans.get(0), equalTo(new Human("Jack", 12)));
}

3. Базовая сортировка с поддержкой лямбда

С введением Lambdas мы теперь можем обойти анонимный внутренний класс и добиться того же результата с помощью простой функциональной семантики :

(final Human h1, final Human h2) -> h1.getName().compareTo(h2.getName());

Точно так же мы можем теперь проверить поведение так же, как и раньше:

@Test
public void whenSortingEntitiesByName_thenCorrectlySorted() {
    List<Human> humans = Lists.newArrayList(
      new Human("Sarah", 10), 
      new Human("Jack", 12)
    );
    
    humans.sort(
      (Human h1, Human h2) -> h1.getName().compareTo(h2.getName()));
 
    assertThat(humans.get(0), equalTo(new Human("Jack", 12)));
}

Обратите внимание, что мы также используем новый API сортировки , добавленный в java.util.List в Java 8 , вместо старого API Collections.sort .

4. Базовая сортировка без определения типа

Мы можем еще больше упростить выражение, не указывая определения типов; компилятор способен вывести их самостоятельно:

(h1, h2) -> h1.getName().compareTo(h2.getName())

Опять же, тест остается очень похожим:

@Test
public void 
  givenLambdaShortForm_whenSortingEntitiesByName_thenCorrectlySorted() {
    
    List<Human> humans = Lists.newArrayList(
      new Human("Sarah", 10), 
      new Human("Jack", 12)
    );
    
    humans.sort((h1, h2) -> h1.getName().compareTo(h2.getName()));
 
    assertThat(humans.get(0), equalTo(new Human("Jack", 12)));
}

5. Сортировка с использованием ссылки на статический метод

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

Во-первых, мы собираемся определить метод compareByNameThenAge с точно такой же сигнатурой, что и метод сравнения в объекте Comparator<Human> :

public static int compareByNameThenAge(Human lhs, Human rhs) {
    if (lhs.name.equals(rhs.name)) {
        return Integer.compare(lhs.age, rhs.age);
    } else {
        return lhs.name.compareTo(rhs.name);
    }
}

Затем мы собираемся вызвать метод human.sort с этой ссылкой:

humans.sort(Human::compareByNameThenAge);

Конечным результатом является работающая сортировка коллекции с использованием статического метода в качестве Comparator :

@Test
public void 
  givenMethodDefinition_whenSortingEntitiesByNameThenAge_thenCorrectlySorted() {
    
    List<Human> humans = Lists.newArrayList(
      new Human("Sarah", 10), 
      new Human("Jack", 12)
    );
    
    humans.sort(Human::compareByNameThenAge);
    Assert.assertThat(humans.get(0), equalTo(new Human("Jack", 12)));
}

6. Сортировка извлеченных компараторов

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

Мы собираемся использовать геттер getName() для построения лямбда-выражения и сортировки списка по имени:

@Test
public void 
  givenInstanceMethod_whenSortingEntitiesByName_thenCorrectlySorted() {
    
    List<Human> humans = Lists.newArrayList(
      new Human("Sarah", 10), 
      new Human("Jack", 12)
    );
    
    Collections.sort(
      humans, Comparator.comparing(Human::getName));
    assertThat(humans.get(0), equalTo(new Human("Jack", 12)));
}

7. Обратная сортировка

JDK 8 также представил вспомогательный метод для реверсирования компаратора. Мы можем быстро использовать это, чтобы изменить нашу сортировку:

@Test
public void whenSortingEntitiesByNameReversed_thenCorrectlySorted() {
    List<Human> humans = Lists.newArrayList(
      new Human("Sarah", 10), 
      new Human("Jack", 12)
    );
    
    Comparator<Human> comparator
      = (h1, h2) -> h1.getName().compareTo(h2.getName());
    
    humans.sort(comparator.reversed());
 
    Assert.assertThat(humans.get(0), equalTo(new Human("Sarah", 10)));
}

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

Лямбда-выражения сравнения не обязательно должны быть такими простыми. Мы можем написать и более сложные выражения, например, отсортировав объекты сначала по имени, а затем по возрасту:

@Test
public void whenSortingEntitiesByNameThenAge_thenCorrectlySorted() {
    List<Human> humans = Lists.newArrayList(
      new Human("Sarah", 12), 
      new Human("Sarah", 10), 
      new Human("Zack", 12)
    );
    
    humans.sort((lhs, rhs) -> {
        if (lhs.getName().equals(rhs.getName())) {
            return Integer.compare(lhs.getAge(), rhs.getAge());
        } else {
            return lhs.getName().compareTo(rhs.getName());
        }
    });
    Assert.assertThat(humans.get(0), equalTo(new Human("Sarah", 10)));
}

9. Сортировка с несколькими условиями — композиция

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

Начиная с JDK 8, теперь мы можем объединять несколько компараторов для создания более сложной логики сравнения:

@Test
public void 
  givenComposition_whenSortingEntitiesByNameThenAge_thenCorrectlySorted() {
    
    List<Human> humans = Lists.newArrayList(
      new Human("Sarah", 12), 
      new Human("Sarah", 10), 
      new Human("Zack", 12)
    );

    humans.sort(
      Comparator.comparing(Human::getName).thenComparing(Human::getAge)
    );
    
    Assert.assertThat(humans.get(0), equalTo(new Human("Sarah", 10)));
}

10. Сортировка списка с помощью `Stream.sorted()`

Мы также можем сортировать коллекцию, используя API Java 8 Stream sorted() .

Мы можем сортировать поток, используя естественный порядок, а также порядок, предоставляемый Компаратором. Для этого у нас есть два перегруженных варианта API sorted() :

sort ed() — сортирует элементы Stream в естественном порядке; класс элемента должен реализовать интерфейс Comparable .
`sorted` `(Comparator` `<?` `super` `T>` `comparator)` — сортирует элементы на основе экземпляра `Comparator .`

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

@Test
public final void 
  givenStreamNaturalOrdering_whenSortingEntitiesByName_thenCorrectlySorted() {
    List<String> letters = Lists.newArrayList("B", "A", "C");
    
    List<String> sortedLetters = letters.stream().sorted().collect(Collectors.toList());
    assertThat(sortedLetters.get(0), equalTo("A"));
}

Теперь давайте посмотрим, как мы можем использовать собственный компаратор с API sorted() :

@Test
public final void 
  givenStreamCustomOrdering_whenSortingEntitiesByName_thenCorrectlySorted() {   
    List<Human> humans = Lists.newArrayList(new Human("Sarah", 10), new Human("Jack", 12));
    Comparator<Human> nameComparator = (h1, h2) -> h1.getName().compareTo(h2.getName());
    
    List<Human> sortedHumans = 
      humans.stream().sorted(nameComparator).collect(Collectors.toList());
    assertThat(sortedHumans.get(0), equalTo(new Human("Jack", 12)));
}

Мы можем еще больше упростить приведенный выше пример, если воспользуемся методом Comparator.comparing() :

@Test
public final void 
  givenStreamComparatorOrdering_whenSortingEntitiesByName_thenCorrectlySorted() {
    List<Human> humans = Lists.newArrayList(new Human("Sarah", 10), new Human("Jack", 12));
 
    List<Human> sortedHumans = humans.stream()
      .sorted(Comparator.comparing(Human::getName))
      .collect(Collectors.toList());
      
    assertThat(sortedHumans.get(0), equalTo(new Human("Jack", 12)));
}

11. Сортировка списка в обратном порядке с помощью `Stream.sorted()`

Мы также можем использовать Stream.sorted() для сортировки коллекции в обратном порядке.

Во-первых, давайте посмотрим на пример того, как объединить метод sorted() с Comparator.reverseOrder() для сортировки списка в обратном естественном порядке :

@Test
public final void 
  givenStreamNaturalOrdering_whenSortingEntitiesByNameReversed_thenCorrectlySorted() {
    List<String> letters = Lists.newArrayList("B", "A", "C");

    List<String> reverseSortedLetters = letters.stream()
      .sorted(Comparator.reverseOrder())
      .collect(Collectors.toList());
      
    assertThat(reverseSortedLetters.get(0), equalTo("C"));
}

Теперь давайте посмотрим, как мы можем использовать метод sorted() и собственный Comparator :

@Test
public final void 
  givenStreamCustomOrdering_whenSortingEntitiesByNameReversed_thenCorrectlySorted() {
    List<Human> humans = Lists.newArrayList(new Human("Sarah", 10), new Human("Jack", 12));
    Comparator<Human> reverseNameComparator = 
      (h1, h2) -> h2.getName().compareTo(h1.getName());

    List<Human> reverseSortedHumans = humans.stream().sorted(reverseNameComparator)
      .collect(Collectors.toList());
    assertThat(reverseSortedHumans.get(0), equalTo(new Human("Sarah", 10)));
}

Обратите внимание, что вызов compareTo переворачивается, что отвечает за реверсирование.

Наконец, давайте упростим приведенный выше пример, используя метод Comparator.comparing () :

@Test
public final void 
  givenStreamComparatorOrdering_whenSortingEntitiesByNameReversed_thenCorrectlySorted() {
    List<Human> humans = Lists.newArrayList(new Human("Sarah", 10), new Human("Jack", 12));

    List<Human> reverseSortedHumans = humans.stream()
      .sorted(Comparator.comparing(Human::getName, Comparator.reverseOrder()))
      .collect(Collectors.toList());
    
    assertThat(reverseSortedHumans.get(0), equalTo(new Human("Sarah", 10)));
}

12. Нулевые значения

До сих пор мы реализовывали наши Comparator так, чтобы они не могли сортировать коллекции, содержащие нулевые значения. То есть, если коллекция содержит хотя бы один нулевой элемент, то метод сортировки выдает исключение NullPointerException :

@Test(expected = NullPointerException.class)
public void givenANullElement_whenSortingEntitiesByName_thenThrowsNPE() {
    List<Human> humans = Lists.newArrayList(null, new Human("Jack", 12));

    humans.sort((h1, h2) -> h1.getName().compareTo(h2.getName()));
}

Самое простое решение — обрабатывать нулевые значения вручную в нашей реализации Comparator :

@Test
public void givenANullElement_whenSortingEntitiesByNameManually_thenMovesTheNullToLast() {
    List<Human> humans = Lists.newArrayList(null, new Human("Jack", 12), null);

    humans.sort((h1, h2) -> {
        if (h1 == null) {
            return h2 == null ? 0 : 1;
        }
        else if (h2 == null) {
            return -1;
        }
        return h1.getName().compareTo(h2.getName());
    });

    Assert.assertNotNull(humans.get(0));
    Assert.assertNull(humans.get(1));
    Assert.assertNull(humans.get(2));
}

Здесь мы перемещаем все нулевые элементы в конец коллекции. Для этого компаратор считает, что нуль больше, чем ненулевые значения. Когда оба равны null , они считаются равными.

Кроме того, мы можем передать любой компаратор , который не является нулевым, в метод Comparator.nullsLast() и получить тот же результат :

@Test
public void givenANullElement_whenSortingEntitiesByName_thenMovesTheNullToLast() {
    List<Human> humans = Lists.newArrayList(null, new Human("Jack", 12), null);

    humans.sort(Comparator.nullsLast(Comparator.comparing(Human::getName)));

    Assert.assertNotNull(humans.get(0));
    Assert.assertNull(humans.get(1));
    Assert.assertNull(humans.get(2));
}

Точно так же мы можем использовать Comparator.nullsFirst() для перемещения нулевых элементов к началу коллекции:

@Test
public void givenANullElement_whenSortingEntitiesByName_thenMovesTheNullToStart() {
    List<Human> humans = Lists.newArrayList(null, new Human("Jack", 12), null);

    humans.sort(Comparator.nullsFirst(Comparator.comparing(Human::getName)));

    Assert.assertNull(humans.get(0));
    Assert.assertNull(humans.get(1));
    Assert.assertNotNull(humans.get(2));
}

Настоятельно рекомендуется использовать декораторы nullsFirst() или nullsLast() , поскольку они более гибкие и читабельные.

13. Заключение

Эта статья иллюстрирует различные интересные способы сортировки списка с помощью лямбда-выражений Java 8, переходя от синтаксического сахара к реальной и мощной функциональной семантике.

Реализацию всех этих примеров и фрагментов кода можно найти на GitHub .

Задача: Медиана двух отсортированных массивов

1. Обзор​

2. Базовая сортировка без лямбда-выражений​

3. Базовая сортировка с поддержкой лямбда​

4. Базовая сортировка без определения типа​

5. Сортировка с использованием ссылки на статический метод​

6. Сортировка извлеченных компараторов​

7. Обратная сортировка​

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

9. Сортировка с несколькими условиями — композиция​

10. Сортировка списка с помощью Stream.sorted()​

11. Сортировка списка в обратном порядке с помощью Stream.sorted()​

12. Нулевые значения​

13. Заключение​