Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #6998

Re: setSize ArrayList, when will it come?

Show all headers | View raw

Andreas Leitgeb schrieb:
>  1.) a good estimate on what size you'll end up using, and
>     create the ArrayList with that size.  Eating up a few
>     kilobytes (or even up to a megabyte) of nulls too much
>     is probably still greener than re-allocating the buffer
>     each time a new largest-so-far index shows up.  If the
>     original estimation turns out to be too small, then grow
>     it with addAll(...nCopies(...)) - it wouldn't be done
>     all that often, so the extra effort wouldn't matter.

>   2.) if no such limit can be reasonably predicted, then
>      chances are that a real sparse structure really fits
>      the bill better.  (I didn't quite understand your argument
>      against using a Map - it didn't make sense to me when you
>      wrote it)

I never placed an argument against map. Where was this?
Just assume that the original code had setSize() for
whatever reason, and that the redesign of the original
code is not at stake.

But you are right, a redesign could of course be an option.

 > The ideal (semi-)sparse structure wouldn't even need a setSize(),
 > as it would grow the internal buffer as needed to allow .set() to
 > work with any (non-negative) index, and let .get() just return null
 > for indices beyond the current end instead of throwing
 > IndexOutOfBounds-Exceptions.

Actually in the current application the Vector/ArrayList need
not necessarely be sparse. It could be, but it does not have
to be, both scenarios should possible coexist, sparse and non-sparse.
The current application has a high frequency of creating for an 
initially Vector/ArrayList of size 0.

Then upon some event (imagine also high frequency) the size
might jump to n, and the element at position n-1 is set to
non null. And then upon some other event the size might jump
to m, and the element at position m-1 is set to non null. But
there is no guarantee that n and m are close. Also it can
happen that an event j arrives, and the element at position
j is set to non null, j being somewhere between 0 and m-1. So
that the array might become gradually less sparse.

Imagine the above process to last a very short time, until the
livecycle of the array ends. Before the livecycle ends, the
array might contain up to 100 or more non-null positions. But
there is no guarantee that they are close together or not.
But when there are 100 entries their indexes might span the
range of 1000. But it is very important that the access to
the elements is O(1).

The sparseness is only mentioned in the oracle bug. But actually
I think the sparseness is irrelevant. Just assume you have an
existing application with Vector that happily uses setSize(). So
what do you do?

Bye

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-09 00:47 +0200
  Re: setSize ArrayList, when will it come? Knute Johnson <september@knutejohnson.com> - 2011-08-08 16:53 -0700
    Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-09 02:30 +0200
  Re: setSize ArrayList, when will it come? Arne Vajhøj <arne@vajhoej.dk> - 2011-08-08 20:50 -0400
  Re: setSize ArrayList, when will it come? Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-08-08 21:09 -0400
    Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-09 04:16 +0200
      Re: setSize ArrayList, when will it come? Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-08-08 21:39 -0500
        Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-09 09:33 +0200
          Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-09 09:42 +0200
        Re: setSize ArrayList, when will it come? Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-08-09 07:56 +0000
          Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-09 11:18 +0200
          Re: setSize ArrayList, when will it come? Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-08-09 10:36 -0500
            Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-09 18:30 +0200
              Re: setSize ArrayList, when will it come? Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-08-09 16:30 -0500
                Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-10 00:31 +0200
                Re: setSize ArrayList, when will it come? Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-08-09 20:36 -0500
                Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-10 09:04 +0200
                Re: setSize ArrayList, when will it come? Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-08-10 08:50 +0000
                Re: setSize ArrayList, when will it come? Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-08-10 18:16 -0500
                Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-11 01:55 +0200
      Re: setSize ArrayList, when will it come? Patricia Shanahan <pats@acm.org> - 2011-08-09 01:33 -0700
        Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-09 11:16 +0200
          Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-09 11:32 +0200
            Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-09 11:35 +0200
          Re: setSize ArrayList, when will it come? Patricia Shanahan <pats@acm.org> - 2011-08-09 04:00 -0700
          Re: setSize ArrayList, when will it come? Arne Vajhøj <arne@vajhoej.dk> - 2011-08-09 20:11 -0400
      Re: setSize ArrayList, when will it come? Robert Klemme <shortcutter@googlemail.com> - 2011-08-10 10:21 +0200
        Re: setSize ArrayList, when will it come? Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-08-10 09:14 +0000
        Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-10 12:29 +0200
          Re: setSize ArrayList, when will it come? Robert Klemme <shortcutter@googlemail.com> - 2011-08-10 19:27 +0200
            Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-10 20:22 +0200
              Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-10 20:37 +0200
                Re: setSize ArrayList, when will it come? Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-08-10 18:22 -0500
                Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-11 01:52 +0200
                Re: setSize ArrayList, when will it come? Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-08-10 21:43 -0500
                Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-11 14:19 +0200
              Re: setSize ArrayList, when will it come? Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-08-10 22:23 +0000
                Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-11 01:47 +0200
                Re: setSize ArrayList, when will it come? Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-08-11 00:23 +0000
                Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-11 09:19 +0200
                Re: setSize ArrayList, when will it come? Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-08-12 15:06 +0000
  Re: setSize ArrayList, when will it come? Roedy Green <see_website@mindprod.com.invalid> - 2011-08-09 09:58 -0700
    Re: setSize ArrayList, when will it come? Patricia Shanahan <pats@acm.org> - 2011-08-09 10:25 -0700
      Re: setSize ArrayList, when will it come? Tom Anderson <twic@urchin.earth.li> - 2011-08-09 22:38 +0100
        Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-10 00:36 +0200
          Re: setSize ArrayList, when will it come? Roedy Green <see_website@mindprod.com.invalid> - 2011-08-09 15:55 -0700
          Re: setSize ArrayList, when will it come? Knute Johnson <september@knutejohnson.com> - 2011-08-09 16:03 -0700
            Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-10 09:18 +0200
              Re: setSize ArrayList, when will it come? Mayeul <mayeul.marguet@free.fr> - 2011-08-10 11:26 +0200
                Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-10 12:35 +0200
              Re: setSize ArrayList, when will it come? Lew <lewbloch@gmail.com> - 2011-08-10 09:33 -0700
                Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-10 20:22 +0200
          Re: setSize ArrayList, when will it come? Patricia Shanahan <pats@acm.org> - 2011-08-09 22:13 -0700
            Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-11 02:01 +0200
              Re: setSize ArrayList, when will it come? Patricia Shanahan <pats@acm.org> - 2011-08-10 18:42 -0700
                Re: setSize ArrayList, when will it come? Jan Burse <janburse@fastmail.fm> - 2011-08-11 14:21 +0200
    Re: setSize ArrayList, when will it come? Arne Vajhøj <arne@vajhoej.dk> - 2011-08-09 20:09 -0400
  Re: setSize ArrayList, when will it come? Roedy Green <see_website@mindprod.com.invalid> - 2011-08-09 16:02 -0700
    Re: setSize ArrayList, when will it come? Arne Vajhøj <arne@vajhoej.dk> - 2011-08-09 20:13 -0400

csiph-web