不带 Stream API 的集合 GroupBy 聚合

Question

我有一个简单的 ArrayList，其中包含人们的姓名和年龄（Person 对象）。

class Person {
    String name;
    int age;
}

List<Person> personList = new ArrayList<>();
personList.add(new Person("john", 47));
personList.add(new Person("john", 35));
personList.add(new Person("john", 12));
personList.add(new Person("britney", 27));
personList.add(new Person("britney", 16));

目标是与每个名字都有最大年龄的人一起生成ArrayList，但不使用Stream API。类似于 SQL 的

SELECT name, max(AGE) FROM P GROUP BY name

:

[人（“约翰”，47），人（“布兰妮”，27）]

使用 Stream API 我就是这样做的：

personList.stream()
        .collect(Collectors
            .groupingBy(Person::getName,
                    Collectors.maxBy(Comparator.comparing(Person::getAge))))
            .values().stream()
            .map(s -> s.orElseGet(Person::new))
            .collect(Collectors.toList());

但我怀疑，在没有 Stream API 的情况下我是否做得最好（代码如下）。

问题：下面的代码是最佳方式吗？如果没有，请描述您的情况并提及 O 复杂度。

第二个问题： 上述 Stream API 的解决方案有哪些 O 复杂度？令人惊讶的是，使用函数式方法我无法掌握它。

Map<String, Integer> personAgg = new HashMap<>();
personList.forEach(personAdd -> {
    var currentKey=personAdd.getName();
    var currentValue=personAdd.getAge();
    if (personAgg.containsKey(currentKey)) {
        if (personAgg.get(currentKey) < currentValue)
            personAgg.put(currentKey, currentValue);
    } else {
        personAgg.put(currentKey, currentValue);
    }
});

List<Person> personAggArray = new ArrayList<>();
personAgg.forEach((k,v) -> personAggArray.add(new Person(k,v)));

Answer 1

执行此操作的时间复杂度必须至少为 O(n)，其中 n 是

personList

中的元素数量。要找到每个人的最大年龄，您必须检查每个人。

流操作的时间复杂度保证很少甚至没有，所以这里我只考虑我机器上的 OpenJDK 17 实现。

使用流的解决方案是 O(n)。每个元素首先由

groupingBy

收集器处理并放入其中一个组中，然后由

maxBy

收集器消耗，该收集器对每个组进行操作。两个收集器所做的事情都是在恒定的时间内完成的。

groupingBy

只是检查它是否与任何现有组匹配（这是通过

HashMap

查找完成的），并且

maxBy

使用提供的比较器将其与当前最大值进行比较。

然后，为结果映射中的每个条目创建一个

Person

，这显然也是 O(n) 。

不使用流的解决方案也是 O(n) - 您为

personAgg

中的每个元素执行一堆恒定时间的操作（读取和写入

personList

）。所以就时间复杂度而言它是最优的。

请注意，您还可以将循环体重写为仅调用一次

compute

:

for (var person: personList) {
    personAgg.compute(
        person.getMame(),
        (k, v) -> Math.max(
            Objects.requireNonNullElse(v, Integer.MIN_VALUE),
            person.getAge()
        )
    );
}

当然，这只是避免了多次访问地图，而改变了时间复杂度。