我有一个简单的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类似:

[Person("John",47),Person("Britney",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-Complex.

Second question:以上使用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)));

推荐答案

这样做的时间复杂性必须至少为O(N),其中n是personList个元素的数量.要找到每个人的最大年龄,你必须判断every个人.

流操作的时间复杂性几乎没有保证,因此在这里我将假定我的机器上有OpenJDK 17实现.也就是说,很难想象有人会编写非最佳实现.

您使用STREAMS的解决方案是O(N).每个元素首先由groupingBy收集器处理以放入其中一个组中,然后由maxBy收集器使用,maxBy收集器对每个组进行操作.两位Collection 家所做的事情都是在固定的时间内完成的.groupingBy只判断它是否匹配任何现有的组(这是通过HashMap查找来完成的),maxBy使用提供的比较器将其与当前的最大值进行比较.

然后,您为结果映射中的每个条目创建一个Person,这显然也是O(N).

不使用流的解决方案也是O(N)--对personList中的每个元素执行一系列恒定时间的操作(读写到personAgg).因此,就时间复杂性而言,它是最优的.

请注意,您还可以将循环体重写为对compute的一次调用:

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

当然,这只是避免了多次访问 map ,并改变了时间复杂性.

Java相关问答推荐

无法处理批处理侦听器中的反序列化异常

Hibernate 6支持Joda DateTime吗?

Spring Boot@Cachebale批注未按预期工作

呈现文本和四舍五入矩形时出现的JavaFX窗格白色瑕疵

无法使用Java&;TestContainers获取AWS SQS队列的属性

使用UTC时区将startDatetime转换为本地时间

自定义批注的外推属性值

使用Room Database删除Jetpack合成中的所有项目后,UI未重新合成

搜索列表返回多个频道

将ByteBuffer异步写入InputStream或Channel或类似对象

基于配置switch 的@Controller的条件摄取

根本不显示JavaFX阿拉伯字母

如果List是一个抽象接口,那么Collectors.toList()如何处理流呢?

在java中使用不同的application.properties-jar而不使用Spring

Java Flux中的延迟增加

Java中的发布/订阅-Long Live和Short Live Publisher,哪种方法是正确的?

如何设计包含已知和未知键值对映射的Java类?

如何使用Java ZoneID的区域设置?

按长度排序字符串数组

多线程、并发和睡眠未按预期工作