Removing Elements from a Vector

Discussion in 'Java' started by Helge Richter, Feb 27, 2004.

  1. I'm trying to optimize my application for speed.
    Basically what I'm doing is adding Elements which need to be informed of
    a Tick (a specifc amount of time) to an Vector and remove them when
    they're finished.

    My First aproach was:
    for (int i = 0; i < tickables.size(); i++) {
    tickable t = (tickable) tickables.elementAt(i);
    t.tick(timediff, this);
    if (t.canBeRemoved())
    tickables.remove(t);
    }
    }

    This obviously skips a tickable when the one in front of it was removed.

    What's the best thing to do in this case?

    Reduce i by one and check if I'm still within the Vector-bounds?
    Do a clone of the Vector and only remove from the "real" vector?

    I'll want to do that during a paint method, so I'm trying to make it as
    cpu friendly as possible..

    Thx for your help...
     
    Helge Richter, Feb 27, 2004
    #1
    1. Advertising

  2. "Helge Richter" <> wrote in message
    news:c1nknc$3v8$00$-online.com...
    > I'm trying to optimize my application for speed.
    > Basically what I'm doing is adding Elements which need to be informed of
    > a Tick (a specifc amount of time) to an Vector and remove them when
    > they're finished.
    >
    > My First aproach was:
    > for (int i = 0; i < tickables.size(); i++) {
    > tickable t = (tickable) tickables.elementAt(i);
    > t.tick(timediff, this);
    > if (t.canBeRemoved())
    > tickables.remove(t);
    > }
    > }
    >
    > This obviously skips a tickable when the one in front of it was removed.
    >
    > What's the best thing to do in this case?
    >
    > Reduce i by one and check if I'm still within the Vector-bounds?
    > Do a clone of the Vector and only remove from the "real" vector?
    >
    > I'll want to do that during a paint method, so I'm trying to make it as
    > cpu friendly as possible..
    >
    > Thx for your help...


    Well, starting with the basics -- does it have to be a Vector? In other
    words, does it have to be synchronized? If not, you are probably better off
    going with an ArrayList, which is unsynchronized but faster. It appears
    that you need something within the Collections framework, so moving towards
    an array is probably overkill at this point.

    The approach that I would probably take is to create a temporary Collection
    of items that need to be removed and then remove them afterwards.

    // assuming tickables is arraylist

    ArrayList toRemove = new ArrayList(tickables.size()); // set the capacity to
    avoid expensive in-iteration resizing.
    for (int i=0, n=tickables.size(); i < n; i++) {
    tickable t = (tickable)tickabled.get(i);
    t.tick(timediff,this);
    if (t.canBeRemoved()) {
    toRemove.add(t);
    }
    }
    tickables.removeAll(toRemove);

    When your tickables is a reasonable size, I don't see this as adversely
    affecting your performance (maintaining a separate collection).

    -CV
     
    Collin VanDyck, Feb 27, 2004
    #2
    1. Advertising

  3. Helge Richter

    Suresh Guest

    [ .. snip ..]

    >
    > My First aproach was:
    > for (int i = 0; i < tickables.size(); i++) {
    > tickable t = (tickable) tickables.elementAt(i);
    > t.tick(timediff, this);
    > if (t.canBeRemoved())
    > tickables.remove(t);
    > }
    > }
    >
    > This obviously skips a tickable when the one in front of it was removed.
    >
    > What's the best thing to do in this case?


    [.. snip ..]

    for (int i = 0; i < tickables.size(); ) { // i++ removed
    tickable t = (tickable) tickables.elementAt(i);
    t.tick(timediff, this);
    if (t.canBeRemoved())
    tickables.remove(t);
    }else{ // increament
    i only if the element is not removed
    i++;
    }
    }
     
    Suresh, Feb 27, 2004
    #3
  4. Helge Richter

    Suresh Guest

    "Suresh" <no-emails> wrote in message
    news:...
    > [ .. snip ..]
    >
    > >
    > > My First aproach was:
    > > for (int i = 0; i < tickables.size(); i++) {
    > > tickable t = (tickable) tickables.elementAt(i);
    > > t.tick(timediff, this);
    > > if (t.canBeRemoved())
    > > tickables.remove(t);
    > > }
    > > }
    > >
    > > This obviously skips a tickable when the one in front of it was removed.
    > >
    > > What's the best thing to do in this case?

    >
    > [.. snip ..]
    >
    > for (int i = 0; i < tickables.size(); ) { // i++

    removed
    > tickable t = (tickable) tickables.elementAt(i);
    > t.tick(timediff, this);
    > if (t.canBeRemoved())
    > tickables.remove(t);
    > }else{ //

    increament
    > i only if the element is not removed
    > i++;
    > }
    > }



    use tickables.removeElementAt(i) instead of remove(..). The former would
    remove the element that we are "looking" at, and the later would remove the
    first element that matches the object t (would be problem if there are
    duplicates, and is also slow).
     
    Suresh, Feb 27, 2004
    #4
  5. Helge Richter <> wrote:

    > I'm trying to optimize my application for speed.
    > Basically what I'm doing is adding Elements which need to be
    > informed of a Tick (a specifc amount of time) to an Vector and
    > remove them when they're finished.
    >
    > My First aproach was:
    > for (int i = 0; i < tickables.size(); i++) {
    > tickable t = (tickable) tickables.elementAt(i);
    > t.tick(timediff, this);
    > if (t.canBeRemoved())
    > tickables.remove(t);
    > }
    >}
    >
    > This obviously skips a tickable when the one in front of it was
    > removed.
    >
    > What's the best thing to do in this case?
    >
    > Reduce i by one and check if I'm still within the Vector-bounds?


    You don't need to check because the lowest i can go is -1, which gets
    incremented to 0 by the for loop.

    This algorithm is O(N^2) because removing a middle element from a
    Vector is O(N).

    > Do a clone of the Vector and only remove from the "real" vector?


    This algoritm is O(N^2) as well.

    > I'll want to do that during a paint method, so I'm trying to make
    > it as cpu friendly as possible..


    You could use another Vector with enought space for all tickables and
    add to it the tickables that can't be removed. Then just switch
    Vectors. This algorithm is O(N) because adding each individual
    tickable is O(1).

    If the order of tickables is not significant, you can store the last
    tickable in the current index and then do
    tickables.setSize(tickables.size()-1). This algorithm is O(N).

    --
    No address munging in use. I like the smell of nuked accounts in the
    morning.
     
    Timo Kinnunen, Feb 27, 2004
    #5
  6. Helge Richter

    Andrew Hobbs Guest

    "Helge Richter" <> wrote in message
    news:c1nknc$3v8$00$-online.com...
    > I'm trying to optimize my application for speed.
    > Basically what I'm doing is adding Elements which need to be informed of
    > a Tick (a specifc amount of time) to an Vector and remove them when
    > they're finished.
    >
    > My First aproach was:
    > for (int i = 0; i < tickables.size(); i++) {
    > tickable t = (tickable) tickables.elementAt(i);
    > t.tick(timediff, this);
    > if (t.canBeRemoved())
    > tickables.remove(t);
    > }
    > }


    How about going backwards.

    > for (int i = tickables.size() - 1; i > -1; i--) {
    > tickable t = (tickable) tickables.elementAt(i);
    > t.tick(timediff, this);
    > if (t.canBeRemoved())
    > tickables.remove(t);
    > }
    > }


    Andrew






    >
    > This obviously skips a tickable when the one in front of it was removed.
    >
    > What's the best thing to do in this case?
    >
    > Reduce i by one and check if I'm still within the Vector-bounds?
    > Do a clone of the Vector and only remove from the "real" vector?
    >
    > I'll want to do that during a paint method, so I'm trying to make it as
    > cpu friendly as possible..
    >
    > Thx for your help...
     
    Andrew Hobbs, Feb 28, 2004
    #6
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Tino
    Replies:
    1
    Views:
    8,916
    Jonathan Turkanis
    Feb 20, 2004
  2. Jason Heyes
    Replies:
    6
    Views:
    8,395
    Jason Heyes
    Nov 16, 2004
  3. Adam Hartshorne
    Replies:
    2
    Views:
    382
    Nitin Motgi
    Jan 27, 2006
  4. Replies:
    8
    Views:
    1,970
    Csaba
    Feb 18, 2006
  5. Replies:
    11
    Views:
    684
    Daniel T.
    Nov 24, 2006
Loading...

Share This Page