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