Why is an array so much faster than an ArrayList?

Recently, I tried to solve Problem 23 of Project Euler. For that I first create a list of all abundant numbers, called abundants.

Next I iterate over this list and build another list of all sums of abundant numbers that are below a certain li开发者_StackOverflow中文版mit. Now I noticed something strange. I use a nested loop to iterate twice over the list. But if I use an array to store the sum it takes some seconds, if I add the sums to an ArrayList it takes hours. What's the reason for that? I thought the costly operation are the two nested loops, but it seems the costly operation is ArrayList#add. Any hints why this is the case?

Here the code for the array:

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;
      }
   }
}

Here the code for the 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);
      }
   }
 }

---

Your ArrayList implementation is O(n^3) whereas the other is O(n^2): sums.contains(...) has to traverse the entire sums list for every iteration of your inner loop.

---

I think rather that your problem is in ArrayList#contains, which has to traverse the whole list, thus raising your complexity to O(n^3), as opposed to O(n^2) of the program #1.

---

Your code isn't equivalent, the .contains() is more expensive than what you are doing with the raw array. The .contains() walks the entire array every time is called, you don't do this in the raw array based version.

---

Because int can be much faster than Integer.

Try using Integer[] in the first case or TIntArrayList in the second case for comparison.

---

If you know the (maximum) number of the elements, try to initialize the Array list with a given size:

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

With that the ArrayList won't have to be resized, this will increase the speed.