Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > ArrayList.Iterator.remove()

Reply
Thread Tools

ArrayList.Iterator.remove()

 
 
Donkey Hottie
Guest
Posts: n/a
 
      06-30-2009

Just noticed a 'hidden feature of Java'

Removing items an ArrayList (at least with an Iterator) takes ages.

Better - while not obvious - solution is to create an new ArrayList with the
remaining elements.

So it seems. removal is futile.


 
Reply With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      06-30-2009
Donkey Hottie wrote:
>
> Just noticed a 'hidden feature of Java'
>
> Removing items an ArrayList (at least with an Iterator) takes ages.


If the ArrayList contains a lot of items, yes. No, wait,
for "yes" read "of course" or even "obviously."

> Better - while not obvious - solution is to create an new ArrayList with
> the remaining elements.


Depends on how many items there are, how many you're
deleting, and where they're positioned.

> So it seems. removal is futile.


Nonsense. No, wait, for "nonsense" read "balderdash" or
even "baloney." If you brush your teeth with a broom and have
an unpleasant experience, it does not follow that brushing your
teeth is futile.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)lid
 
Reply With Quote
 
 
 
 
Lew
Guest
Posts: n/a
 
      06-30-2009
On Jun 30, 4:50*pm, "Donkey Hottie" <(E-Mail Removed)> wrote:
> Just noticed a 'hidden feature of Java'
>
> Removing items an ArrayList (at least with an Iterator) takes ages.
>
> Better - while not obvious - solution is to create an new ArrayList with the
> remaining elements.
>
> So it seems. removal is futile.


Not so hidden, really.

<http://java.sun.com/javase/6/docs/api/java/util/ArrayList.html>
> The size, isEmpty, get, set, iterator, and listIterator operations run
> in constant time. The add operation runs in amortized constant time, that
> is, adding n elements requires O(n) time. All of the other operations run
> in linear time (roughly speaking).
>


That's for *each* removal.

That's because 'ArrayList#remove()' (through an iterator or
otherwise)
> [s]hifts any subsequent elements to the left (subtracts one from their indices).

<http://java.sun.com/javase/6/docs/ap...st.html#remove
(int)>

The documentation for the collection classes usually indicates the big-
O time of the common operations.

I would expect copying to take longer, however, depending on where one
is in the iteration. Perhaps there's extra machinery in the iterator
logic to normalize the iterator's position within the list.

Or are you copying individual elements as you iterate, skipping over
the "removed" ones? That should be much faster than multiple
removals.

--
Lew
 
Reply With Quote
 
Donkey Hottie
Guest
Posts: n/a
 
      06-30-2009
"Eric Sosman" <(E-Mail Removed)> wrote in
message news:h2dv0m$350$(E-Mail Removed)-september.org
> Donkey Hottie wrote:
>>
>> Just noticed a 'hidden feature of Java'
>>
>> Removing items an ArrayList (at least with an Iterator)
>> takes ages.

>
> If the ArrayList contains a lot of items, yes. No,
> wait, for "yes" read "of course" or even "obviously."
>
>> Better - while not obvious - solution is to create an
>> new ArrayList with the remaining elements.

>
> Depends on how many items there are, how many you're
> deleting, and where they're positioned.
>
>> So it seems. removal is futile.

>
> Nonsense. No, wait, for "nonsense" read "balderdash"
> or even "baloney." If you brush your teeth with a broom
> and have an unpleasant experience, it does not follow
> that brushing your teeth is futile.


* Loaded 223673 addresses
* Sorting...
* Merging...
* Merged 22577 address ranges.

Removed 22577 items from 223673. Don't know it that is many or not.


 
Reply With Quote
 
Donkey Hottie
Guest
Posts: n/a
 
      06-30-2009
"Lew" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)
..
>
> I would expect copying to take longer, however, depending
> on where one
> is in the iteration. Perhaps there's extra machinery in
> the iterator
> logic to normalize the iterator's position within the
> list.
>
> Or are you copying individual elements as you iterate,
> skipping over
> the "removed" ones? That should be much faster than
> multiple
> removals.


Well, after I discovered the slow speed of removal, I rewrote the method now
creates a new List and always just adds the suitable elements and replaces
the List instance.

10% of the original List seem to be removed, and it is 1000 times faster
now.


 
Reply With Quote
 
Donkey Hottie
Guest
Posts: n/a
 
      06-30-2009
"Patricia Shanahan" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) m
>
> Also, if access to a List is dominated by iterators with
> remove, LinkedList is likely to be more efficient than
> ArrayList. ArrayList is optimized for indexed access.
>


Thanks!

I was not aware of that kind of a List being in Java library (thought it
would be an Apache solution or something).

LinkedList now belongs to my toolkit allright.




 
Reply With Quote
 
Lew
Guest
Posts: n/a
 
      06-30-2009
"Donkey Hottie" wrote:
> * Loaded 223673 addresses
> * Sorting...
> * Merging...
> * Merged 22577 address ranges.
>
> Removed 22577 items from 223673. Don't know it that is many or not.


I would expect, based on the extremely non-hidden documentation of
ArrayList, for that to take time roughly

T = (22577 * 223673 / 2) * k

where 'k' is the time to copy an element from one array location to
another.

If 'k' is around 100 nanoseconds, T would be around 252 seconds, or
somewhat over 4 minutes. A 'k' of 10 ns would require about 25
seconds of removal time.

--
Lew
 
Reply With Quote
 
Donkey Hottie
Guest
Posts: n/a
 
      06-30-2009
"Lew" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)
> "Donkey Hottie" wrote:
>> * Loaded 223673 addresses
>> * Sorting...
>> * Merging...
>> * Merged 22577 address ranges.
>>
>> Removed 22577 items from 223673. Don't know it that is
>> many or not.

>
> I would expect, based on the extremely non-hidden
> documentation of ArrayList, for that to take time roughly
>
> T = (22577 * 223673 / 2) * k
>
> where 'k' is the time to copy an element from one array
> location to another.
>
> If 'k' is around 100 nanoseconds, T would be around 252
> seconds, or somewhat over 4 minutes. A 'k' of 10 ns
> would require about 25 seconds of removal time.


Great

I'm writing a rival to a Windows application, which does that merge at least
5 minutes in a Athlon XP 1900+ machine. My Java implementation does it now
in ten seconds in a Pentium Pro 3 machine.

And I though as a C++ programmer (for 10 years) that Java is sluggish..




 
Reply With Quote
 
Knute Johnson
Guest
Posts: n/a
 
      06-30-2009
Donkey Hottie wrote:
> "Lew" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)
> .
>>
>> I would expect copying to take longer, however, depending
>> on where one
>> is in the iteration. Perhaps there's extra machinery in
>> the iterator
>> logic to normalize the iterator's position within the
>> list.
>>
>> Or are you copying individual elements as you iterate,
>> skipping over
>> the "removed" ones? That should be much faster than
>> multiple
>> removals.

>
> Well, after I discovered the slow speed of removal, I rewrote the method
> now creates a new List and always just adds the suitable elements and
> replaces the List instance.
>
> 10% of the original List seem to be removed, and it is 1000 times faster
> now.


I'd be really curious to know if using the LinkedList is significantly
faster than ArrayList. If you try it, please post back.

Thanks,

--

Knute Johnson
email s/nospam/knute2009/

--
Posted via NewsDemon.com - Premium Uncensored Newsgroup Service
------->>>>>>http://www.NewsDemon.com<<<<<<------
Unlimited Access, Anonymous Accounts, Uncensored Broadband Access
 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      06-30-2009
Donkey Hottie wrote:
> "Lew" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)
>> "Donkey Hottie" wrote:
>>> * Loaded 223673 addresses
>>> * Sorting...
>>> * Merging...
>>> * Merged 22577 address ranges.
>>>
>>> Removed 22577 items from 223673. Don't know it that is
>>> many or not.

>>
>> I would expect, based on the extremely non-hidden
>> documentation of ArrayList, for that to take time roughly
>>
>> T = (22577 * 223673 / 2) * k
>>
>> where 'k' is the time to copy an element from one array
>> location to another.
>>
>> If 'k' is around 100 nanoseconds, T would be around 252
>> seconds, or somewhat over 4 minutes. A 'k' of 10 ns
>> would require about 25 seconds of removal time.

>
> Great
>
> I'm writing a rival to a Windows application, which does that merge at
> least 5 minutes in a Athlon XP 1900+ machine. My Java implementation
> does it now in ten seconds in a Pentium Pro 3 machine.
>
> And I though as a C++ programmer (for 10 years) that Java is sluggish..


As almost always, you get a lot more improvement out of
choosing the right data structures and algorithms than out of
shaving cycles or even out of choosing implementation language.

You haven't fully explained what you're trying to do, but
at a guess you're collecting a big pile of numeric "addresses"
from somewhere, sorting them, possibly eliminating duplicates,
and finally combining groups of neighboring addresses into
"ranges." ArrayList doesn't strike me as a good candidate for
the elimination and combining stages, precisely because of the
time required to squeeze out the vacated slots. If you *must*
use ArrayList (for reasons the sketchy problem description does
not reveal), consider working on it from the end toward the
beginning instead of from the beginning toward the end. (But
since you're removing only 10% of the total, I don't hold out
a lot of hope for a huge improvement therefrom.)

--
Eric Sosman
(E-Mail Removed)lid
 
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




Advertisments