Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Removing Elements from a Vector

Reply
Thread Tools

Removing Elements from a Vector

 
 
Helge Richter
Guest
Posts: n/a
 
      02-27-2004
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...
 
Reply With Quote
 
 
 
 
Collin VanDyck
Guest
Posts: n/a
 
      02-27-2004
"Helge Richter" <(E-Mail Removed)> wrote in message
news:c1nknc$3v8$00$(E-Mail Removed)-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



 
Reply With Quote
 
 
 
 
Suresh
Guest
Posts: n/a
 
      02-27-2004
[ .. 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++;
}
}


 
Reply With Quote
 
Suresh
Guest
Posts: n/a
 
      02-27-2004

"Suresh" <no-emails> wrote in message
news:(E-Mail Removed)...
> [ .. 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).




 
Reply With Quote
 
Timo Kinnunen
Guest
Posts: n/a
 
      02-27-2004
Helge Richter <(E-Mail Removed)> 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.
 
Reply With Quote
 
Andrew Hobbs
Guest
Posts: n/a
 
      02-28-2004

"Helge Richter" <(E-Mail Removed)> wrote in message
news:c1nknc$3v8$00$(E-Mail Removed)-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...



 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Removing elements from vector kaferro@hotmail.com C++ 11 11-24-2006 03:01 AM
Free memory allocate by a STL vector, vector of vector, map of vector Allerdyce.John@gmail.com C++ 8 02-18-2006 12:48 AM
Removing a vector element using std::swap and std::vector::resize. Jason Heyes C++ 8 01-15-2006 10:40 PM
Removing elements from std::vector. Jason Heyes C++ 6 11-16-2004 02:23 AM
adding/removing elements from std::vector Tino C++ 1 02-20-2004 10:51 PM



Advertisments