两种改组方法中哪一种效果更好？

Question

我试图在List中随机洗牌整数集合,我想出了两种改组方法来完成这项工作.但是,我不确定哪一个效果更好？有没有人有任何意见或建议？

public class TheCollectionInterface {

    public static <E> void swap(List<E> list1, int i, int j) {
        E temp = list1.get(i);
        list1.set(i, list1.get(j));
        list1.set(j, temp);
    }

// Alternative version:    
//    public static void shuffling(List<?> list, Random rnd){
//        for(int i = list.size(); i >= 1; i--){
//            swap(list, i - 1, rnd.nextInt(i));
//        }
//    }


    public static <E> void shuffling(List<E> list1, Random rnd) {
        for (int i = list1.size(); i >= 1; i--){
            swap(list1, i - 1, rnd.nextInt(list1.size()));
        }
    }

    public static void main(String[] args) {

        List<Integer> li2 = Arrays.asList(1,2,3,4,5,6,7,8,9);

        Random r1 = new Random();

        TheCollectionInterface.shuffling(li2, r1);

        System.out.println(li2);
    }
}

Answer 1

如果每个可能的结果同样可能,则通常认为改组算法是好的.您的混洗算法的"替代版本"称为Fisher-Yates算法.给定足够好的随机性源,该算法可证明地以相等的概率生成输入的每个可能的排列.JDK Collections.shuffle()方法使用此算法.

未注释的算法理论上较差,这很容易证明.维基百科有关Fisher-Yates shuffle的文章中给出了为何如此的解释.引用该文章,(为清晰起见编辑)

实现Fisher-Yates shuffle时常见的错误是从错误的范围中选择随机数.有缺陷的算法似乎可以正常工作,但它不会以相同的概率产生每个可能的排列.始终在每次迭代时从整个有效数组索引范围中选择j会产生偏差的结果,尽管不那么明显.这可以从这样的事实看出,即这样做产生了n^n不同的可能的交换序列,而只有n!n元素阵列的可能的排列.因为当(因为后者可被整除,其中没有主要因素共同使用时,一些排列必须由更多的互换序列产生,而不是其他因素),n^n因此永远不能被可分割.n!n > 2n?1n)n^n

在此上下文中,j是目标槽,用于i - 1交换元素.看起来可能会将当前元素与0之间的所有元素进行交换,并list.size()提供更好的随机播放,因为它似乎可以"更多"地进行洗牌.实际上,存在比Fisher-Yates更多不同的可能序列,但额外的序列增加了偏差,降低了混洗的质量.

维基百科的文章详细介绍了为什么会这样,并且它显示了改组3元素阵列的每个结果的概率.

这很容易证明.拿一个3元素的数组或列表并将其洗牌,比如说,一百万次,并计算每种可能的六种排列的出现频率.我用Fisher-Yates做了这个,结果都在±0.3%之内.在全范围随机播放中,三种排列比其他三种排列频率高出约20%.

Fisher-Yates shuffle算法,你标记为"替代版本",显然是优越的方法.