如何使用 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的选择不好。

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

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

如果使用HashMap而不是ArrayList，则更新代码将如下所示：

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

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

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

Answer 2

在这种情况下，

我还可以采取其他措施来提高性能？

问题是您的算法必须myClass.foo应用于列表中的每个元素，直到找到第一个匹配项。 如果按顺序执行此操作，则最坏情况的复杂性O(N)其中N是列表大小。 (而且列表大小很大。

现在，您可以并行进行搜索。 但是，如果可以有多个匹配项，则匹配列表中的第一个匹配项将很棘手。 而且您最终仍然会得到O(N/C)其中C是可用内核的数量。

比O(N)更好的唯一方法是使用不同的数据结构。 但是，如果不知道MyClass::foo方法的作用，就很难说出数据结构应该是什么。

---

你的第二个问题似乎是试图解决"前 K 个 N 个"问题。 这可以O(N log K)实施，甚至可能更好;请参阅从长度为 N 的数组返回前 k 个值的最佳算法。