How to choose one of the largest elements in a collection

Question

I have a list of tuples, and I want to find the tuples with the largest x value. In the case where there are multiple largest x values, I want to choose one at random. I can't figure out how to implement this random selection functionality. Below is the code I have so far:

public void testSelectRandomFromLargestVals() {
    List<Tuple<Integer, String>> list = new ArrayList<>();
    list.add(new Tuple<>(5, "five-1"));
    list.add(new Tuple<>(2, "two"));
    list.add(new Tuple<>(3, "three"));
    list.add(new Tuple<>(5, "five-2"));
    list.add(new Tuple<>(5, "five-3"));

    Optional<Tuple<Integer, String>> largestTuple = list.stream().max((t1, t2) -> Integer.compare(t1.x, t2.x));
    System.out.println("Largest tuple is: " + largestTuple.get().x + " value is: " + largestTuple.get().y);
}

public class Tuple<X, Y> {
    public final X x;
    public final Y y;
    public Tuple(X x, Y y) {
        this.x = x;
        this.y = y;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Tuple<?, ?> tuple = (Tuple<?, ?>) o;
        if (!x.equals(tuple.x)) return false;
        return y.equals(tuple.y);
    }
    @Override
    public int hashCode() {
        int result = x.hashCode();
        result = 31 * result + y.hashCode();
        return result;
    }
}

Answer 1

It turns out that Misha's one-pass random selector (nice work, +1) can be combined with my one-pass max-value collector from this other answer into a single collector. This allows a random element from the set of maximal ones to be selected in a single pass.

Here's the merged collector:

static <T> Collector<T, ?, Optional<T>> rndMax(Comparator<? super T> cmp) {
    class RndMax {
        T val;
        int cnt;

        void add(T t) {
            int c;
            if (cnt == 0 || (c = cmp.compare(t, val)) > 0) {
                cnt = 1;
                val = t;
            } else if (c == 0) {
                cnt++;
                if (ThreadLocalRandom.current().nextInt(cnt) == 0) {
                    val = t;
                }
            }
        }

        RndMax merge(RndMax other) {
            if (cnt == 0) {
                return other;
            }

            if (other.cnt == 0) {
                return this;
            }

            int c = cmp.compare(val, other.val);
            if (c < 0) {
                return other;
            } else if (c > 0) {
                return this;
            } else {
                cnt += other.cnt;
                if (ThreadLocalRandom.current().nextInt(cnt) < other.cnt) {
                    val = other.val;
                }
                return this;
            }
        }

        Optional<T> finish() {
            return cnt == 0 ? Optional.empty() : Optional.of(val);
        }
    }

    return Collector.of(RndMax::new, RndMax::add, RndMax::merge, RndMax::finish);
}

You'd invoke it like this:

List<Tuple<Integer,String>> list = ... ;
Optional<Tuple<Integer,String>> max =
    list.stream().collect(rndMax(Comparator.comparingInt(t -> t.x)));

Answer 2

For most practical purposes, @Bohemian's shuffle-based solution is the best, but since you expressed an interest in an approach that's constant in memory, you can do it with a custom Collector that chooses a random element:

public static <T> Collector<T, ?, Optional<T>> random() {
    class Rnd {

        T val;
        int cnt;

        void add(T t) {
            cnt++;
            if (ThreadLocalRandom.current().nextInt(cnt) == 0) {
                val = t;
            }
        }

        Rnd merge(Rnd other) {
            cnt += other.cnt;
            if (ThreadLocalRandom.current().nextInt(cnt) < other.cnt) {
                val = other.val;
            }
            return this;
        }

        Optional<T> finish() {
            return cnt == 0 ? Optional.empty() : Optional.of(val);
        }

    }

    return Collector.of(Rnd::new, Rnd::add, Rnd::merge, Rnd::finish);
}

With that, you can make one pass to find the largest x and another to pick a random matching tuple:

int largestX = list.stream().mapToInt(t -> t.x).max()
        .getAsInt();  // or throw if list is empty

Tuple<Integer, String> randomLargestTuple = list.stream()
        .filter(t -> largestX == t.x)
        .collect(random())
        .get();