Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > setSize ArrayList, when will it come?

Reply
Thread Tools

setSize ArrayList, when will it come?

 
 
Jan Burse
Guest
Posts: n/a
 
      08-09-2011
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
 
Reply With Quote
 
 
 
 
Jan Burse
Guest
Posts: n/a
 
      08-09-2011
Andreas Leitgeb schrieb:
> Sorry to be so direct, but this "prognose" appeared entirely
> brainless to me. I know, that your arguments usually aren't.
> I guess this is just the type of answer you give to people
> that you "identified" as trolls.


I guess you guys have nothing todo, except feeding each other
in a troll like manner.

Bye
 
Reply With Quote
 
 
 
 
Jan Burse
Guest
Posts: n/a
 
      08-09-2011
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);
}
}
 
Reply With Quote
 
Jan Burse
Guest
Posts: n/a
 
      08-09-2011
Jan Burse schrieb:
>
> BTW: Both Vector and ArrayList have a little glitch, an
> unused variable, probably anyway optimized away by the
> JIT, but nevertheless:


Ok, they saw that:
http://bugs.sun.com/view_bug.do?bug_id=6812879

 
Reply With Quote
 
Joshua Cranmer
Guest
Posts: n/a
 
      08-09-2011
On 8/9/2011 2:56 AM, Andreas Leitgeb wrote:
> Joshua Cranmer<(E-Mail Removed)> wrote:
>> Now you're going to argue that it's brainless that ...

>
> Sorry to be so direct, but this "prognose" appeared entirely
> brainless to me. I know, that your arguments usually aren't.
> I guess this is just the type of answer you give to people
> that you "identified" as trolls.


I meant it as a rhetorical device to show that the argument, applied
strictly, leads to a rather untenable proposition. There are a fair
number of observable differences between Vector and ArrayList, even if
you exclude the part about synchronized methods.

I would also like to point out that in the time you have spent arguing
for this feature, you could have implemented a small class that had this
feature already.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
 
Reply With Quote
 
Jan Burse
Guest
Posts: n/a
 
      08-09-2011
Joshua Cranmer schrieb:
> There are a fair number of observable differences between Vector and
> ArrayList, even if you exclude the part about synchronized methods.

What are you refering to? Can you elaborate on your thoughts.
 
Reply With Quote
 
Roedy Green
Guest
Posts: n/a
 
      08-09-2011
On Tue, 09 Aug 2011 00:47:12 +0200, Jan Burse <(E-Mail Removed)>
wrote, quoted or indirectly quoted someone who said :

>When will ArrayList have a setSize() method. Its lack
>makes it practically impossible to consistently replace
>Vector by ArrayList.


This will not make you happy, but there is ArrayList.trimToSize

To grow an ArrayList, you must do it one slot at a time.

Further, I would hope ArrayList.addAll would be smart enough to grow
the array only once, if needed.
--
Roedy Green Canadian Mind Products
http://mindprod.com
Most of computer code is for telling the computer
what do if some very particular thing goes wrong.
 
Reply With Quote
 
Joshua Cranmer
Guest
Posts: n/a
 
      08-09-2011
On 8/9/2011 11:30 AM, Jan Burse wrote:
> Joshua Cranmer schrieb:
>> There are a fair number of observable differences between Vector and
>> ArrayList, even if you exclude the part about synchronized methods.

> What are you refering to? Can you elaborate on your thoughts.


Anything reflective is a dead giveaway, and I'm pretty sure that the two
classes have slightly different sizes, so you could observe differences
in memory characteristics.

More seriously, the Collections API tweaked some method names
differently, so there are a few methods in Vector which are kept around
for legacy use (addElement, e.g.).

In general, an ArrayList is a list that happens to be backed by an
array. A Vector is a synchronized, automatically-growing array that
leaks details about its array all over the place; it was shoehorned into
the Collections API upon introduction to allow for a more gradual,
correct migration.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
 
Reply With Quote
 
Tom Anderson
Guest
Posts: n/a
 
      08-09-2011
On Tue, 9 Aug 2011, Patricia Shanahan wrote:

> On 8/9/2011 9:58 AM, Roedy Green wrote:
> ...
>> Further, I would hope ArrayList.addAll would be smart enough to grow
>> the array only once, if needed.

> ...
>
> It does the following:
>
> 1. Grow to the needed size.
>
> 2. Call the other collection's toArray method.
>
> 3. System.arraycopy the toArray result into the ArrayList's elementData.
>
> This double copy is going to be faster than the one at a time approach
> only if large numbers of nulls are being added. If that is the case, the
> structure is probably too sparse for ArrayList to be a good choice.


It would be nice if ArrayList used a loop to do the copy for small added
collections; it could cut over to the array method for larger addends.

Anyway, with List.addAll and Collections.nCopies, we can write:

<T> void setSize(List<T> list, int size) {
int change = size - list.size();
if (change > 0) {
list.addAll(Collections.nCopies(change, null));
}
else if (change < 0) {
list.subList(size, list.size()).clear();
if (list instanceof ArrayList) ((ArrayList)list).trimToSize();
}
// else do nothing
}

I haven't tried that, but it should work.

So, Jan, less whining, more coding, please.

tom

--
As Emiliano Zapata supposedly said, "Better to die on your feet than
live on your knees." And years after he died, Marlon Brando played him
in a movie. So just think, if you unionize, Marlon Brando might play
YOU in a movie. Even though he's dead. -- ChrisV82
 
Reply With Quote
 
Jan Burse
Guest
Posts: n/a
 
      08-09-2011
Joshua Cranmer schrieb:
> Anything reflective is a dead giveaway, and I'm pretty sure that the two
> classes have slightly different sizes, so you could observe differences
> in memory characteristics.


In vector you can parametrisize the growing characteristics, either
by a constant increment or doubling the size. For this purpose there
is an extra field not found in ArrayList.

Array list always follows a 150% + 1 rule when growing the internal
data buffer. There is no extra field need to store some parameter.
But otherwise the two use the same data representation.

But I think it would not prevent me from using ArrayList instead
of Vector, that this parameter is missing. The 150% has its merits
over the strategies implemented in vector.

> More seriously, the Collections API tweaked some method names
> differently, so there are a few methods in Vector which are kept
> around for legacy use (addElement, e.g.).


Yes when replacing Vector by ArrayList, one has to rename the method
calls. For example instead of addElement() one needs to use add(), and
instead of elementAt().

But renaming methods does not prevent me from using ArrayList. As
long each legacy method has a new buddy, I don't see any problem
whatever with it.

> In general, an ArrayList is a list that happens to be backed by an
> array. A Vector is a synchronized, automatically-growing array that
> leaks details about its array all over the place; it was shoehorned
> into the Collections API upon introduction to allow for a more
> gradual, correct migration.


I don't see that Vector leaks more details than ArrayList about its
implementation. Could you make an example? I only see that the fields
of vector are protected, and well yes this means vector is not fully
encapsulated.

But I want to migrate to ArrayList whereever possible, so why should
I bother that Vector is not fully encapsulated. And if ArrayList has
the merrit that it is fully encapsulated the better.

But the protected fields would only be seen by a subclass, which could
sneak into some of your parameters of your methods, and spy on you or
cheat on you. Since vector is not final. That is a drawback. But same
problem with ArrayList.

Vector and ArrayList both implement the following protocolls:
AbstractList<E>
List<E>,
RandomAccess,
Cloneable,
Serializable

If only somebody would have had the brains to include setSize()
somewhere. List has the methods size(), add() and remove() in it.
setSize(n) could be neatly abstractly specified as having the
post condition size()=n and after.get(i)=before.get(i) for
i<before.size() and after.get(i)=null for i>=before.size() and
i<after.size().

And the AbstractList could implement abstractly the inefficient
setSize() that would use remove() and add(), when Random access is
present via index, or otherwise maybe with a backward iterator.
Backward iterator is also missing btw. And then concrete classes
could provide more efficient implementations if necessary.

Bye


Best Regards
 
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


Similar Threads
Thread Thread Starter Forum Replies Last Post
setSize problem Douglas Masterson Java 0 09-24-2003 01:40 PM



Advertisments