为什么数组比ArrayList快那么多？

Question

最近，我尝试解决 Project Euler 的第23道题。为此，我首先创建了一个名为abundants的所有过剩数的列表。

接下来，我遍历这个列表，并构建另一个列表，其中包含在某个限制以下的所有过剩数之和。现在我注意到了一些奇怪的事情。我使用嵌套循环两次迭代列表。但如果我使用数组来存储总和，那么它只需要几秒钟，如果我将总和添加到 ArrayList 中，则需要几个小时。这是为什么呢？我认为昂贵的操作应该是两个嵌套循环，但似乎ArrayList#add才是代价高昂的操作。有没有任何提示说明这种情况？

这里是数组的代码：

for (int i = 0; i < abundants.size(); i++) {
   for (int j = 0; j < abundants.size(); j++) {
      int tot = abundants.get(i) + abundants.get(j);
      if (tot <= limit)
         isSum[tot] = true;
      }
   }
}

以下是ArrayList的代码：

ArrayList<Integer> sums = new ArrayList<Integer>();
for (int i = 0; i < abundants.size(); i++) {
   for (int j = 0; j < abundants.size(); j++) {
      int s = abundants.get(i) + abundants.get(j);
      if (!sums.contains(s) && s < limit) {
         sums.add(s);
      }
   }
 }

- anon

---

我不是专家，但根据大小而定，如果contains()无法执行二进制搜索，则可能会变得昂贵。 - Bobby

是的，但这是否是几秒钟对几小时的原因？ - anon

使用 BitSet 会更好。 - starblue

Answer 1

您的ArrayList实现是O(n^3)，而另一个是O(n^2): sums.contains(...)必须遍历整个sums列表，以便在内部循环的每次迭代中使用。

- sjr

---

你能否加上可能的解决方案（如果你知道的话），因为我也很感兴趣。 - Bobby

@Bobby, @Roflcoptr，if (!sums.contains(s) && s < limit) { sums.add(s); } 应该改为 if (s <= limit) { sums.set(s, True); } 才能等效。 - ikegami

这真的可以成为几秒钟与几小时的原因吗？ - RoflcoptrException

这真的取决于这些列表有多大，但是可以的！ :) - sjr

如果您的abundants数组中有20000个元素，那么您需要执行20000 * 20000次操作。在每一次操作中，您都需要做些什么。如果最坏情况下，您还需要对这些迭代中的每一个元素再执行20000次操作，这可能需要几个小时或几天的时间。 - sjr

20000次很好。做一件每次需要1秒钟的事情，你需要五个半小时。 - schnaader

Answer 2

我认为你的问题在于ArrayList#contains方法，因为它必须遍历整个列表，从而将复杂度提高到O(n^3)，而程序#1的复杂度只有O(n^2)。

- Amadan

Answer 3

您的代码不等价，.contains() 比您使用原始数组的方式更加昂贵。每次调用 .contains() 都会遍历整个数组，而在基于原始数组的版本中则不需要这样做。

- user177800

Answer 4

因为int比Integer更快。

尝试在第一种情况下使用Integer[]，或在第二种情况下使用TIntArrayList进行比较。

- Peter Lawrey

---

Java 没有将 int、long、float 和其他基本类型作为一等对象的原因是有其道理的... - Bill K

虽然 int 比 Integer 更快，但需要 极其特殊的情况 才会导致减速 3000 倍（如问题中所述，小时级别与秒级别）。 - meriton

@meriton，这是非常正确的。我错过了那一点。根据情况，改进很可能会达到20%至300%。一般规则是，在比较两个事物时，要进行类似的比较，不要以不同的方式使用它。 ;) - Peter Lawrey

Answer 5

如果您知道元素的（最大）数量，请尝试使用给定大小初始化数组列表：

ArrayList<Integer> sums = new ArrayList<Integer>(abundants.size() * abundants.size());

这样做，ArrayList 就不必被重新调整大小，这将提高速度。

- leifg

---

contains()仍然需要遍历整个ArrayList，因此速度增加微不足道。最好尝试将运行时复杂度从O(n^3)更改为更合理的值。 - Emil Vikström