Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #9508

Re: iteration blues

Show all headers | View raw

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)).

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

iteration blues bob <bob@coolgroups.com> - 2011-11-03 08:37 -0700
  Re: iteration blues Knute Johnson <nospam@knutejohnson.com> - 2011-11-03 08:51 -0700
    Re: iteration blues Lew <lewbloch@gmail.com> - 2011-11-03 09:32 -0700
      Re: iteration blues Arne Vajhøj <arne@vajhoej.dk> - 2011-11-04 21:00 -0400
        Re: iteration blues spk <jhic@speak.invalid> - 2011-11-05 07:48 -0400
  Re: iteration blues Henk van Voorthuijsen <voorth@xs4all.nl> - 2011-11-03 09:31 -0700
    Re: iteration blues Lew <lewbloch@gmail.com> - 2011-11-03 13:50 -0700
      Re: iteration blues Henk van Voorthuijsen <voorth@xs4all.nl> - 2011-11-04 08:07 -0700
    Re: iteration blues Arne Vajhøj <arne@vajhoej.dk> - 2011-11-04 21:02 -0400
  Re: iteration blues Roedy Green <see_website@mindprod.com.invalid> - 2011-11-03 10:08 -0700
  Re: iteration blues Travers Naran <tnaran@gmail.com> - 2011-11-03 22:22 -0700
  Re: iteration blues Robert Klemme <shortcutter@googlemail.com> - 2011-11-04 10:34 +0100
    Re: iteration blues Lew <lewbloch@gmail.com> - 2011-11-04 10:46 -0700
      Re: iteration blues Robert Klemme <shortcutter@googlemail.com> - 2011-11-04 23:55 +0100
        Re: iteration blues Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-11-04 21:06 -0400
        Re: iteration blues Lew <lewbloch@gmail.com> - 2011-11-04 20:30 -0700
        Re: iteration blues bob <bob@coolgroups.com> - 2011-11-05 12:40 -0700
          Re: iteration blues Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-11-05 16:14 -0400
            Re: iteration blues Lew <lewbloch@gmail.com> - 2011-11-05 13:41 -0700
    Re: iteration blues bob <bob@coolgroups.com> - 2011-11-04 13:42 -0700

csiph-web