如何选择集合中最大的元素之一
我有一个元组列表，我想找到具有最大x值的元组。 在存在多个最大x值的情况下，我想随机选择一个。 我无法弄清楚如何实现这种随机选择function。 以下是我到目前为止的代码：
public void testSelectRandomFromLargestVals() { List<Tuple> 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> 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 { 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; } }
事实certificate， Misha的一次通过随机选择器（很好的工作，+ 1）可以与我的一次通过最大值收集器从这个其他答案组合成一个收集器。 这允许在单次通过中选择来自该组最大值的随机元素。
这是合并的collections家：
static Collector> rndMax(Comparator 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 finish() { return cnt == 0 ? Optional.empty() : Optional.of(val); } } return Collector.of(RndMax::new, RndMax::add, RndMax::merge, RndMax::finish); }
你这样调用它：
List> list = ... ; Optional> max = list.stream().collect(rndMax(Comparator.comparingInt(t -> tx)));
简单的回答是先洗牌：
List> copy = new ArrayList<>(list); Collections.shuffle(copy); Tuple largestTuple = Collections.max(copy, Comparator.comparingInt(t -> tx)); // credit @Holger
max()返回的元素受到遭遇顺序的影响，因此改组有效地使其随机化。
如果列表不是太大（不是数千个元素），那么shuffle将非常快。
我制作了一份清单，以免影响原始清单的顺序。 如果这不重要，只需使用原始列表进行随机播放。
对于大多数实际用途，@ Bohemian基于shuffle的解决方案是最好的，但由于您表达了对内存中常量的方法的兴趣，您可以使用选择随机元素的自定义Collector来实现：
public static Collector> 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 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 -> tx).max() .getAsInt(); // or throw if list is empty Tuple randomLargestTuple = list.stream() .filter(t -> largestX == tx) .collect(random()) .get();
可能不是最佳解决方案
final Optional> largestTuple = list.stream().max((t1, t2) -> Integer.compare(t1.x, t2.x)); final List> allMaxElements = list.stream().filter(z -> zx == largestTuple.get().x).collect(Collectors.toList()); final Tuple randomMaxTuple = allMaxElements.get(new SecureRandom().nextInt(allMaxElements.size())); System.out.println("Largest tuple is: " + randomMaxTuple.x + " value is: " + randomMaxTuple.y);
在equals和hashCode方法上，您可以使用番石榴
@Override public int hashCode() { return com.google.common.base.Objects.hashCode(x, y); } @Override public boolean equals(final Object object) { if (object instanceof Tuple) { final Tuple that = (Tuple) object; return com.google.common.base.Objects.equal(this.x, that.x) && com.google.common.base.Objects.equal(this.y, that.y); } return false; }
您可以将元组收集到TreeMap ，其中键是元组中每个可能的x值，值是具有该x值的所有元组的列表：
TreeMap>> map = list.stream() .collect(Collectors.groupingBy( t -> tx, TreeMap::new, Collectors.toList()));
然后，您可以使用TreeMap.lastEntry()方法获取具有最大键的条目：
List> largestTuples = map.lastEntry().getValue();
然后，只需从largestTuples列表中随机选择一个元素。
@Misha的自定义Collector也可以使用匿名类型而不是本地类来实现：
public static Collector> random() { return Collector.of( () -> new Object() { T val; int cnt; }, (this_, t) -> { this_.cnt++; if (ThreadLocalRandom.current().nextInt(this_.cnt) == 0) { this_.val = t; } }, (this_, other) -> { this_.cnt += other.cnt; if (ThreadLocalRandom.current().nextInt(this_.cnt) < other.cnt) { this_.val = other.val; } return this_; }, this_ -> this_.cnt == 0 ? Optional.empty() : Optional.of(this_.val) ); }