«

Tom Anderson schrieb:
> 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
>

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.

On Wed, 10 Aug 2011 00:36:03 +0200, Jan Burse <>
wrote, quoted or indirectly quoted someone who said :

>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 Canadian Mind Products
http://mindprod.com
Most of computer code is for telling the computer
what do if some very particular thing goes wrong.

On Tue, 09 Aug 2011 00:47:12 +0200, Jan Burse <>
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.

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
--
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.

On 8/9/2011 3:36 PM, Jan Burse wrote:
> 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.

--

Knute Johnson

On 8/9/2011 12:58 PM, Roedy Green wrote:
> On Tue, 09 Aug 2011 00:47:12 +0200, Jan Burse<>
> 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

Which seems completely irrelevant for the problem.

Arne

On 8/9/2011 5:16 AM, Jan Burse wrote:
> 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.
>
> 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

On 8/9/2011 7:02 PM, Roedy Green wrote:
> On Tue, 09 Aug 2011 00:47:12 +0200, Jan Burse<>
> 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.
>
> 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

On 8/9/2011 5:31 PM, Jan Burse wrote:
> 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.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth

Joshua Cranmer schrieb:
> 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....lang.Object%29
... 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

Knute Johnson schrieb:
> 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