如何选择集合中最大的元素之一

Question

我有一个元组列表,我想找到具有最大值的元组x.在有多个最大值的情况下x,我想随机选择一个.我无法弄清楚如何实现这种随机选择功能.以下是我到目前为止的代码:

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

事实证明,Misha的一次通过随机选择器(很好的工作,+ 1)可以与我的一次通过最大值收集器从这个其他答案组合成一个收集器.这允许在单次通过中选择来自该组最大值的随机元素.

这是合并的收藏家:

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);
}

你这样调用它:

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

Answer 2

简单的回答是先洗牌:

List<Tuple<Integer, String>> copy = new ArrayList<>(list);
Collections.shuffle(copy);
Tuple<Integer, String> largestTuple = Collections.max(copy, Comparator.comparingInt(t -> t.x)); // credit @Holger

返回的元素max()受到遭遇顺序的影响,因此改组有效地使其随机化.

如果列表不是太大(不是数千个元素),则shuffle将非常快.

我制作了一份清单副本,以免影响原始清单的顺序.如果这不重要,只需使用原始列表进行随机播放.

Answer 3

对于大多数实际用途,@ Bohemian基于shuffle的解决方案是最好的,但是由于你表达了对内存中常量的方法的兴趣,你可以使用Collector选择随机元素的自定义来实现:

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);
}

有了这个,你可以通过一次找到最大的x,另一次来选择一个随机匹配的元组:

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();