随机/随机比较器
有没有办法模拟Collections.shuffle的行为而没有比较器易受排序算法实现的影响,结果是安全的?
我的意思是不打破可比合同等。
在不违反合同的情况下实施真正的“改组比较器”是不可能的。 Comparator
合同的一个基本方面是结果是可重现的,因此必须修复特定Comparator
实例的顺序。
当然,您可以使用混洗操作预先初始化该固定排序,并创建一个比较器,该比较器将精确地建立此排序。 例如
List ordering=new ArrayList<>(list); Collections.shuffle(ordering); list.sort(Comparator.comparingInt(ordering::indexOf));
虽然这有点无意义。 很明显,这个比较器不能用于包含不在ordering
列表中的元素的集合。
或者,您可以使用首先没有排序的值的稳定属性作为排序条件,例如哈希码。 这可以通过稳定但随机化的变换来增强,例如
public static Comparator 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 list=Arrays.asList("hello", "now", "shuffle", "this", "!"); list.sort(randomOrder()); System.out.println(list); list.sort(randomOrder()); System.out.println(list);
关键点是每个Comparator
实例代表一个随机选择但固定的排序,我们创建一个新的Comparator
实例来请求不同的排序。 因此,没有Comparator
违反合同。
请注意,此Comparator
看起来有点复杂,因为它必须关心可能的哈希冲突。 它将使用length
属性(也是随机的)然后对于具有相同哈希码和长度的String
,它将简单地回退到自然或逆序,这不太可能引人注意,因为它只影响这些不常见对的关系。
如果为没有冲突的值(例如Integer
实例)创建这样的比较器或覆盖定义相等的值的所有属性(例如, Point
x
和y
两者),比较器看起来会更简单。
当元素的类型未知时,比前一个答案更通用:
public static Comparator shuffle() { final Map
也可以在流中使用:
list.stream().sorted(Streams.shuffle()).collect(Collectors.toList())
可能会以某种方式发生冲突,因此可以使用HashSet
为UUID
扩展以检查此情况
这是我的解决方案:
List st = Arrays.asList("aaaa","bbbb","cccc"); System.err.println(st.stream().sorted((o1, o2) -> RandomUtils.nextInt(0, 2)-1).findFirst().get());