Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

ArrayList.Iterator.remove()

 
 
Arne Vajh°j
Guest
Posts: n/a
 
      06-30-2009
Donkey Hottie wrote:
> "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.


It is many.

If all the items were removed first in the list you would have moved
approx. 4.8 billion elements because ArrayList is backed by an array
and need to move things around after a delete.

Arne
 
Reply With Quote
 
 
 
 
Arne Vajh°j
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.


Most likely it would be better with another data type than
ArrayList.

Arne
 
Reply With Quote
 
 
 
 
Arne Vajh°j
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..


I would expect a C++ program using STL vector to have the same
behavior.

Arne
 
Reply With Quote
 
Roedy Green
Guest
Posts: n/a
 
      06-30-2009
On Tue, 30 Jun 2009 18:32:21 -0400, Eric Sosman
<(E-Mail Removed)> wrote, quoted or indirectly quoted
someone who said :

> 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.


It is very quick if you create a new array. See
http://mindprod.com/products1.html#SORTED for a set of classes for
merging and deduping etc. Unfortunately, the classes were written
before generics were introduced.
--
Roedy Green Canadian Mind Products
http://mindprod.com

"Deer hunting would be fine sport, if only the deer had guns."
~ William S. Gilbert of Gilbert and Sullivan
 
Reply With Quote
 
Lew
Guest
Posts: n/a
 
      07-01-2009
Donkey Hottie wrote:
> "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).


This is where being a Javadoc junkie pays off.

<http://java.sun.com/javase/6/docs/api/java/util/package-summary.html>

There really is no reason not to be aware of the basic collection classes.

--
Lew
 
Reply With Quote
 
markspace
Guest
Posts: n/a
 
      07-01-2009
Donkey Hottie wrote:
>> ArrayList. ArrayList is optimized for indexed access.
>>

>
> Thanks!
>
> I was not aware of that kind of a List being in Java library (thought it



What?! Are you kidding me? I'm sorry but this is bull****. How the
hell can you program in Java at all with out at least bumping into the
Collections classes? This is really amazing to me. They're in every
tutorial. It's basic algorithms and should be instantly familiar to
anyone who made it through their lower division course work.... I'm just
aghast. Seriously.

Especially a C++ programmer should be on the lookout for something in a
new language to replace the STL, and Collections is a big part of Java's
answer to the STL.


 
Reply With Quote
 
Joshua Cranmer
Guest
Posts: n/a
 
      07-01-2009
Arne Vajh°j wrote:
> I would expect a C++ program using STL vector to have the same
> behavior.


He should have used the STL list instead .

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      07-01-2009
Roedy Green wrote:
> On Tue, 30 Jun 2009 18:32:21 -0400, Eric Sosman
> <(E-Mail Removed)> wrote, quoted or indirectly quoted
> someone who said :
>
>> 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.

>
> It is very quick if you create a new array. [...]


Assuming the items being removed are fairly numerous. (As
it seems they are, although the O.P. let slip this information
only in follow-ups and not in the original "removal is futile"
post.)

If only a few items are being deleted, especially if they
are known to appear near the end, the work involved in sliding
all their successors one place to the left may well be less than
the work of copying "all except" to an entirely new array. Horses
for courses, and don't blame the horse if he falters when you
ride him up the ski jump.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)lid
 
Reply With Quote
 
Arne Vajh°j
Guest
Posts: n/a
 
      07-01-2009
Joshua Cranmer wrote:
> Arne Vajh°j wrote:
>> I would expect a C++ program using STL vector to have the same
>> behavior.

>
> He should have used the STL list instead .


Yep.

But then LinkedList is the solution in Java.

Arne
 
Reply With Quote
 
Kevin McMurtrie
Guest
Posts: n/a
 
      07-01-2009
In article <(E-Mail Removed)>,
"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.


Skipped school? This is in the basics of information science. It has
nothing to do with Java.

When I think of hidden Java features I think of secret accessor methods,
generics insanity, -XX switches, FinalReference, and in-place math
operators lacking narrowing checks.

--
I will not see your reply if you use Google.
 
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