Geek Answers Handbook

Why is an array so much faster than an ArrayList?

I recently tried to solve Problem 23 Project Euler . To do this, I first create a list of all the plentiful numbers, called abundants.

Next, I sort through this list and build another list of all sums of plentiful numbers that are below a certain limit. Now I noticed something strange. I use a nested loop to repeat twice in a list. But if I use an array to store the amount, it takes a few seconds, if I add the amount to an ArrayList, it takes several hours. What is the reason for this? I thought that an expensive operation is two nested loops, but it looks like an expensive operation is ArrayList # add. Any hints why this is so?

Here's 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 is the code for 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);
      }
   }
 }
+5
5

ArrayList - O (n ^ 3), - O (n ^ 2): sums.contains(...) sums .

+17

, ArrayList#contains, , O (n ^ 3), O (n ^ 2) # 1.

+6

, .contains() , , . .contains() , .

+3

int , Integer.

Try to use Integer[]in the first case or TIntArrayListin the second case for comparison.

+2
source

If you know the (maximum) number of elements, try initializing a list of arrays with a given size:

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

Since ArrayList will not need to be resized, it will increase speed.

-1
source

More articles:


All Articles