setSize ArrayList, when will it come?

[Jan Burse]

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

This is not efficient. You don't get it what the
problem is. I really really need a highly efficient
setSize() specialized, otherwise my stuff will not work.

 

[Roedy Green]

This is not efficient. You don't get it what the
problem is. I really really need a highly efficient
setSize() specialized, otherwise my stuff will not work.

ArrayList is not that complicated a class. You might write your own
in an afternoon. If you get stuck, you can always peek at Sun's
source.

I wrote a "SortedArrayList" that lazily kept ArrayLists sorted. You
might cannibalise it. (I don't think I ever got around to putting
generics in it though). see http://mindprod.com/products1.html#SORTED

 

[Roedy Green]

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

Have you checked if ArrayList is final? If not, you can extend it
with just a setSize method.

Even if it is final, you could implement a SizeableArrayList class
like this:

class SizeableArrayList implements List{

ArrayList inner;

void int setSize(int size )
{
// to change the size you reallocate and copy the ArrayList, or use //
//setToSize
}

Then create facade methods to implement List that pass parms on to
inner.

This is how I implemented LEInputDataStream to use InputDataStream
methods when InputDataStream was final.
see http://mindprod.com/products1.html#LEDATASTREAM

 

[Knute Johnson]

This is not efficient. You don't get it what the
problem is. I really really need a highly efficient
setSize() specialized, otherwise my stuff will not work.

That's BS. Either it's sparse enough to use a Map or it's too large to
use ArrayList and that would make it too large to use Vector. Just use
arrays, they're a lot faster than a Vector or any List. Or just get a
faster computer.

I should have long since killed this thread.

 

[Arne Vajhøj]

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

Which seems completely irrelevant for the problem.

Arne

 

[Arne Vajhøj]

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.

You can do it with only public methods.

Arne

 

[Arne Vajhøj]

Have you checked if ArrayList is final? If not, you can extend it
with just a setSize method.

It is not final.

But a helper method may actually be more useful, because
you can not assign from a standard ArrayList to the extended
class.

Arne

 

[Joshua Cranmer]

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.

Or you could use addAll and Collections.nCopies to implement setSize,
and use ListIterator to do reverse iteration.

Notice that ArrayList does not sport a sort method--it's on
Collections.sort. Just because the method is not on the list itself does
not mean it's not implemented. Implementing it on the class implies that
anyone who implements the same interface has to reimplement it or
forward it to the same implementation all over again.

 

[Jan Burse]

Or you could use addAll and Collections.nCopies to implement setSize,
and use ListIterator to do reverse iteration.

No you didn't get it. I need a fast specialized
setSize() as argued in the bug reference. According
to the collections documentation, the nCopies method
does create an extra object:

http://download.oracle.com/javase/1...llections.html#nCopies(int, java.lang.Object)
... The newly allocated data object is tiny (it contains
a single reference to the data object). ...

But it is not only that this tiny object of type
Collections.CopiesList will be created. For addAll
call an Iterator AbstractList.Itr will be
created I guess, not sure.

But most likely given the abstract implementation of
addAll, the abstract way it treats its argument, and
in the particular situation that the argument is a
CopiesList.

So this is already two temporary objects on the heap.

Don't have a good feeling with this.

Bye

 

[Jan Burse]

That's BS. Either it's sparse enough to use a Map or it's too large to
use ArrayList and that would make it too large to use Vector. Just use
arrays, they're a lot faster than a Vector or any List. Or just get a
faster computer.

I should have long since killed this thread.

I am refering to the number of created temporary objects
during the operation. See my other post. Using the
official existing API with nCopies and addAll will use
at least two additional temporary objects.

But there is one more disadvantage of the helper
going the official way approach. If you look at the
addAll you see that it will repeatedly call add().
So it will repeatedly enlarge the ArrayList.

So instead of jumping instantly to the desired size
as a setSize implementation can do. It will temporarly
create elementData arrays of different sizes until
it has reached the final size. Given the 150% + 1
expension rule, if I do a setSize(100) from start
it will create the following temporary elementData
array objects:

Nr Size
1 1
2 2
3 4
4 7
5 11
6 17
7 26
8 40
9 61
10 92
11 139

So there are 10 temporary array allocations, until
we reach the final array. Also the resultinhg elementData
has 39 excess place holders which I don't need.
A setSize() implementation might just create the
array right sized.

So now you can go about and kill whatever you like.

Bye

 

[Robert Klemme]

I have only referted to the meta use case in my post.
The software refactoring use case, is replacing a synchronized
Vector by an unsychronized ArrayList in regions where no synchronization
is necessary.

This can be done in many cases, especially in all cases where Vector
instances are used through the List interface.

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 really need a sparse type then you could use Map<Integer,E> or

The missing thought in the reponse is the design goal
of ArrayList. They are explicitly advertised in the
class comment as unsynchronized version of Vector. It
is brainless not to honor such a design goal in a response.

This is not true. Quote: "This class is roughly equivalent to Vector,
except that it is unsynchronized."
http://download.oracle.com/javase/6/docs/api/java/util/ArrayList.html

Note the "roughly". This is the only reference to "Vector" on that doc
page (apart from the link to Vector's page).

On the other hand it is very clever to have the possibility
of turning initial design goals into requests for
enhancement. Imagine the following situation:

You go into a restaurant and order pizza,
you get your pizza without cheese, you
ask the waiter what is wrong, and the waiter
says, oh this cannot be changed, cheese has
to be ordered separately.

Brainless are we, who accept this.

Engineers at Sun might be less brainless than you think. In fact, they
probably used the chance to clean the interface. I believe the design
rationale here is that the size of a collection should only be modified
by methods which actually add or remove from the collection.

Frankly, all the efforts you spend for ranting about Sun / Oracle not
"fixing" a bug with prio "low" (and also the erroneous statement about
"sparse Vectors") could be better spent for any of these solutions:

1. Write your own version of ArrayList by inheriting AbstractList and
adding all the methods you need.

2. Writing a static helper method which uses ArrayList.ensureCapacity()
and a loop which invokes add() or removeRange() depending on whether the
new capacity is larger or smaller.

3. Do nothing. Synchronization overhead of Vector isn't too bad if it's
not used by multiple threads. After all the replacement is more like an
optimization. If you want to be sure, do the measurements.

Kind regards

robert

 

[Andreas Leitgeb]

According to the collections documentation, the nCopies method
does create an extra object: ...

How do Java developers change lightbulbs?
First they create an instance of ...

I'm afraid, you'll have to get used to that certain tasks (involving
classes of the standard library) are not done the straightforward way,
but by abstrahizing the problem "beyond recognition", and then throwing
some use-once instances at it. ;-)

Posting about perceived imperfections of Java here in cljp typically
has one of these outcomes:
- If you just missed something simple, you'll be told so.
That's why it is often good to ask here.
- Otherwise, you're told of some roundabout way to do it - and will
be seen as a troll if you comment on the roundaboutedness per se.
One should always measure it. And measuring indeed often shows
that the roundabout way isn't all that bad after all. If it is,
then you're suggested to buy a stronger machine (for you and for
all those who will run your code).

What one can be entirely sure won't happen under any circumstances
for a deficiency posted here:
- The straightforward solution will be implemented in Java.
A feature request on oracle's site might have had little more than
zero-chance, if also avoiding the word "sparse" in the description.

 

[Andreas Leitgeb]

This can be done in many cases, especially in all cases where Vector
instances are used through the List interface.

Originally, Vector wasn't a List. So, really old code isn't
very "likely" to use the List interface of Vector.

If you really need a sparse type ...

didn't seem so.

 

[Mayeul]

I am refering to the number of created temporary objects
during the operation. See my other post. Using the
official existing API with nCopies and addAll will use
at least two additional temporary objects.

Wow, a whole two objects? While manipulating a typical Java Collection?
That just simply won't do.

I actually have my doubts that it would be any inefficient at all until
I've measured it. Anyway, if I have read the thread correctly, there is
claim that we have here a tradeoff: ensure that a List's size will only
change on element insertion or deletion, a rather natural assertion. At
the cost of possibly, if measured so, forcing developers in your
situation to keep Vector or to get a more specialized implementation of
List.
How long do you plan to ignore this claim?

But there is one more disadvantage of the helper
going the official way approach. If you look at the
addAll you see that it will repeatedly call add().

Your prediction proved wrong. Though I do not think my eyes are playing
tricks on me, I saw nothing of the sort.

So it will repeatedly enlarge the ArrayList.

So instead of jumping instantly to the desired size
as a setSize implementation can do. It will temporarly
create elementData arrays of different sizes until
it has reached the final size. Given the 150% + 1
expension rule, if I do a setSize(100) from start
it will create the following temporary elementData
array objects:

Nr Size
1 1
2 2
3 4
4 7
5 11
6 17
7 26
8 40
9 61
10 92
11 139

So there are 10 temporary array allocations, until
we reach the final array. Also the resultinhg elementData
has 39 excess place holders which I don't need.
Nope

A setSize() implementation might just create the
array right sized.

As does an addAll() of any size.

 

[Jan Burse]

2. Writing a static helper method which uses ArrayList.ensureCapacity()
and a loop which invokes add() or removeRange() depending on whether the
new capacity is larger or smaller.

removeRange is protected, so I cannot use it in a helper.

 

[Jan Burse]

Nope

Yes that you are right, since array list does override
the addAll method, and there they do set the size correctly.

But a new object pops up there. The CopiesList is materialized.
Here you see the code:

public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}

So there are two temporary objects, the CopiesList, and the
Object[] a from above. No enumerator.

Not nice

 

[Lew]

I am refering to the number of created temporary objects
during the operation. See my other post. Using the
official existing API with nCopies and addAll will use
at least two additional temporary objects.

But there is one more disadvantage of the helper
going the official way approach. If you look at the
addAll you see that it will repeatedly call add().
So it will repeatedly enlarge the ArrayList.

'ArrayList#ensureCapacity()'?

So instead of jumping instantly to the desired size
as a setSize implementation can do. It will temporarly
create elementData arrays of different sizes until
it has reached the final size. Given the 150% + 1
expension rule, if I do a setSize(100) from start
it will create the following temporary elementData
array objects:
'ArrayList#ensureCapacity()'?

Nr Size
1 1
2 2
3 4
4 7
5 11
6 17
7 26
8 40
9 61
10 92
11 139

So there are 10 temporary array allocations, until
we reach the final array. Also the resultinhg elementData
has 39 excess place holders which I don't need.
A setSize() implementation might just create the
array right sized.

'ArrayList#ensureCapacity()'?

So now you can go about and kill whatever you like.

Your objection?

 

[Robert Klemme]

removeRange is protected, so I cannot use it in a helper.

Sorry about that. Then just use a loop with remove(int).

Actually how to do it was not my main point. You can still do it
yourself and efficiently so. Your complaint about a bug report which is
not handled to your liking is most likely futile - and also in the wrong
place. And please also keep in mind that the JDK is given to you for
free which kinda limits the handle you have on Oracle to force them to
do what you want. Maybe you need to sink Larry's ship - but even in
that case I reckon it's more likely that he gets after you than the
other way round.

Cheers

robert

 

[Jan Burse]

Sorry about that. Then just use a loop with remove(int).

Actually how to do it was not my main point. You can still do it
yourself and efficiently so. Your complaint about a bug report which is
not handled to your liking is most likely futile - and also in the wrong
place. And please also keep in mind that the JDK is given to you for
free which kinda limits the handle you have on Oracle to force them to
do what you want. Maybe you need to sink Larry's ship - but even in that
case I reckon it's more likely that he gets after you than the other way
round.

Cheers

robert

I guess Larry will give me some money, when he sees that
with the new setSize() his servers will be more green. There
should be a market for energy efficiency nowadays.

Bye

P.S.: I don't champion energy efficiency yet, one of the
applications I am working on is rather a black hole concerning
energy, compared to the video streaming which only eats up
3W or so (which still impresses me), when I run my application
energy consumption goes up by 16W or so.

 

[Jan Burse]

'ArrayList#ensureCapacity()'?

Your objection?

Although it is a public method, it wouldn't work,
since it does not set the size field of the ArrayList.
So you only have as a post condition after ensureCapacity(n):

elementData.length>=n

But not:

size=n

You would still need to invoke a couple of add() calls
after calling ensureCapacity().

But calling ensureCapacity() before calling the add()s
would prevent gradually enlarging the ArrayList, so that
we would have a solution with zero unnecessary temporary
objects.

gr8 step forward, many thanks.

But still not what I consider an efficient solution. You
will burn some CPU cycles in the add()s call for nothing,
since the elementData is already nulled from Array.newInstance()
as required by the JLS.

So not a green solution.

Best Regards