Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Best way to loop through ArrayList and remove elements on the way?

Reply
Thread Tools

Best way to loop through ArrayList and remove elements on the way?

 
 
Kevin
Guest
Posts: n/a
 
      01-28-2008
Hi guys,

Just want to confirm:

for a ArrayList, in single thread mode (only one thread will access
this ArrayList), what is the best way to:

1) loop through all the element of this arraylist (for example, each
item of it is a String).
2) do some check on each item (for example, check if it equals to
"abc").
3) remove this item from the arraylist if the above check is true.

Is using iterator() and then use iterator.remove() the best way?
Like:

for (Iterator it = myarraylist.iterator(); it.hasNext(); )
{
String s = (String) it.next();
if (s.equals("abc"))
{
it.remove();
}
};


Thanks a log.

 
Reply With Quote
 
 
 
 
Daniele Futtorovic
Guest
Posts: n/a
 
      01-28-2008
On 28.01.2008 23:46, Kevin allegedly wrote:
> Hi guys,
>
> Just want to confirm:
>
> for a ArrayList, in single thread mode (only one thread will access
> this ArrayList), what is the best way to:
>
> 1) loop through all the element of this arraylist (for example, each
> item of it is a String). 2) do some check on each item (for example,
> check if it equals to "abc"). 3) remove this item from the arraylist
> if the above check is true.
>
> Is using iterator() and then use iterator.remove() the best way?
> Like:
>
> for (Iterator it = myarraylist.iterator(); it.hasNext(); ) { String s
> = (String) it.next(); if (s.equals("abc")) { it.remove(); } };
>
>
> Thanks a log.
>


"Best" with respects to what?

The code above will be more efficient on a LinkedList than on an
ArrayList. As a general rule, when doing filtering operations
(conditional removing/keeping) on array-backed structures (ArrayList,
StringBuffer, etc.), it is more efficient, especially if the structure
is big, to copy those elements which are to be kept into a new
structure, and then to discard the old one, instead of perform multiple
deletions. Only if there would be a significant number (more than a
couple) of deletions, of course. Your mileage may vary, but it takes a
lot off the CPU and adds only little memory overhead.

DF.
 
Reply With Quote
 
 
 
 
Lasse Reichstein Nielsen
Guest
Posts: n/a
 
      01-28-2008
Kevin <(E-Mail Removed)> writes:

> for a ArrayList, in single thread mode (only one thread will access
> this ArrayList), what is the best way to:
>
> 1) loop through all the element of this arraylist (for example, each
> item of it is a String).
> 2) do some check on each item (for example, check if it equals to
> "abc").
> 3) remove this item from the arraylist if the above check is true.


First of all, an ArrayList takes linear time to remove a single
element, so repeated removal is a bad idea.

Either use a LinkedList, which can remove in constant time during
iteration, or first collect the elements in a HashSet and then remove
them at the end using Collection.removeAll(Collection). I suggest the
latter.

For ArrayList, the removeAll method takes time proportional to the
size of the list times the lookup time for the argument collection.
Using a HashSet as argument should minimize the time it takes.

If you only remove a few values, any collection will probably suffice.

I.e., either:

LinkedList tmpLinkedList = new LinkedList(myarraylist);
for(Iterator iter = tmpLinkedList.iterator(); iter.hasNext() {
if (test(iter.next)) { iter.remove(); }
}
myarraylist.clear();
myarraylist.addAll(tmpLinkedList);

or

HashSet toRemove = new HashSet();
for(Iterator iter = myarraylist.iterator(); iter.hasNext() {
Object elem = iter.next();
if (test(elem)) { toRemove.add(elem); }
}
myarraylist.removeAll(toRemove);

This is assuming the test is complicated. If it's just equality
check, then you might be able to use removeAll directly.

> Is using iterator() and then use iterator.remove() the best way?


For the above reasons, I'd say no.

> Like:
>
> for (Iterator it = myarraylist.iterator(); it.hasNext(); )
> {
> String s = (String) it.next();
> if (s.equals("abc"))
> {
> it.remove();
> }
> };


In this simple case, where you only compare for equality (and even to
only a single value), it would suffice to do:
myarraylist.removeAll(Collections.singletonSet("ab c"));
If you have more values, but still only do equality checks, just create
a collection and remove them all.
/L
--
Lasse Reichstein Nielsen - http://www.velocityreviews.com/forums/(E-Mail Removed)
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
 
Reply With Quote
 
Kevin
Guest
Posts: n/a
 
      01-29-2008
Thanks guys!

So remove(object) is linear time with respect to the ArrayList's
lenght, right?

Is using iterator.remove() still O(n) time? I think the iterator
already keep the "reference" to the current item (for example, in my
previous example code, it "points" to the current item already), and
if we want to remove it, there is no need to look for it in the
arraylist, so it just removes it directly, which should be constant
time, right?

Thanks.

 
Reply With Quote
 
Daniele Futtorovic
Guest
Posts: n/a
 
      01-29-2008
On 29.01.2008 00:30, Lasse Reichstein Nielsen allegedly wrote:
> Kevin <(E-Mail Removed)> writes:
>
>> for a ArrayList, in single thread mode (only one thread will access
>> this ArrayList), what is the best way to:
>>
>> 1) loop through all the element of this arraylist (for example,
>> each item of it is a String). 2) do some check on each item (for
>> example, check if it equals to "abc"). 3) remove this item from the
>> arraylist if the above check is true.

>
> First of all, an ArrayList takes linear time to remove a single
> element, so repeated removal is a bad idea.
>
> Either use a LinkedList, which can remove in constant time during
> iteration, or first collect the elements in a HashSet and then remove
> them at the end using Collection.removeAll(Collection). I suggest
> the latter.
>
> For ArrayList, the removeAll method takes time proportional to the
> size of the list times the lookup time for the argument collection.
> Using a HashSet as argument should minimize the time it takes.


I don't quite understand that advice. The docs for removeAll(Collection)
in AbstractCollection (neither AbstractList nor ArrayList override that
method) state:
"This implementation iterates over this collection, checking each
element returned by the iterator in turn to see if it's contained in the
specified collection. If it's so contained, it's removed from this
collection with the iterator's remove method".

Which is what the OP was doing -- except for the part of the lookup.
Sure, using removeAll is cleaner, and, as opposed to removing one "type"
(as defined by equality relations in this context) at once, it is
superior. But only in that it avoids multiple iterations. The most
itensive operation here, however, isn't the iteration, but the removal.
Which your suggestion does not affect.

As far as I can surmise, there are only two ways of substantially
improving the algorithm: either switch to a sequential list (and then
using removeAll would be a good idea too), or give up on having the
filtering modify the list at all, but rather yield a new one.

DF.
 
Reply With Quote
 
Patricia Shanahan
Guest
Posts: n/a
 
      01-29-2008
Kevin wrote:
> Hi guys,
>
> Just want to confirm:
>
> for a ArrayList, in single thread mode (only one thread will access
> this ArrayList), what is the best way to:
>
> 1) loop through all the element of this arraylist (for example, each
> item of it is a String).
> 2) do some check on each item (for example, check if it equals to
> "abc").
> 3) remove this item from the arraylist if the above check is true.
>
> Is using iterator() and then use iterator.remove() the best way?
> Like:
>
> for (Iterator it = myarraylist.iterator(); it.hasNext(); )
> {
> String s = (String) it.next();
> if (s.equals("abc"))
> {
> it.remove();
> }
> };
>
>
> Thanks a log.
>


From the point of view of coding simplicity, I think it is the best way.

If it becomes a performance bottleneck, investigate whether you should
switch to LinkedList or take other steps to reduce the cost.

Patricia
 
Reply With Quote
 
Roedy Green
Guest
Posts: n/a
 
      01-29-2008
On Mon, 28 Jan 2008 14:46:35 -0800 (PST), Kevin
<(E-Mail Removed)> wrote, quoted or indirectly quoted
someone who said :

>Is using iterator() and then use iterator.remove() the best way?
>Like:


yes.
--
Roedy Green, Canadian Mind Products
The Java Glossary, http://mindprod.com
 
Reply With Quote
 
Mike Schilling
Guest
Posts: n/a
 
      01-29-2008
Kevin wrote:
> Thanks guys!
>
> So remove(object) is linear time with respect to the ArrayList's
> lenght, right?


Yes. So is remove(int), but remove(object) has a larger constant.
remove(m) for an ArrayList of size n needs to:

1. copy the references numbered from m+1 to n-1 to the positions m
to n-2 respectively
2. Set the reference at m-1 to null.

remove(o) has to

a. Find the index m of the first o in the ArrayList
b. perform steps 1 and 2 above.

>
> Is using iterator.remove() still O(n) time?


Yes, because it amounts to remove(int).


 
Reply With Quote
 
Kevin McMurtrie
Guest
Posts: n/a
 
      01-29-2008
In article
<(E-Mail Removed)>,
Kevin <(E-Mail Removed)> wrote:

> Hi guys,
>
> Just want to confirm:
>
> for a ArrayList, in single thread mode (only one thread will access
> this ArrayList), what is the best way to:
>
> 1) loop through all the element of this arraylist (for example, each
> item of it is a String).
> 2) do some check on each item (for example, check if it equals to
> "abc").
> 3) remove this item from the arraylist if the above check is true.
>
> Is using iterator() and then use iterator.remove() the best way?
> Like:
>
> for (Iterator it = myarraylist.iterator(); it.hasNext(); )
> {
> String s = (String) it.next();
> if (s.equals("abc"))
> {
> it.remove();
> }
> };
>
>
> Thanks a log.


Removing from ArrayList requires shifting elements so it can be slow.
If an ArrayList is still the right tool, it may be faster in some cases
to build a new list based on what wouldn't be removed. If you can't
rebuild, you can still get an improvement by going backwards through the
list.

--
I don't read Google's spam. Reply with another service.
 
Reply With Quote
 
Lasse Reichstein Nielsen
Guest
Posts: n/a
 
      01-29-2008
Daniele Futtorovic <(E-Mail Removed)> writes:

> I don't quite understand that advice. The docs for removeAll(Collection)
> in AbstractCollection (neither AbstractList nor ArrayList override that
> method) state:
> "This implementation iterates over this collection, checking each
> element returned by the iterator in turn to see if it's contained in the
> specified collection. If it's so contained, it's removed from this
> collection with the iterator's remove method".


True, my mistake.

I was looking at the GNU Classpath implementation of ArrayList,
which does implement an optimized removeAll, without noticing
that it wasn't the Sun version.
<URL:http://www.docjar.com/html/api/java/util/ArrayList.java.html>

/L
--
Lasse Reichstein Nielsen - (E-Mail Removed)
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
 
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
Triple nested loop python (While loop insde of for loop inside ofwhile loop) Isaac Won Python 9 03-04-2013 10:08 AM
Does the clone() method of ArrayList<> make a copy of the objects in the ArrayList? xz Java 16 08-04-2007 10:33 PM
a class inherited from ArrayList, is saved to ViewState, why the type of the object read from ViewSate is not the class, but the parent, ArrayList leal ting ASP .Net 1 02-10-2004 07:45 PM
writeObject with ArrayList of ArrayList? Kaidi Java 4 01-03-2004 08:16 PM
Iterate through ArrayList using an another ArrayList Saravanan Rathinavelu ASP .Net 3 08-19-2003 07:03 AM



Advertisments