java - 如何提高 Java ArrayList 的性能

Question

我正在使用一个巨大的ArrayList，代码如下

public final List<MyClass> list = new ArrayList<>();

public void update(MyClass myClass) {
int i;
for (i=0; i < list.size(); i++) {
        if (myClass.foo(list.get(i))) {
            list.set(i, myClass);
            break;
        }    
    }    
    if (i == list.size()) {    
        list.add(myClass);    
    }    
}

这个列表非常大。在这种情况下我还可以做些什么来提高性能吗？也许使用一些 Java 8 功能，替换 ArrayList 或类似的东西。

与此列表相关的另一个运行时间太长的代码如下:

public List<MyClass> something(Integer amount) {
list.sort((m1, m2) -> Double.compare(m2.getBar(), m1.getBar()));
return list.stream()
        .limit(amount)
        .collect(Collectors.toList());
}

欢迎大家帮忙，谢谢大家

Answer 1

这似乎是ArrayList的选择不太好。

在第一种情况下，您尝试通过列表中的属性查找对象。要在列表中查找对象，您必须 checkin 列表中的每个元素。列表越大，它就越长。 (使用 ArrayList 最坏情况复杂度为 O(N))

如果您使用HashMap您可以使用您的属性作为 map 的键，而不是 List。这样，您可以直接选择需要更新的对象，而无需检查列表中的每个元素。执行时间将不再依赖于条目数。 (使用 HashMap 最坏情况复杂度为 O(1))

如果您使用HashMap而不是ArrayList ，您的更新代码将如下所示:

public void update(MyClass myClass) {
    map.put(myClass.getKey(), myClass);
}

(其中 getKey() 是您尝试在 foo 方法中等于的属性)。

但这只是针对第一种情况。根据我们掌握的信息，这似乎是最好的解决方案。