Collections.shuffle to accept RandomGenerator

[Tagir Valeev]

Thanks, Paul, Jason. I've filed an issue:
https://bugs.openjdk.org/browse/JDK-8294693

I'm not sure about the lifting shuffle() and making it an instance
method of List interface. The shuffle() is used much less often,
compared to sort(). Also, it produces an unspecified side-effect.
Namely, it updates the state of the supplied RandomGenerator.
Currently, it does this in a very stable way, calling nextInt() size-1
times for any list implementation. So if I initialize a RNG with a
specific seed, then shuffle several lists, they will be shuffled in
predictable manner, regardless of a particular list implementation.
This might be desired, e.g., to write tests or reproduce problems. If
we move it to an instance method, implementations might vary, and
passing identical RNG may produce different shuffle order for lists
with identical content but having different implementations. Moreover,
it may even leave RNG in a different state afterwards which may affect
subsequent operations performed with the same RNG. With sorting, any
implementation must produce the same result, so such questions don't
rise.

With best regards,
Tagir Valeev

On Thu, Sep 29, 2022 at 4:27 AM Jason Mehrens <jason_mehrens at hotmail.com> wrote:
>
> JDK20 has Random.from(RandomGenerator) which could be used to do something like Collections.shuffle(List, Random.from(rg)).
>
> List.shuffle(RandomGenerator ) would allow for more efficient CopyOnWriteArrayList shuffle.
>
> Jason
>
> ________________________________________
> From: core-libs-dev <core-libs-dev-retn at openjdk.org> on behalf of Paul Sandoz <paul.sandoz at oracle.com>
> Sent: Wednesday, September 28, 2022 10:36 AM
> To: Tagir Valeev
> Cc: core-libs-dev at openjdk.org
> Subject: Re: Collections.shuffle to accept RandomGenerator
>
> That looks reasonable.
>
> Thinking a little more broadly.
>
> We could also change Collections.shuffle(List) to use ThreadLocalRandom so it does not have to cache the Random instance, plus it has better concurrent and PRNG properties. The spec does not describe the precise details of randomness.
>
> It’s tempting to lift Collections.shuffle(List, RandomGenerator) to List.shuffle(RandomGenerator ), similar to what we did for Collections.sort, to align with that pattern and which also aligns with reverse of sequenced collections. There is likely not much performance advantage to do doing so as there was with sort, but that location is much easier to find and use IMHO. Since the method accepts RandomGenerator the compatibility risk would likely be low.
>
> Paul.
>
> > On Sep 27, 2022, at 3:11 AM, Tagir Valeev <amaembo at gmail.com> wrote:
> >
> > Hello!
> >
> > Currently, Collections.shuffle(List, Random) accepts an outdated
> > Random class instead of RandomGenerator interface. It looks like,
> > RandomGenerator would suffice. The code change looks trivial (aside
> > from documentation and testing), as shuffle() implementation does not
> > need anything except nextInt:
> >
> > diff --git a/src/java.base/share/classes/java/util/Collections.java
> > b/src/java.base/share/classes/java/util/Collections.java
> > --- a/src/java.base/share/classes/java/util/Collections.java (revision
> > cab590517bf705418c7376edd5d7066b13b6dde8)
> > +++ b/src/java.base/share/classes/java/util/Collections.java (date
> > 1664273240190)
> > @@ -37,6 +37,7 @@
> > import java.util.function.IntFunction;
> > import java.util.function.Predicate;
> > import java.util.function.UnaryOperator;
> > +import java.util.random.RandomGenerator;
> > import java.util.stream.IntStream;
> > import java.util.stream.Stream;
> > import java.util.stream.StreamSupport;
> > @@ -454,8 +455,12 @@
> >      * @throws UnsupportedOperationException if the specified list or its
> >      *         list-iterator does not support the {@code set} operation.
> >      */
> > -    @SuppressWarnings({"rawtypes", "unchecked"})
> >     public static void shuffle(List<?> list, Random rnd) {
> > +        shuffle(list, (RandomGenerator) rnd);
> > +    }
> > +
> > +    @SuppressWarnings({"rawtypes", "unchecked"})
> > +    public static void shuffle(List<?> list, RandomGenerator rnd) {
> >         int size = list.size();
> >         if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
> >             for (int i=size; i>1; i--)
> >
> > What do you think? Should we implement this improvement? I think I can
> > contribute if there's a general agreement that such an enhancement
> > would be useful.
> >
> > With best regards,
> > Tagir Valeev
>