Shuffle Stream using sort - IllegalArgumentException

Question

I have this commands:

list.stream()
    .filter(e -> ...)
    .sorted(comparatorShuffle())
    .findAny()
    .orElse(null);

This is comparatorShuffle():

public static <E> Comparator<E> comparatorShuffle(){

    return new Comparator<>(){
        private final List<Integer> temp = List.of(-1, 1);
        private final Random random = new Random();
        @Override
        @SuppressWarnings("ComparatorMethodParameterNotUsed")
        public int compare(E o1, E o2){
            return temp.get(random.nextInt(temp.size()));
        }
    };

}

Sometimes I get an exception: IllegalArgumentException: Comparison method violates its general contract!

I understand why I get this, it's because the sort(it's random) don't respect the rule: if A > B && B > C then A > C

There is a way to suppress/ignore this error? Or another way to shuffle the stream without using collect?

Your comparator is not a proper comparator. It violates the comparator protocol. This is also not a sensible way to randomly sample or shuffle in the first place. — kaya3, Oct 01 '21 at 12:08
@kaya3 "It violates the comparator protocol" OP knows this ("I understand why I get this"). — Andy Turner, Oct 01 '21 at 12:10

Andy Turner · Accepted Answer · 2021-10-01T12:13:17.773

5

There is a way to suppress/ignore this error?

No.

You're not really shuffling here, you're ostensibly just trying to pick a random element from the stream.

To do this, you can pair up the elements with a random number and pick the min/max:

...
.map(a -> new AbstractMap.SimpleEntry<>(Math.random(), a))
.min(Map.Entry.comparingByKey())
.map(Map.Entry::getValue)
.orElse(null)

Alternatively, you can write a custom collector which randomly picks between two things when merging:

.collect(
    Collector.of(
        // Use Optional.empty() as the identity element, if the stream is empty.
        Optional::empty,
        // Optionalize the element, taking it randomly or if we have the identity element.
        (a, b) -> a.isEmpty() || Math.random() > 0.5 ? Optional.of(b) : a,
        // Merge.
        (a, b) -> Math.random() > 0.5 ? b : a,
        // Unwrap the value.
        r -> r.orElse(null)))

The big problem with this alternative is it doesn't pick uniformly from the stream (you're not equally likely to get any one of the elements from the stream), whereas you are with the first way.

edited Oct 01 '21 at 12:13

answered Oct 01 '21 at 11:37

Andy Turner

137,514
11
162
243

`You're not really shuffling here, you're ostensibly just trying to pick a random element from the stream.` true – KunLun Oct 01 '21 at 11:40
I have a warning at `Optional::of` - `Static method referenced through receiver` – KunLun Oct 01 '21 at 11:42
@kaya3 yep, I was concerned about that. And since the "alternative" ended up neater, I swapped them round. – Andy Turner Oct 01 '21 at 12:11
That's weird, your edit was 4 minutes before my comment, but SO still showed me the old version when I commented. – kaya3 Oct 01 '21 at 12:12
1

`new AbstractMap.SimpleEntry<>(k, v)` ... or just `Map.entry(k, v)`. – MC Emperor Oct 01 '21 at 12:21
Your solution with `Map.Entry` is ok for me. Thank you. But also I will gonna look for something which can be implemented in a method and reuse. – KunLun Oct 01 '21 at 12:24
@KunLun you can put the `Map.Entry` way in a method. – Andy Turner Oct 01 '21 at 12:27
2

You can actually solve the non-uniformity problem using [reservoir sampling](https://en.wikipedia.org/wiki/Reservoir_sampling). The simplest version would be: where your code uses `Math.random() > 0.5`, instead make the threshold be `1 / [num items seen so far]`. – jacobm Oct 01 '21 at 12:27
1

If you want a correct `Collector` picking one random element, consider [this answer](https://stackoverflow.com/a/35998302/2711488). If you want to sort all elements in an order that’s actually shuffling, see [Shuffle/Random comparator](https://stackoverflow.com/q/29241746/2711488). – Holger Oct 04 '21 at 10:21

Shuffle Stream using sort - IllegalArgumentException

1 Answers1