# Removing Elements from a Vector

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

1. ### Helge RichterGuest

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

Helge Richter, Feb 27, 2004

2. ### Collin VanDyckGuest

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

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()) {
}
}
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

3. ### SureshGuest

[ .. 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
4. ### SureshGuest

"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
5. ### Timo KinnunenGuest

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
6. ### Andrew HobbsGuest

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

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