title: Why is an array so much faster than an ArrayList?
body: <p>Recently, I tried to solve <a href="http://projecteuler.net/index.php?section=problems&amp;id=23" rel="nofollow noreferrer">Problem 23 of Project Euler</a>. For that I first create a list of all abundant numbers, called <code>abundants</code>.</p>
  
  <p>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?</p>
  
  <p>Here the code for the array:</p>
  
  <pre><code>for (int i = 0; i &lt; abundants.size(); i++) {
     for (int j = 0; j &lt; abundants.size(); j++) {
        int tot = abundants.get(i) + abundants.get(j);
        if (tot &lt;= limit)
           isSum[tot] = true;
        }
     }
  }
  </code></pre>
  
  <p>Here the code for the ArrayList:</p>
  
  <pre><code>ArrayList&lt;Integer&gt; sums = new ArrayList&lt;Integer&gt;();
  for (int i = 0; i &lt; abundants.size(); i++) {
     for (int j = 0; j &lt; abundants.size(); j++) {
        int s = abundants.get(i) + abundants.get(j);
        if (!sums.contains(s) &amp;&amp; s &lt; limit) {
           sums.add(s);
        }
     }
   }
  </code></pre>