ArrayList.Iterator.remove()

Discussion in 'Java' started by Donkey Hottie, Jun 30, 2009.

  1. 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.
     
    Donkey Hottie, Jun 30, 2009
    #1
    1. Advertising

  2. Donkey Hottie

    Eric Sosman Guest

    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
    lid
     
    Eric Sosman, Jun 30, 2009
    #2
    1. Advertising

  3. Donkey Hottie

    Lew Guest

    On Jun 30, 4:50 pm, "Donkey Hottie" <> 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)
    > hifts any subsequent elements to the left (subtracts one from their indices).

    <http://java.sun.com/javase/6/docs/api/java/util/ArrayList.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
     
    Lew, Jun 30, 2009
    #3
  4. "Eric Sosman" <> wrote in
    message news:h2dv0m$350$-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.
     
    Donkey Hottie, Jun 30, 2009
    #4
  5. "Lew" <> wrote in message
    news:
    ..
    >
    > 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.
     
    Donkey Hottie, Jun 30, 2009
    #5
  6. "Patricia Shanahan" <> wrote in message
    news:
    >
    > 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.
     
    Donkey Hottie, Jun 30, 2009
    #6
  7. Donkey Hottie

    Lew Guest

    "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
     
    Lew, Jun 30, 2009
    #7
  8. "Lew" <> wrote in message
    news:
    > "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..
     
    Donkey Hottie, Jun 30, 2009
    #8
  9. Donkey Hottie wrote:
    > "Lew" <> wrote in message
    > news:
    > .
    >>
    >> 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
     
    Knute Johnson, Jun 30, 2009
    #9
  10. Donkey Hottie

    Eric Sosman Guest

    Donkey Hottie wrote:
    > "Lew" <> wrote in message
    > news:
    >> "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
    lid
     
    Eric Sosman, Jun 30, 2009
    #10
  11. Donkey Hottie

    Arne Vajhøj Guest

    Donkey Hottie wrote:
    > "Eric Sosman" <> wrote in
    > message news:h2dv0m$350$-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
     
    Arne Vajhøj, Jun 30, 2009
    #11
  12. Donkey Hottie

    Arne Vajhøj Guest

    Donkey Hottie wrote:
    > "Lew" <> wrote in message
    > news:
    >> 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
     
    Arne Vajhøj, Jun 30, 2009
    #12
  13. Donkey Hottie

    Arne Vajhøj Guest

    Donkey Hottie wrote:
    > "Lew" <> wrote in message
    > news:
    >> "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
     
    Arne Vajhøj, Jun 30, 2009
    #13
  14. Donkey Hottie

    Roedy Green Guest

    On Tue, 30 Jun 2009 18:32:21 -0400, Eric Sosman
    <> 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
     
    Roedy Green, Jul 1, 2009
    #14
  15. Donkey Hottie

    Lew Guest

    Donkey Hottie wrote:
    > "Patricia Shanahan" <> wrote in message
    > news:
    >>
    >> 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
     
    Lew, Jul 1, 2009
    #15
  16. Donkey Hottie

    markspace Guest

    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.
     
    markspace, Jul 1, 2009
    #16
  17. 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
     
    Joshua Cranmer, Jul 1, 2009
    #17
  18. Donkey Hottie

    Eric Sosman Guest

    Roedy Green wrote:
    > On Tue, 30 Jun 2009 18:32:21 -0400, Eric Sosman
    > <> 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
    lid
     
    Eric Sosman, Jul 1, 2009
    #18
  19. Donkey Hottie

    Arne Vajhøj Guest

    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
     
    Arne Vajhøj, Jul 1, 2009
    #19
  20. In article <>,
    "Donkey Hottie" <> 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.
     
    Kevin McMurtrie, Jul 1, 2009
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Saravanan Rathinavelu

    Iterate through ArrayList using an another ArrayList

    Saravanan Rathinavelu, Aug 16, 2003, in forum: ASP .Net
    Replies:
    3
    Views:
    2,794
    Natty Gur
    Aug 19, 2003
  2. John C. Bollinger
    Replies:
    3
    Views:
    12,397
    Adam Maass
    Aug 6, 2003
  3. Kaidi
    Replies:
    4
    Views:
    2,486
    Kaidi
    Jan 3, 2004
  4. xz
    Replies:
    16
    Views:
    2,441
  5. Philipp
    Replies:
    6
    Views:
    970
    Arne Vajhøj
    May 28, 2008
Loading...

Share This Page