Removing Elements from a Vector

[Helge Richter]

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

 

[Collin VanDyck]

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

 

[Suresh]

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

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

 

[Timo Kinnunen]

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

 

[Andrew Hobbs]

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.