«Фильтрация коллекции Java по списку»

«1. Обзор

Фильтрация коллекции по списку — распространенный сценарий бизнес-логики. Есть много способов добиться этого. Однако некоторые из них могут привести к неэффективным решениям, если они не будут выполнены должным образом.

В этом уроке мы сравним некоторые реализации фильтрации и обсудим их преимущества и недостатки.

2. Использование цикла For-Each

Мы начнем с самого классического синтаксиса, цикла for-each.

Для этого и всех других примеров в этой статье мы будем использовать следующий класс:

public class Employee {

    private Integer employeeNumber;
    private String name;
    private Integer departmentId;
    //Standard constructor, getters and setters.
}

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

private List<Employee> buildEmployeeList() {
    return Arrays.asList(
      new Employee(1, "Mike", 1),
      new Employee(2, "John", 1),
      new Employee(3, "Mary", 1),
      new Employee(4, "Joe", 2),
      new Employee(5, "Nicole", 2),
      new Employee(6, "Alice", 2),
      new Employee(7, "Bob", 3),
      new Employee(8, "Scarlett", 3));
}

private List<String> employeeNameFilter() {
    return Arrays.asList("Alice", "Mike", "Bob");
}

Для В нашем примере мы отфильтруем первый список сотрудников на основе второго списка с именами сотрудников, чтобы найти только сотрудников с этими конкретными именами.

Теперь давайте посмотрим на традиционный подход — просмотр обоих списков в цикле в поисках совпадений:

@Test
public void givenEmployeeList_andNameFilterList_thenObtainFilteredEmployeeList_usingForEachLoop() {
    List<Employee> filteredList = new ArrayList<>();
    List<Employee> originalList = buildEmployeeList();
    List<String> nameFilter = employeeNameFilter();

    for (Employee employee : originalList) {
        for (String name : nameFilter) {
            if (employee.getName().equals(name)) {
                filteredList.add(employee);
                // break;
            }
        }
    }

    assertThat(filteredList.size(), is(nameFilter.size()));
}

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

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

Если мы назовем размер списка сотрудников n, то nameFilter будет примерно таким же большим, что даст нам классификацию O(n2).

3. Использование потоков и List#contains

Теперь мы проведем рефакторинг предыдущего метода, используя лямбда-выражения для упрощения синтаксиса и улучшения читабельности. Давайте также используем метод List#contains в качестве лямбда-фильтра:

@Test
public void givenEmployeeList_andNameFilterList_thenObtainFilteredEmployeeList_usingLambda() {
    List<Employee> filteredList;
    List<Employee> originalList = buildEmployeeList();
    List<String> nameFilter = employeeNameFilter();

    filteredList = originalList.stream()
      .filter(employee -> nameFilter.contains(employee.getName()))
      .collect(Collectors.toList());

    assertThat(filteredList.size(), is(nameFilter.size()));
}

Использование Stream API значительно улучшило читабельность, но наш код остается таким же неэффективным, как и предыдущий метод, потому что он все еще выполняет внутреннюю итерацию декартова произведения. . Таким образом, мы имеем ту же классификацию O(n2).

4. Использование потоков с HashSet

Для повышения производительности мы должны использовать метод HashSet#contains. Этот метод отличается от List#contains тем, что он выполняет поиск хеш-кода, что дает нам количество операций за постоянное время:

@Test
public void givenEmployeeList_andNameFilterList_thenObtainFilteredEmployeeList_usingLambdaAndHashSet() {
    List<Employee> filteredList;
    List<Employee> originalList = buildEmployeeList();
    Set<String> nameFilterSet = employeeNameFilter().stream().collect(Collectors.toSet());

    filteredList = originalList.stream()
      .filter(employee -> nameFilterSet.contains(employee.getName()))
      .collect(Collectors.toList());

    assertThat(filteredList.size(), is(nameFilterSet.size()));
}

Благодаря использованию HashSet эффективность нашего кода значительно улучшилась, не влияя на удобочитаемость. Поскольку HashSet# содержит запуски за постоянное время, мы улучшили нашу классификацию до O(n).

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

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

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

Весь код, представленный в этой статье, доступен на GitHub.