Фильтрация коллекции 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 (n 2 ) .

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(n 2 ) .

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 .