ArrayList.Iterator.remove()
 

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.

Re: ArrayList.Iterator.remove()
 

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
esosman@ieee-dot-org.invalid

Re: ArrayList.Iterator.remove()
 

On Jun 30, 4:50*pm, "Donkey Hottie" <don...@fred.pp.fi> 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

Re: ArrayList.Iterator.remove()
 

"Eric Sosman" <esosman@ieee-dot-org.invalid> wrote in
message news:h2dv0m$350$1@news.eternal-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.

Re: ArrayList.Iterator.remove()
 

"Lew" <lew@lewscanon.com> wrote in message
news:98f02bfe-752f-41a2-8ab0-abac861efca0@g6g2000vbr.googlegroups.com
..
>
> 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.

Re: ArrayList.Iterator.remove()
 

"Patricia Shanahan" <pats@acm.org> wrote in message
news:EamdnSEBOsIoHdfXnZ2dnUVZ_vqdnZ2d@earthlink.co 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.

Re: ArrayList.Iterator.remove()
 

"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

Re: ArrayList.Iterator.remove()
 

"Lew" <lew@lewscanon.com> wrote in message
news:41a887d9-5729-4818-b2cd-40366d0c60d2@r34g2000vba.googlegroups.com
> "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..

Re: ArrayList.Iterator.remove()
 

Donkey Hottie wrote:
> "Lew" <lew@lewscanon.com> wrote in message
> news:98f02bfe-752f-41a2-8ab0-abac861efca0@g6g2000vbr.googlegroups.com
> .
>>
>> 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

Re: ArrayList.Iterator.remove()
 

Donkey Hottie wrote:
> "Lew" <lew@lewscanon.com> wrote in message
> news:41a887d9-5729-4818-b2cd-40366d0c60d2@r34g2000vba.googlegroups.com
>> "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
esosman@ieee-dot-org.invalid