Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.albasani.net!.POSTED!not-for-mail
From: Jan Burse <janburse@fastmail.fm>
Newsgroups: comp.lang.java.programmer
Subject: Re: setSize ArrayList, when will it come?
Date: Tue, 09 Aug 2011 11:32:42 +0200
Organization: albasani.net
Lines: 110
Message-ID: <j1quru$l0i$1@news.albasani.net>
References: <j1pp1j$3rf$1@news.albasani.net> <j1q1cv$aos$1@dont-email.me> <j1q596$gs8$1@news.albasani.net> <wcqdnZuEIsJJbd3TnZ2dnUVZ_hmdnZ2d@earthlink.com> <j1qtu4$iuj$1@news.albasani.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: news.albasani.net 1VhgVC1LhmD8Au4VWWbVFKrtnG6xH03TCIjqXlb/7s7MrM7Tz9KsQNluNm+5LITixwXzj4OtT5WJWCK2XH7xqw==
NNTP-Posting-Date: Tue, 9 Aug 2011 09:32:46 +0000 (UTC)
Injection-Info: news.albasani.net; logging-data="oWLemuX7Bu08PGK8ZfSRfYVTHpKMVfnSdckbMQc49IyHZHPXNsWcbXRoL7kQvSvlfG6xeSezCPjUjA2j0dV8aAO/02VpgZJ2h4xSK4gecVc58arE5Z8P7tEqYPmq3qHB"; mail-complaints-to="abuse@albasani.net"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:5.0) Gecko/20110706 Firefox/5.0 SeaMonkey/2.2
In-Reply-To: <j1qtu4$iuj$1@news.albasani.net>
Cancel-Lock: sha1:5ZXE3haGHhTVxj6XtewWkdrIF3k=
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:6905

Jan Burse schrieb:
> Patricia Shanahan schrieb:
>> On 8/8/2011 7:16 PM, Jan Burse wrote:
>> ...
>>> I actually do use setSize for a kind of sparse Vector.
>>> Sparse in the sense that my Vector will have a couple
>>> of holes represented by null value elements. Which
>>> is eventually abuse of the term "sparse", but the use
>>> case is there.
>> ...
>>
>> If you only need small numbers of null elements, you could write a class
>> extending ArrayList that has setSize(). All you would do is loop adding
>> null elements or removing the tail elements until the ArrayList is the
>> required size.
>>
>> Patricia
>
> If only so many fields in ArrayList would not be private
> I could do that. But since for example in JDK 1.6.0_26
> none of the fields are protected, everything is private.
>
> What you suggest is theoretically sound but practically
> impossible. Look see:
>
> public class ArrayList<E> extends ...
> {
> private transient Object[] elementData;
> private int size;
> ...
> }
>
> And using reflection overriding this protection,
> is kind of ugly and eventually less performant.
>
> Bye

Interestingly ArrayList has ensureCapacity() which
is public. Whereby in Vector ensureCapacityHelper() is
private.

You are right, one could do a half way efficient setSize()
with ensureCapacity() of ArrayList, by calling
ensureCapacity() and then looping with add() of null.

But the request and idea is to have an efficient setSize().
In the spirit of the Vector setSize(). Namely:

     /* from vector */

     public synchronized void setSize(int newSize) {
	modCount++;
	if (newSize > elementCount) {
	    ensureCapacityHelper(newSize);
	} else {
	    for (int i = newSize ; i < elementCount ; i++) {
		elementData[i] = null;
	    }
	}
	elementCount = newSize;
     }

The last statement and the preceeding loop are crucial.
They require direct access to elementCount and elementData.
These fields correspond to size and elementData in
ArrayList.

But maybe in some VMs/Plattforms/Architectur a loop add()
after ensureCapacity() doesn't show any performance penalty
and would be feasible. Have to check.

Best Regards

BTW: Both Vector and ArrayList have a little glitch, an
unused variable, probably anyway optimized away by the
JIT, but nevertheless:

ArrayList:

     /* Glitch: oldData not used anymore. */

     public void ensureCapacity(int minCapacity) {
	modCount++;
	int oldCapacity = elementData.length;
	if (minCapacity > oldCapacity) {
	    Object oldData[] = elementData;
	    int newCapacity = (oldCapacity * 3)/2 + 1;
     	    if (newCapacity < minCapacity)
		newCapacity = minCapacity;
             // minCapacity is usually close to size, so this is a win:
             elementData = Arrays.copyOf(elementData, newCapacity);
	}
     }

Vector:

    /* Glitch: oldData not used anymore. */

    private void ensureCapacityHelper(int minCapacity) {
	int oldCapacity = elementData.length;
	if (minCapacity > oldCapacity) {
	    Object[] oldData = elementData;
	    int newCapacity = (capacityIncrement > 0) ?
		(oldCapacity + capacityIncrement) : (oldCapacity * 2);
     	    if (newCapacity < minCapacity) {
		newCapacity = minCapacity;
	    }
             elementData = Arrays.copyOf(elementData, newCapacity);
	}
     }