title: Randomizing list processing faster than Collections.shuffle()?
body: <p>I am developing an agent-based model in Java. I have used a profiler to reduce any inefficiencies down to the point that the only thing holding it back is Java's <strong>Collections.shuffle()</strong>.</p>
  
  <p>The agents (they're animals) in my model need to be processed in a random order so that no agent is consistently processed before the others.</p>
  
  <p><strong>I am looking for</strong>: Either a <em>faster</em> way to shuffle than Java's Collections.shuffle() or an alternative method of processing the elements in an ArrayList in a randomized order that is <em>significantly faster</em>. If you know of a data structure that would be faster than an ArrayList, by all means please answer. I have considered LinkedList and ArrayDeque, but they aren't making much of a difference.</p>
  
  <p><strong><em>Currently, I have over 1,000,000 elements in the list I am trying to shuffle. Over time, this amount increases and it is becoming increasingly inefficient to shuffle it.</em></strong></p>
  
  <p><strong>Is there an alternative data structure or way of randomizing the processing of elements that is faster?</strong></p>
  
  <p>I only need to be able to store elements and process them in a randomized order. I do not use contains or anything more complex than storage and iterating over them.</p>
  
  <p>Here is some sample code to better explain what I am trying to achieve:</p>
  
  <p><strong>UPDATE:</strong> Sorry for the ConcurrentModificationException, I didn't realize I had done that and I didn't intend to confuse anyone. Fixed it in the code below.</p>
  
  <pre><code>ArrayList&lt;Agent&gt; list = new ArrayList&lt;&gt;();
  void process()
  {
      list.add(new Agent("Zebra"));
      Random r = new Random();
      for (int i = 0; i &lt; 100000; i++)
      {
          ArrayList&lt;Agent&gt; newlist = new ArrayList&lt;&gt;();
          Collections.shuffle(list);//Something that will allow the order to be random (random quality does not matter to me), yet faster than a shuffle
          for (String str : list)
          {
              newlist.add(str);
              if(r.nextDouble() &gt; 0.99)//1% chance of adding another agent to the list
              {
                  newlist.add(new Agent("Lion"));
              }
          }
          list = newlist;
      }
  }
  </code></pre>
  
  <p><strong>ANOTHER UPDATE</strong>
  I thought about doing list.remove(rando.nextInt(list.size()) but since remove for ArrayLists is O(n) it would be even worse to do that rather than shuffle for such a large list size.</p>