Arrays.asList() doesn't work quite like I would think it should

[Ken]

I've included an example of the problem I've run into. I'm trying to
randomize an array of integers, much like the following program does.
Unfortunately when I ask the system to do so, I don't get a randomized
array. Now normally this wouldn't bother me. I would just assume that
a new object is being created and then destroyed by the garbage collector
without my ever seeing it, but in this case it looks like a bug.

Isn't the whole point of the asList() interface to allow this kind of
thing?

Is this a bug in Java?

--
Kenneth P. Turvey <[email protected]>

--------------------------------------------------------------------

import java.util.Arrays;
import java.util.Collections;

public class ArrayAsListTester {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
int indicies[] = new int[100];

for (int index = 0; index < 100; index++) {
indicies[index] = index;
}

Collections.shuffle(Arrays.asList(indicies));

for (int index = 0; index < 100; index++) {
System.out.println(indicies[index]);
}
}
}

 

[Stefan Ram]

--

Writing your program in front of the signature separator
will enhance the visibility of your code.

int indicies[] = new int[100];

Use »java.lang.Integer indicies[] = new java.lang.Integer[ 100 ];« here.

Otherwise, »asList« will see an array with only one component
»indicies« because its parameter has type »T...«.

Using an English word like »indices« (instead of
»indicies«) will enhance the readability of your code.

 

[xen]

I've included an example of the problem I've run into. I'm trying to
randomize an array of integers, much like the following program does.
Unfortunately when I ask the system to do so, I don't get a randomized
array. Now normally this wouldn't bother me. I would just assume that
a new object is being created and then destroyed by the garbage collector
without my ever seeing it, but in this case it looks like a bug.

Isn't the whole point of the asList() interface to allow this kind of
thing?

Is this a bug in Java?

Arrays.asList() tries to instantiate an ArrayList on the specified
array but an ArrayList can never be backed by an int[].

If you call asList() on an int[], you will get a List<int[]> with one
element: the int[] you supplied. If you call shuffle on that list,
nothing will change in the int[].

You don't get an error because the parameter for asList is a "T... a".
If you call it with a T[], that array is passed.
If you call it with an array of a primitive type, then it cannot be
treated as a T[] because generic types cannot be primitives. Instead,
because int[] itself is an object, it matches the T in the signature
and is wrapped inside an array. So what actually gets passed is not
your int[], but an array of int[] with one element.

There is no way for the compiler to generate an error.
And why should ArrayList(T... t) complain? An int[] is a valid type
parameter.

Perhaps the compiler should generate a warning if you pass an array of
primitive to a generic dynamic array parameter.

Anyway, you can only solve it by using an Integer[] instead of an
int[].

 

[Mark Space]

I've included an example of the problem I've run into. I'm trying to
randomize an array of integers, much like the following program does.
Unfortunately when I ask the system to do so, I don't get a randomized
array. Now normally this wouldn't bother me. I would just assume that
a new object is being created and then destroyed by the garbage collector
without my ever seeing it, but in this case it looks like a bug.

Isn't the whole point of the asList() interface to allow this kind of
thing?

Is this a bug in Java?

I doubt it. A more experienced Java programmer would spot this right away.

I didn't run your program (which is a shame since you did include a good
one), but I'm gonna guess that the output is a sorted, not randomized list.

Not a Java bug.

asList returns a NEW OBJECT. Your original array was never touched. Try
something like:

List myList = Arrays.asList(indicess);
Collections.shuffle(myList);

Then print out myList and see what you get.

 

[Stefan Ram]

asList returns a NEW OBJECT. Your original array was never touched.

In German, there is a saying »Wer schreit hat Unrecht.«¹. Thus,

»Changes to the returned list "write through" to the array.«

http://download.java.net/jdk7/docs/api/java/util/Arrays.html#asList(T...)

1) »He who shouts is wrong.«. In Usenet, using
all caps sometimes is considered to resemble shouting.

 

[Roedy Green]

Collections.shuffle(Arrays.asList(indicies));

asList makes a copy. So you have shuffled a new copy of the data in a
List then thrown it away. Your code does not shuffle the original
array.

 

[Daniel Pitts]

asList makes a copy. So you have shuffled a new copy of the data in a
List then thrown it away. Your code does not shuffle the original
array.

Actually, it does *not* make a copy. It makes a List instance that
"wraps" the array.

The problem with the OP's code is the fact that you can't use
Arrays.asList on an array of primatives.

Many people have pointed this out, and have suggested that the OP use
Integer[] instead. It is a pity that Sun didn't add an Arrays.shuffle
for the primitive array types.

 

[Roedy Green]

»Changes to the returned list "write through" to the array.«

That was a surprise. I looked up Arrays.asList and there it was.

It also says .

This method also provides a convenient way to create a fixed-size list
initialized to contain several elements.

This means insert and delete would be suppressed. Shuffle just might
try to use those methods.

I got caught because I always use these idioms:

ArrayList <=> array

// NEW STYLE with generics

// converting an array to an ArrayList, with Generics
String[] animals = { "bear", "cougar", "wolverine"};
ArrayList<String> al = new ArrayList<String>( Arrays.asList( animals )
);

// converting an ArrayList to an array with generics.
String[] predators = al.toArray( new String[ al.size() ] );

// OLD STYLE, without generics

// converting an array to an ArrayList, without Generics
String[] animals = { "bear", "cougar", "wolverine"};
ArrayList al = new ArrayList( Arrays.asList( animals ) );

// converting an ArrayList to an array without generics,
String[] predators = (String[])al.toArray( new String[ al.size() ] );

 

[Piotr Kobzda]

It is a pity that Sun didn't add an Arrays.shuffle
for the primitive array types.

Maybe lack of boxing of primitive type arrays is bigger pity?

Hopefully, we can easily do something similar, see example below.


piotr


import java.util.*;

public class ArrayBoxingTest {

public static void main(String[] args) {
final int[] a = new int[] { 1, 2, 3, 4, 5 };
Collections.shuffle(new AbstractList<Integer>() {

public int size() { return a.length; }

public Integer get(int index) { return a[index]; }

public Integer set(int index, Integer element) {
Integer r = a[index];
a[index] = element;
return r;
}

});
System.out.println(Arrays.toString(a));
}
}

 

[Roedy Green]

Collections.shuffle(Arrays.asList(indicies));

This code puzzled the heck out of me.

I have done experiments and I think I now know what is going on. It
is far stranger than you would imagine.

I have posted my findings at
http://mindprod.com/jgloss/array.html#GOTCHAS

I think it fair to say OP DID find a bug in Java, or at least the
mother of all gotchas.

 

[Roedy Green]

The problem with the OP's code is the fact that you can't use
Arrays.asList on an array of primatives.

Many people have pointed this out, and have suggested that the OP use
Integer[] instead. It is a pity that Sun didn't add an Arrays.shuffle
for the primitive array types.

But you don't get any error message, just some VERY weird run-time
behaviour. see http://mindprod.com/jgloss/array.html#GOTCHAS

 

[Ken]

This code puzzled the heck out of me.

It did me too. Thank all of you for your assistance in this matter. I
understand the problem now. I'm still a bit annoyed that there isn't a
straight forward way to shuffle an array of ints given that the code is
already there hidden somewhere, but at least I understand the problem now.

 

[Roedy Green]

It did me too. Thank all of you for your assistance in this matter. I
understand the problem now. I'm still a bit annoyed that there isn't a
straight forward way to shuffle an array of ints given that the code is
already there hidden somewhere, but at least I understand the problem now.

Let's peek under the covers at java.util.Collections.shuffle.
Internally it converts to an array to shuffle!


/**
* Randomly permute the specified list using the specified source
of
* randomness. All permutations occur with equal likelihood
* assuming that the source of randomness is fair.<p>
*
* This implementation traverses the list backwards, from the last
element
* up to the second, repeatedly swapping a randomly selected
element into
* the "current position". Elements are randomly selected from
the
* portion of the list that runs from the first element to the
current
* position, inclusive.<p>
*
* This method runs in linear time. If the specified list does
not
* implement the {@link RandomAccess} interface and is large, this
* implementation dumps the specified list into an array before
shuffling
* it, and dumps the shuffled array back into the list. This
avoids the
* quadratic behavior that would result from shuffling a
"sequential
* access" list in place.
*
* @param list the list to be shuffled.
* @param rnd the source of randomness to use to shuffle the
list.
* @throws UnsupportedOperationException if the specified list or
its
* list-iterator does not support the <tt>set</tt>
operation.
*/
public static void shuffle(List<?> list, Random rnd) {
int size = list.size();
if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess)
{
for (int i=size; i>1; i--)
swap(list, i-1, rnd.nextInt(i));
} else {
Object arr[] = list.toArray();

// Shuffle array
for (int i=size; i>1; i--)
swap(arr, i-1, rnd.nextInt(i));

// Dump array back into list
ListIterator it = list.listIterator();
for (int i=0; i<arr.length; i++) {
it.next();
it.set(arr);
}
}
}

 

[Roedy Green]

Let's peek under the covers at java.util.Collections.shuffle.
Internally it converts to an array to shuffle!

Here is the guts, that handles an int[]. Note how much simpler the
code is. You can download this as part of the common11 package
at http://mindprod.com/products.html#COMMON11

/**
* Shuffles an int[], much like Collections.shuffle
* copyright (c) 2007 Roedy Green, Canadian Mind Products Shareware
that may be copied and used freely for any purpose but military.
Roedy Green<
Canadian Mind Products
#101 - 2536 Wark Street
Victoria, BC Canada
V8T 4G8
mailto:[email protected]
http://mindprod.com
*/
package com.mindprod.common11;

import java.util.Random;

/**
* Shuffles an int[], much like Collections.shuffle
*
* @author Roedy Green, Canadian Mind Products
* @version 1.0, 2007-10-03 Created with IntelliJ IDEA.
*/
public class Shuffle {

// ------------------------------ FIELDS
------------------------------

/**
* true if you want the debugging main harness.
*/
private static final boolean DEBUGGING = true;

/**
* default source of randomness for shuffling.
*/
private static Random wheel;

// -------------------------- PUBLIC STATIC METHODS
--------------------------

/**
* Works much like Collections.shuffle. Randomly permutes the
specified list
* using a default source of randomness. All permutations occur
with
* approximately equal likelihood.<p>
* <p/>
* The hedge "approximately" is used in the foregoing description
because
* default source of randomness is only approximately an unbiased
source of
* independently chosen bits. If it were a perfect source of
randomly chosen
* bits, then the algorithm would choose permutations with perfect
* uniformity.<p>
* <p/>
* This implementation traverses the list backwards, from the last
element
* up to the second, repeatedly swapping a randomly selected
element into
* the "current position". Elements are randomly selected from
the portion
* of the list that runs from the first element to the current
position,
* inclusive.<p>
*
* @param toShuffle the array to be shuffled.
*/
public static void shuffle( int[] toShuffle )
{
// wheel is initialised only once, and only if needed.
if ( wheel == null )
{
wheel = new Random();
}
shuffle( toShuffle, wheel );
}

/**
* This method uses the same technique as Collections.shuffle, but
is
* somewhat simpler with direct array access. Randomly permute the
specified
* list using the specified source of randomness. All
permutations occur
* with equal likelihood assuming that the source of randomness is
fair.<p>
* <p/>
* This implementation traverses the array backwards, from the
last element
* up to the second, repeatedly swapping a randomly selected
element into
* the "current position". Elements are randomly selected from
the portion
* of the list that runs from the first element to the current
position,
* inclusive.<p>
*
* @param toShuffle the array to be shuffled.
* @param wheel the source of randomness to use to shuffle the
list.
*/
public static void shuffle( int[] toShuffle, Random wheel )
{
for ( int i = toShuffle.length; i > 1; i-- )
{
// swap elt i-1 and a random elt 0..i-1
final int temp = toShuffle[ i - 1 ];
final int otherSlot = wheel.nextInt( i );
toShuffle[ i - 1 ] = toShuffle[ otherSlot ];
toShuffle[ otherSlot ] = temp;
}
}

// --------------------------- main() method
---------------------------

/**
* test driver demonstrate use of shuffle.
*
* @param args not used.
*/
public static void main( String[] args )
{
if ( DEBUGGING )
{
int[] deck = new int[52];
for ( int i = 0; i < 52; i++ )
{
deck[ i ] = i;
}
System.out.println( "\nbefore shuffle" );
for ( int i = 0; i < 52; i++ )
{
System.out.print( " " );
System.out.print( deck[ i ] );
}

shuffle( deck );

System.out.println( "\nafter shuffle" );

for ( int i = 0; i < 52; i++ )
{
System.out.print( " " );
System.out.print( deck[ i ] );
}
}
}
}

 

[xen]

This code puzzled the heck out of me.

I have done experiments and I think I now know what is going on. It
is far stranger than you would imagine.

I have posted my findings at
http://mindprod.com/jgloss/array.html#GOTCHAS

I think it fair to say OP DID find a bug in Java, or at least the
mother of all gotchas.

Do you even read other people's answers? Stefan Ram and I already
explained it in detail. But maybe the posts didn't reach you.

 

[Roedy Green]

Do you even read other people's answers? Stefan Ram and I already
explained it in detail. But maybe the posts didn't reach you.

Have you read my essay? I don't think you found all of what I did.
All I saw was you are not supposed to pass an int[].


http://mindprod.com/jgloss/array.html#GOTCHAS

 

[Roedy Green]

Do you even read other people's answers? Stefan Ram and I already

explained it in detail. But maybe the posts didn't reach you.

Even if you had explained it in detail, there is no harm in yet
another explanation, especially one posted on a website.

 

[Roedy Green]

Do you even read other people's answers? Stefan Ram and I already
explained it in detail. But maybe the posts didn't reach you.

You would find me less irritating if you imagined I was a sort of
translator repeating everything you said in sign language, or in
simplified language aimed an newbies.

You are imagining that whenever I say something you have already
touched on, I am correcting or publicly chastising you. Unless I
explicitly say otherwise, I am:

1. elaborating
2. simplifying
3. providing an alternative way to look at the problem.
4. asserting agreement.
5. summarising
6. attempting to turn the specific case into a general object lesson.
7. just providing repetition of an important point in slightly
different words.

The big problem most people make with me is imagining I am talking
only to them. I almost never do that. So they get insulted when I say
something they already know or repeat something they already said. I
am not talking to them, I am talking to the much larger audience of
newbies following along trying to learn something.

Similarly my primary goal in not to act as a help desk and get
problems solved rapidly as possible. I want as many people as
possible (including the questioner) to learn as much as possible in
the process. Many would see what I am doing as infuriating digression.

The error you make is
1. presuming everyone reads your every word.
2. everyone understands you every word. After all you do.

Experiments show only a tiny fraction sinks in. You need a surprising
amount of repetition of anything important. So often missing a single
phrase can make everything that follows into Greek. A slightly
different wording produces different ambiguities which may be enough
to get them back on track.

 

[xen]

On Thu, 04 Oct 2007 01:45:46 GMT, Roedy Green

The reason I find you irritating is not because you elaborate, or
simplify, or translate, or create a webbased explanation including
code example. Those are all honorable things.

The reason is that I first state

If you call asList() on an int[], you will get a List<int[]> with one
element: the int[] you supplied. If you call shuffle on that list,
nothing will change in the int[].

If you call it with an array of a primitive type, then it cannot be
treated as a T[] because generic types cannot be primitives. Instead,
because int[] itself is an object, it matches the T in the signature
and is wrapped inside an array. So what actually gets passed is not
your int[], but an array of int[] with one element.

And then three hours later, you state

This code puzzled the heck out of me.

I have done experiments and I think I now know what is going on. It
is far stranger than you would imagine.

suggesting to the sequential reader that you have found something new,
subsequently stating

int[] becomes the one and only element of a List of <int[]> objects!!

While I don't mind you experimenting and coming to your own
conclusions (as I have done), it would be nice and respectful to at
least include a reference or acknowledgement to the other posters, if
you are aware of them, stating that you agree with their findings and
that you have elaborated on it to produce a code demonstration,
located on your website. You are not only targetting an audience of
newbies, you are also participating in a thread, and we are not here
to compete which each other for credits, unless you are purposefully
and irreverently trying to direct as many readers as possible to your
website. So it's not about repetition, it's about acknowledgement.

Have you read my essay? I don't think you found all of what I did.
All I saw was you are not supposed to pass an int[].

Yes I read your code example and it certainly didn't explain more than
what I did, although I agree that my explanation could be improved,
for example by stating that the int[] that is wrapped inside an array
is then used as the backing for the List, thus producing a List that
is backed by an array with one int[] element, but that's not the
point.

 

[xen]

Btw,

I would suggest to change

* You don't have the usual asList backing int[] array or a backing Integer[] array.

into something more understandable. What does »asList backing int[]
array« mean? asList is not backing anything, nor is it backed by
anything. And even if it was, I don't understand it.