Why is an array so much faster than an ArrayList?

Question

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 limit. 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);
 }
 }
 }

• Bobby: I'm no expert, but depending on the size the contains() might get expensive if it can't perform a binary search.
• anon: Yes, but is this the reason for some seconds against some hours?
• starblue: Using BitSet would be even better.

Answer 1

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.

• Bobby: Could you please add a possible solution (if you know any), because I'd also be interested in that.
• ikegami: @Bobby, @Roflcoptr, if (!sums.contains(s) && s < limit) { sums.add(s); } should be if (s <= limit) { sums.set(s, True); } to be equivalent.
• RoflcoptrException: Can this really be the reason for some seconds vs. some hours?
• sjr: It depends really on how big all these lists are, but yes it can be! :)
• sjr: So... if you have 20,000 elements in abundants, you are going over that 20,000 * 20,000 times. For each of those times, you are doing something. If you are, in the worst case, doing 20,000 more operations on EACH of those iterations, this could take hours or days.

Answer 2

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.

Answer 3

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.

Answer 4

Because int can be much faster than Integer.

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

• Bill K: There is a reason that Java didn't make int, long, float and the others first-class Objects...
• meriton: While int is faster than Integer, it takes extremely special circumstances for this to cause a slowdown by a factor of 3000 (hours vs. seconds, as reported in the question).
• Peter Lawrey: @meriton, This is very true. I missed that point. The improvement is more likely to be 20% to 300% depending on the situation. The general rule is when comparing two things, compare like for like and don't use it in different way. ;)

Answer 5

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.

• Emil Vikström: contains() still have to traverse the entire ArrayList so the speed increase is marginal. It's better to try to change the runtime complexity from O(n^3) to something more sane.