随机/随机比较器 [英] Shuffle/Random comparator

问题描述

有没有什么方法来模拟Collections.shuffle的行为，没有比较器容易排序算法实现结果是安全的？

IS there any way to emulate the behavior of Collections.shuffle without a comparator being vulnerable to the sorting algorithm implementation for the result to be safe?

我的意思不是打破可比合同等。

I mean not breaking the comparable contract etc..

推荐答案

不可能实现一个真正的洗牌比较 Comparator 合约的一个基本方面是结果是可重现的，因此特定比较器实例必须是固定的。

It is impossible to implement a real "shuffling comparator" without breaking the contract. One fundamental aspect of the Comparator contract is that the results are reproducible so the ordering of a particular Comparator instance must be fixed.

当然，你可以使用shuffling操作来预先初始化固定排序，并创建一个比较器，它将确定这个排序。例如

Of course, you could pre-initialize that fixed ordering using a shuffling operation and create a comparator which will establish exactly this ordering. E.g.

List<ElementType> ordering=new ArrayList<>(list);
Collections.shuffle(ordering);

list.sort(Comparator.comparingInt(ordering::indexOf));

虽然它有点无意义。很明显，这个比较不能用于包含订单列表中的元素的集合。

though it is a bit pointless. It’s clear that this comparator must not be used for collections containing elements not being in the ordering list.

或者，您可以使用首先没有排序作为排序标准的值的stable属性，例如哈希码。这可以通过稳定但可随机化的变换来增强，例如

Alternatively you can use a stable property of the values which hasn’t an ordering in the first place as sort criteria, e.g. the hash code. This can be augmented by a stable but randomizable transformation, e.g.

public static Comparator<String> randomOrder() {
    ThreadLocalRandom r = ThreadLocalRandom.current();
    int x = r.nextInt(), y = r.nextInt();
    boolean b = r.nextBoolean();
    return Comparator.comparingInt((String s)->s.hashCode()^x)
     .thenComparingInt(s->s.length()^y)
     .thenComparing(b? Comparator.naturalOrder(): Comparator.reverseOrder());
}

List<String> list=Arrays.asList("hello", "now", "shuffle", "this", "!");
list.sort(randomOrder());
System.out.println(list);
list.sort(randomOrder());
System.out.println(list);

关键点是每个 Comparator 表示随机选择但固定的顺序，我们创建一个新的 Comparator 实例来请求不同的排序。因此， Comparator 违反了合同。

The key point is that each Comparator instance represents a randomly chosen but fixed ordering and we create a new Comparator instance to request a different ordering. Therefore, no Comparator violates the contract.

请注意，此 Comparator 看起来有点复杂，因为它必须关心可能的哈希冲突。它将使用 length 属性（也随机化）和 String s具有相同的哈希码和长度将简单地回退到自然或颠倒的顺序，这不太可能是明显的，因为它只影响这些不常见的对的关系。

Note that this Comparator looks a bit complicated as it has to care about possible hash collisions. It will resort to the length property (also randomized) then and for Strings having the same hash code and length it will simply fall back to either natural or reversed order which is unlikely to be noticeable as it only affects the relation of these uncommon pairs.

如果你创建一个比较器的值没有冲突（例如 Integer 实例）或覆盖定义等于的值的所有属性（例如 x y ，一个点），比较器将看起来更简单。

If you create such a comparator for values without collisions (e.g. Integer instances) or covering all properties of the values which define the equality (e.g. both, x and y, of a Point), the comparator will look much simpler.

这篇关于随机/随机比较器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！