Re: iteration blues

On 03/11/2011 8:37 AM, bob wrote:
 >
 > public static void burnfire() {
 > Iterator<Particle> i = particles.iterator();
 > Vector<Particle> removelist = new Vector<Particle>();
 > while (i.hasNext()) {
 > Particle p = i.next();
 > p.move();
 > p.timeleft--;
 > if (p.timeleft == 0) removelist.add(p);
 >
 > }
 > particles.removeAll(removelist);
 >
 > }
 >
 > I'm concerned about inefficiency in the burnfire function. Does
 > anyone know how to rewrite this quickly if particles was a linked
 > list? The main issue is that I'm not sure if removing items during
 > iteration messes up the iterator.

What percentage of elements are removed each loop?

If it's like 1 or 2 out of 1000's, then just your method will be OK.

If you are eliminating like 50% of more per iteration, simply copy the
value:

ArrayList<Particle> newParticleList = new
ArrayList<Particle>(particles.size());

for (Particle p : particles) {
   // Process p
   if (p.timeLeft > 0)
     newParticeList.add(p);
}

Another approach would be "buckets". You create a bucket for each life
span so you know when you've reached nth iteration, the nth bucket
particles are done.

Pseudocode:

   ArrayList<ArrayList<Particle>> buckets = new
ArrayList<ArrayList<Particle>>(MAX_LIFETIME);

   roundRobin = 0;
   for each frame do
     buckets.set(roundRobin, createNewParticles(n));
     animate particles
     roundRobin = (roundRobin + 1) % MAX_LIFETIME;

The reference to the ArrayList<Particle> in slot n should disappear and
the garbage collector can manage the rest. If your concerned about
allocation/deallocation overhead, you can change createNewParticle to
accept the old array list and let it "refresh" the list reusing not just
the ArrayList<Particle> but the actual Particle objects themselves.

If the lifetimes are far more random with large gaps between groups of
extinguishing particles (a sparse array), you could use a
PriorityQueue<Particle> with a comparitor sorting the particle's age up.
  Removing extinguished particles is O(log(n)) which is better than
removing items one at a time from an ArrayList (which is O(n)).