iteration blues

[bob]

So, I wrote this code for some particle effects:

package com.coolfone.particles;

import java.util.Iterator;
import java.util.Vector;

import javax.microedition.khronos.opengles.GL10;

public class FireManager {
static Vector<Particle> particles = new Vector<Particle>();

public static void startfire(float x, float y) {
for (int ctr = 0; ctr < 100; ctr++) {
Particle p = new Particle();
p.x = (float) (x + Math.random()-.5);
p.y = (float) (y + Math.random()-.5);
p.dx = (float) (Math.random()-.5)/4f;
p.dy = (float) (Math.random()-.5)/4f;
p.timeleft = (int) (Math.random() * 50 + 50);
particles.add(p);
}
}

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

}

public static void drawfire(GL10 gl) {
Iterator<Particle> i = particles.iterator();
while (i.hasNext()) {
Particle p = i.next();
p.draw(gl);
}
}

}

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.

 

[Knute Johnson]

So, I wrote this code for some particle effects:

package com.coolfone.particles;

import java.util.Iterator;
import java.util.Vector;

import javax.microedition.khronos.opengles.GL10;

public class FireManager {
static Vector<Particle> particles = new Vector<Particle>();

public static void startfire(float x, float y) {
for (int ctr = 0; ctr< 100; ctr++) {
Particle p = new Particle();
p.x = (float) (x + Math.random()-.5);
p.y = (float) (y + Math.random()-.5);
p.dx = (float) (Math.random()-.5)/4f;
p.dy = (float) (Math.random()-.5)/4f;
p.timeleft = (int) (Math.random() * 50 + 50);
particles.add(p);
}
}

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

}

public static void drawfire(GL10 gl) {
Iterator<Particle> i = particles.iterator();
while (i.hasNext()) {
Particle p = i.next();
p.draw(gl);
}
}

}

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.

while (i.hasNext()) {

Particle p = i.next();
p.move();
p.timeleft--;

while (--p.timeleft >= 0)
p.remove();

if (p.timeleft == 0) removelist.add(p);

I have a game at http://rabbitbrush.frazmtn.com/asteroids.html that
demonstrates this code. I think it is plenty quick for the type of
animation that is being done. See the source code on the link at the
bottom of the page.

 

[Henk van Voorthuijsen]

So, I wrote this code for some particle effects:

package com.coolfone.particles;

import java.util.Iterator;
import java.util.Vector;

import javax.microedition.khronos.opengles.GL10;

public class FireManager {
        static Vector<Particle> particles = new Vector<Particle>();

        public static void startfire(float x, float y) {
                for (int ctr = 0; ctr < 100; ctr++) {
                        Particle p = new Particle();
                        p.x = (float) (x + Math..random()-.5);
                        p.y = (float) (y + Math..random()-.5);
                        p.dx = (float) (Math.random()-.5)/4f;
                        p.dy = (float) (Math.random()-.5)/4f;
                        p.timeleft = (int) (Math.random() * 50 + 50);
                        particles.add(p);
                }
        }

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

        }

        public static void drawfire(GL10 gl) {
                Iterator<Particle> i = particles.iterator();
                while (i.hasNext()) {
                        Particle p = i.next();
                        p.draw(gl);
                }
        }

}

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.

all Vectors should be LinkedLists, I think. Since you're only adding
to the end of the list or terating over it, performance shouldn't be
an issue.

BTW, while loops over an iterator are obsolete since Java 1.5 came
out.
Consider using the enhanced for loop:
public static void drawfire(GL10 gl) {
for ( Particle p: particles ) {
p.draw(gl);
}
}

No need to expose the iterator anymore...

 

[Lew]

PLEASE DO NOT INDENT WITH THE TAB CHARACTER FOR USENET!

Why use 'Vector', then? Isn't 'ArrayList' available in that environment?

Not if you use the iterator, but OTOH removing things from the middle of a large list can be slow, depending on the list implementation. Wouldn't a 'Set' work for this?

while (i.hasNext()) {

while (--p.timeleft >= 0)
p.remove();


I have a game at http://rabbitbrush.frazmtn.com/asteroids.html that
demonstrates this code. I think it is plenty quick for the type of
animation that is being done. See the source code on the link at the
bottom of the page.

The collections Javadocs indicate the big-O for different operations, generally. Pick one that has characteristics that match your use case.

I doubt that the synchronization inherent in 'Vector' will tie up too much time, but there's no noeed for it, is there? Aren't other 'List' implementations available? In the desktop world 'Vector' has been obsolete since 1998.

1998!

Since Java 1.2!

Thirteen years! That's 91 years in software years ("dog years").

 

[Roedy Green]

import java.util.Vector;

Vectors are obsolete.Use ArrayList. See
http://mindprod.com/jgloss/arraylist.html

you can iterate over an array list with

for ( Item a : someList );

See http://mindprod.com/jgloss/iterator.html
for how you can insert/delete while iterating.
--
Roedy Green Canadian Mind Products
http://mindprod.com
Capitalism has spurred the competition that makes CPUs faster and
faster each year, but the focus on money makes software manufacturers
do some peculiar things like deliberately leaving bugs and deficiencies
in the software so they can soak the customers for upgrades later.
Whether software is easy to use, or never loses data, when the company
has a near monopoly, is almost irrelevant to profits, and therefore
ignored. The manufacturer focuses on cheap gimicks like dancing paper
clips to dazzle naive first-time buyers. The needs of existing
experienced users are almost irrelevant. I see software rental as the
best remedy.

 

[Lew]

So, I wrote this code for some particle effects:

package com.coolfone.particles;

import java.util.Iterator;
import java.util.Vector;

import javax.microedition.khronos.opengles.GL10;

public class FireManager {
        static Vector<Particle> particles = new Vector<Particle>();
... [snip]
        public static void drawfire(GL10 gl) {
                Iterator<Particle> i = particles.iterator();
                while (i.hasNext()) {
                        Particle p = i.next();
                        p.draw(gl);
                }
        }

}

I'm concerned about inefficiency in the burnfire function.  Does

Why? What do your measurements tell you? What is not working because of the time this method takes?

all Vectors should be LinkedLists, I think. Since you're only adding
to the end of the list or terating over it, performance shouldn't be
an issue.

BTW, while loops over an iterator are obsolete since Java 1.5 came
out.
Consider using the enhanced for loop:
public static void drawfire(GL10 gl) {
for ( Particle p: particles ) {
p.draw(gl);
}
}

No need to expose the iterator anymore...

That is not true. There are all kinds of scenarios that require one to expose the iterator. It looks like the OP's scenario, for one, requires him to expose the iterator.

the issue is removal of items from the list as each is processed. If your algorithm is (pseudocoded):

for each item in collection
process item
delete item from collection

you will need the iterator. If your algorithm is:

for each item in collection
process items
empty the collection

then you will not need the iterator.

Talking in a single-threaded world here. I'm not going to delve into concurrency issues yet.

 

[Travers Naran]

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

 

[Robert Klemme]

So, I wrote this code for some particle effects:

package com.coolfone.particles;

import java.util.Iterator;
import java.util.Vector;

import javax.microedition.khronos.opengles.GL10;

public class FireManager {
static Vector<Particle> particles = new Vector<Particle>();

public static void startfire(float x, float y) {
for (int ctr = 0; ctr< 100; ctr++) {
Particle p = new Particle();
p.x = (float) (x + Math.random()-.5);
p.y = (float) (y + Math.random()-.5);
p.dx = (float) (Math.random()-.5)/4f;
p.dy = (float) (Math.random()-.5)/4f;
p.timeleft = (int) (Math.random() * 50 + 50);
particles.add(p);
}
}

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

}

public static void drawfire(GL10 gl) {
Iterator<Particle> i = particles.iterator();
while (i.hasNext()) {
Particle p = i.next();
p.draw(gl);
}
}

}

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.

I'm surprised nobody seems to mention Iterator.remove().

public static void burnfire() {
for (final Iterator<Particle> i = particles.iterator(); i.hasNext() {
final Particle p = i.next();
p.move();
p.timeleft--; // Direct access to member, bad!

if (p.timeleft == 0) {
iter.remove();
}
}
}

This can be used regardless of container type. Efficiency depends on
the ratio of removed elements. If you remove much and do not need
indexed access (i.e. via List.get(int)) you can use a LinkedList.
Otherwise use ArrayList as indicated already. There is no point in
using Vector these days any more.

And btw, do not be concerned about performance, measure it. Results may
be surprising.

Kind regards

robert

 

[Henk van Voorthuijsen]

So, I wrote this code for some particle effects:
package com.coolfone.particles;
import java.util.Iterator;
import java.util.Vector;
import javax.microedition.khronos.opengles.GL10;
public class FireManager {
        static Vector<Particle> particles = new Vector<Particle>();
... [snip]
        public static void drawfire(GL10 gl) {
                Iterator<Particle> i = particles.iterator();
                while (i.hasNext()) {
                        Particle p = i.next();
                        p.draw(gl);
                }
        }
}
I'm concerned about inefficiency in the burnfire function.  Does

Why?  What do your measurements tell you?  What is not working because of the time this method takes?

all Vectors should be LinkedLists, I think. Since you're only adding
to the end of the list or terating over it, performance shouldn't be
an issue.

BTW, while loops over an iterator are obsolete since Java 1.5 came
out.
Consider using the enhanced for loop:
  public static void drawfire(GL10 gl) {
    for ( Particle p: particles ) {
      p.draw(gl);
    }
  }

No need to expose the iterator anymore...

That is not true.  There are all kinds of scenarios that require one toexpose the iterator.  It looks like the OP's scenario, for one, requireshim to expose the iterator.

the issue is removal of items from the list as each is processed.  If your algorithm is (pseudocoded):

  for each item in collection
    process item
    delete item from collection

you will need the iterator.

Granted. But this was not the case with the OP's code snippet.

 If your algorithm is:

  for each item in collection
    process items
  empty the collection

then you will not need the iterator.

Exactly.

 

[Lew]

I'm surprised nobody seems to mention Iterator.remove().

You must have missed:
All right, yeah, it *did* require that one be at least minimally familiar with 'java.util.Iterator' to understand exactly why "you will need the iterator", but every Java programmer from beginner onward surely is aware of 'Iterator#remove()', right? Surely no one calling themselves a Java programmer could be ignorant of such a basic, fundamental, early concept in Java? Could they?

 

[bob]

I'm surprised nobody seems to mention Iterator.remove().

public static void burnfire() {
   for (final Iterator<Particle> i = particles.iterator(); i.hasNext() {
     final Particle p = i.next();
     p.move();
     p.timeleft--;  // Direct access to member, bad!

     if (p.timeleft == 0) {
       iter.remove();
     }
   }

}

This can be used regardless of container type.  Efficiency depends on
the ratio of removed elements.  If you remove much and do not need
indexed access (i.e. via List.get(int)) you can use a LinkedList.
Otherwise use ArrayList as indicated already.  There is no point in
using Vector these days any more.

And btw, do not be concerned about performance, measure it.  Results may
be surprising.

Kind regards

        robert

Just what I needed. Thanks.

 

[Robert Klemme]

You must have missed:

All right, yeah, it *did* require that one be at least minimally
familiar with 'java.util.Iterator' to understand exactly why "you
will need the iterator", but every Java programmer from beginner
onward surely is aware of 'Iterator#remove()', right? Surely no one
calling themselves a Java programmer could be ignorant of such a
basic, fundamental, early concept in Java? Could they?

Well... Judging from my experience Iterator.remove() seems to be less
known than the other methods of that interface - although not as much as
methods (and even the existence) of ListIterator. I would consider
this pretty basic knowledge as you did - probably in the same area as
the ternary operator - but empiricism often proves our assumptions
wrong.

Cheers

robert

 

[Arne Vajhøj]

Why use 'Vector', then? Isn't 'ArrayList' available in that environment?

I believe ArrayList is available for ME CDC but not for ME CLDC.

But Iterator is also only available for CDC, so ArrayList
should be there.

I doubt that the synchronization inherent in 'Vector' will tie up too much time, but there's no noeed for it, is there? Aren't other 'List' implementations available? In the desktop world 'Vector' has been obsolete since 1998.

1998!

Since Java 1.2!

Thirteen years! That's 91 years in software years ("dog years").

For ME it is not so much a matter of years but of profile/config.

Arne

 

[Arne Vajhøj]

all Vectors should be LinkedLists, I think. Since you're only adding
to the end of the list or terating over it, performance shouldn't be
an issue.

BTW, while loops over an iterator are obsolete since Java 1.5 came
out.
Consider using the enhanced for loop:
public static void drawfire(GL10 gl) {
for ( Particle p: particles ) {
p.draw(gl);
}
}

No need to expose the iterator anymore...

Is the enhanced for loop available in ME?

Arne

 

[Eric Sosman]

You must have missed:

All right, yeah, it *did* require that one be at least minimally
familiar with 'java.util.Iterator' to understand exactly why "you
will need the iterator", but every Java programmer from beginner
onward surely is aware of 'Iterator#remove()', right? Surely no one
calling themselves a Java programmer could be ignorant of such a
basic, fundamental, early concept in Java? Could they?

Well... Judging from my experience Iterator.remove() seems to be less
known than the other methods of that interface[...]

True. Java's designers ought to have known better than to
bloat an interface with *three* methods. That's at least one too
many for today's programmers to grasp. Maybe two too many, or
even more.

 

[Lew]

Well... Judging from my experience Iterator.remove() seems to be less
known than the other methods of that interface - although not as much as
methods (and even the existence) of ListIterator. I would consider
this pretty basic knowledge as you did - probably in the same area as
the ternary operator - but empiricism often proves our assumptions
wrong.

Just because ignorance is widespread doesn't mean that it's excusable. It's basic knowledge whether people bothered to learn their craft or not.

 

[spk]

I believe ArrayList is available for ME CDC but not for ME CLDC.

But Iterator is also only available for CDC, so ArrayList
should be there.


For ME it is not so much a matter of years but of profile/config.

Arne

how come seen to brains fallow sense?
Derbyshire codes yo ass. Period [hic]

 

[bob]

Well...  Judging from my experience Iterator.remove() seems to be less
known than the other methods of that interface - although not as much as
methods (and even the existence) of ListIterator.  I would consider
this pretty basic knowledge as you did - probably in the same area as
the ternary operator - but empiricism often proves our assumptions
wrong.

Cheers

        robert

Iterator.remove() is probably not well-known because it's an optional
operation. Also, I see no easy way to tell if a given container type
supports it other than to try it.

 

[Eric Sosman]

Iterator.remove() is probably not well-known because it's an optional
operation. Also, I see no easy way to tell if a given container type
supports it other than to try it.

The same could be said for List.add().

 

[Lew]

The same could be said for List.add().

Indeed, and for both cases there is a ridiculously easy way to tell if a given container type supports the operation: read the friggin' Javadocs!

If the container doesn't support the operation you need, don't use it.