iteration blues

Discussion in 'Java' started by bob, Nov 3, 2011.

  1. bob

    bob Guest

    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.
     
    bob, Nov 3, 2011
    #1
    1. Advertisements

  2. 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.
     
    Knute Johnson, Nov 3, 2011
    #2
    1. Advertisements

  3. 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...
     
    Henk van Voorthuijsen, Nov 3, 2011
    #3
  4. bob

    Lew Guest

    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?
    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").
     
    Lew, Nov 3, 2011
    #4
  5. bob

    Roedy Green Guest

    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.
     
    Roedy Green, Nov 3, 2011
    #5
  6. bob

    Lew Guest

    Why? What do your measurements tell you? What is not working because of the time this method takes?
    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.
     
    Lew, Nov 3, 2011
    #6
  7. 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)).
     
    Travers Naran, Nov 4, 2011
    #7
  8. 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
     
    Robert Klemme, Nov 4, 2011
    #8
  9. Granted. But this was not the case with the OP's code snippet.

     If your algorithm is:
    Exactly.
     
    Henk van Voorthuijsen, Nov 4, 2011
    #9
  10. bob

    Lew Guest

    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?
     
    Lew, Nov 4, 2011
    #10
  11. bob

    bob Guest

    Just what I needed. Thanks.
     
    bob, Nov 4, 2011
    #11
  12. 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
     
    Robert Klemme, Nov 4, 2011
    #12
  13. bob

    Arne Vajhøj Guest

    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
     
    Arne Vajhøj, Nov 5, 2011
    #13
  14. bob

    Arne Vajhøj Guest

    Is the enhanced for loop available in ME?

    Arne
     
    Arne Vajhøj, Nov 5, 2011
    #14
  15. bob

    Eric Sosman Guest

    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.
     
    Eric Sosman, Nov 5, 2011
    #15
  16. bob

    Lew Guest

    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.
     
    Lew, Nov 5, 2011
    #16
  17. bob

    spk Guest

    how come seen to brains fallow sense?
    Derbyshire codes yo ass. Period [hic]
     
    spk, Nov 5, 2011
    #17
  18. bob

    bob Guest

    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.
     
    bob, Nov 5, 2011
    #18
  19. bob

    Eric Sosman Guest

    The same could be said for List.add().
     
    Eric Sosman, Nov 5, 2011
    #19
  20. bob

    Lew Guest

    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.
     
    Lew, Nov 5, 2011
    #20
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.