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?

 
 
Daniele Futtorovic
Guest
Posts: n/a
 
      01-29-2008
On 29.01.2008 08:47, Lasse Reichstein Nielsen allegedly wrote:
> 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


I see. They've forgotten to modify the Javadoc accordingly, though. In
their AbstractCollection class they still write it's done using an
Iterator. Which, at that level, is correct, of course. They would have
to override it ArrayList solely for the doc, I suppose.


I started wondering why this hadn't been added to the core classes,
fired up the bugparade, and here we are:
<http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6529800>
.... is flagged as "Closed, fixed" (took them til 1.6!!).

The ArrayList class in my SDK doesn't contain any such implementation,
but it's 1.6.0_02 (yeah, I should update). However, I can't seem to find
the corresponding bugID in the release notes either:
<http://java.sun.com/javase/6/webnotes/ReleaseNotes.html>

:scratches head:

DF.
 
Reply With Quote
 
 
 
 
Boris Stumm
Guest
Posts: n/a
 
      01-29-2008

Kevin wrote:
> 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?


I do not think so, as stated in the other replies. An Iterator moves
from the beginning of the ArrayList to the end, so that the complete
operation will terminate in O(n^2). However, as long as speed is not
an issue (or the lists are small), this approach is the cleanest one.

The fastest way to check all elements in an ArrayList, and remove
some of them is probably the following (assuming that the list is NOT
SORTED!)

ArrayList list = ...;
for (int i = list.size() - 1; i >= 0; i--) {
if (elementNeedsToBeRemoved(list.get(i))) {
list.set(i, list.get(list.size() -1 ));
list.remove(list.size() - 1);
}
}

This will work in O(n).


 
Reply With Quote
 
 
 
 
Patricia Shanahan
Guest
Posts: n/a
 
      01-29-2008
Boris Stumm wrote:
> Kevin wrote:
>> 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?

>
> I do not think so, as stated in the other replies. An Iterator moves
> from the beginning of the ArrayList to the end, so that the complete
> operation will terminate in O(n^2). However, as long as speed is not
> an issue (or the lists are small), this approach is the cleanest one.


Isn't the iterator-based version O(n*(m+1)) where n is the length of the
list and m is the number of items being removed?

Whether this is equivalent to O(n), O(n^2), or something in between
depends on the relationship between n and m.

Patricia


 
Reply With Quote
 
Lasse Reichstein Nielsen
Guest
Posts: n/a
 
      01-30-2008
Patricia Shanahan <(E-Mail Removed)> writes:

> Isn't the iterator-based version O(n*(m+1)) where n is the length of the
> list and m is the number of items being removed?


It's O(n*m*k) where n is the size of the list, m is the number of
elements removed (it's an average, removing the first element is more
expensive than the last element), and k is the time it takes to check
whether an element is in the argument collection.

> Whether this is equivalent to O(n), O(n^2), or something in between
> depends on the relationship between n and m.


Worst case is O(n^2), so it's fair to use that as an upper bound on
the complexity of the algorithm.

/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
 
Patricia Shanahan
Guest
Posts: n/a
 
      01-30-2008
Lasse Reichstein Nielsen wrote:
> Patricia Shanahan <(E-Mail Removed)> writes:
>
>> Isn't the iterator-based version O(n*(m+1)) where n is the length of the
>> list and m is the number of items being removed?

>
> It's O(n*m*k) where n is the size of the list, m is the number of
> elements removed (it's an average, removing the first element is more
> expensive than the last element), and k is the time it takes to check
> whether an element is in the argument collection.


I don't understand why you multiply together m and k.

The cost of examining each element is O(n*k), and the cost of removing
the elements that need removing is O(n*m*j), where j is the cost of
shifting one element down the array. We can treat at least one of k and
j as being one, because constant factors don't affect complexity, so
that can reduce to O(n*k+n*m)=O(n*(k+m)). I was treating them both as
being one unit, so I reduced it to O(n*(m+1)).

>
>> Whether this is equivalent to O(n), O(n^2), or something in between
>> depends on the relationship between n and m.

>
> Worst case is O(n^2), so it's fair to use that as an upper bound on
> the complexity of the algorithm.
>
> /L


However, in many real applications of this sort of operation the number
of removed elements is very small, so I think it is important to
remember that the complexity depends on the removal rate.

Patricia
 
Reply With Quote
 
Lasse Reichstein Nielsen
Guest
Posts: n/a
 
      01-30-2008
Patricia Shanahan <(E-Mail Removed)> writes:

> Lasse Reichstein Nielsen wrote:


>> It's O(n*m*k)

....
> I don't understand why you multiply together m and k.


Neither do I, now that you mention it. I should have said O(n*m+n*k),
but I was too busy multiplying

> The cost of examining each element is O(n*k), and the cost of removing
> the elements that need removing is O(n*m*j), where j is the cost of
> shifting one element down the array. We can treat at least one of k and
> j as being one, because constant factors don't affect complexity, so
> that can reduce to O(n*k+n*m)=O(n*(k+m)). I was treating them both as
> being one unit, so I reduced it to O(n*(m+1)).


Indeed.

>> Worst case is O(n^2), so it's fair to use that as an upper bound on
>> the complexity of the algorithm.


> However, in many real applications of this sort of operation the number
> of removed elements is very small, so I think it is important to
> remember that the complexity depends on the removal rate.


Nah, being practical shouldn't get in the way of a good theory
But ofcourse, you are right. Knowing the actual problem being solved
is more important than general theory. Like Bubble sort being the best
sorting algorithm ... for almost sorted lists.

/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
 
Roedy Green
Guest
Posts: n/a
 
      01-30-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:


Another faster method if the lists are long is to copy leaving behind
the undesired elements.

This is the technique used in the SortedArrayList class.

See http://mindprod.com/products2.html#SORTED
--
Roedy Green, Canadian Mind Products
The Java Glossary, http://mindprod.com
 
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