为什么 Collections.shuffle（）算法比我的实现效果更好

shuffle java

2022-09-02 23:39:08

Collections.shuffle()向后遍历 a 的每个索引，然后将其与包含或之前的随机索引交换。我想知道为什么，所以我尝试做同样的事情，但与.CollectionCollection

以下是 Collections.shuffle（）代码的洗牌部分：

for (int i=size; i>1; i--)
    swap(arr, i-1, rnd.nextInt(i));

这是我的算法：

Random r = new Random();
for (int i = 0; i < a.size(); i++) {
    int index = r.nextInt(a.size());
    int temp = a.get(i);
    a.set(i, a.get(index));
    a.set(index, temp);
}

我发现，当我在同一个代码上运行两者一百万次时，它的分布比我的代码均匀得多。另外，在以下位置运行代码时：Collections.shuffle()ArrayList

[0, 1, 2, 3, 4]

似乎以下排列始终最常发生：

[1, 0, 3, 4, 2]
[1， 2， 3， 4， 0]
[1， 2， 0， 4， 3]
[0， 2， 3， 4， 1]
[1， 2， 3， 0， 4]

有人可以解释一下为什么吗？

答案 1

Collections.Shuffle()做一个费舍尔-耶茨洗牌。这是一种更均匀分布的洗牌形式，不会重新洗牌以前可能已经洗牌的内容，而不是你的算法。

你的算法（也称为朴素实现）的作用是，它会随机选择任何数组索引并将其洗牌，这意味着它很有可能选择以前已经洗牌过的相同索引。

Fisher-Yates shuffle（也称为Donald Knuth Shuffle）是一种无偏算法，它以同样可能的概率对数组中的项目进行洗牌。它避免了两次“移动”相同物体的机会。

以下是我们自己的Jeff Atwood在Code Horror上对Fisher Yates Shuffle的一个很好的解释，他讨论了随机洗牌与Fisher Yates洗牌的天真实现。

另请参阅有关Java实现的SO问题。它提到了你问的问题。如果您愿意，也可以查看源代码，如前所述。我通过在前5个链接中谷歌搜索找到它。Collections.shuffle()

为了进一步讨论这个问题，与幼稚的实现相比，使用Fisher-Yates洗牌总是一个好主意，特别是在需要更高级别随机性的实现中（例如洗牌扑克牌），以避免引入赔率和不公平的游戏。如果机会游戏是基于我们幼稚的实现来实现的，那将不是一件好事，因为偏见导致了你所观察到的，同样的排列似乎比其他排列更频繁地出现。

最后，正如用户@jmruc提到的，这里有一个关于可视化算法的非常好的教程，它包含Fisher-Yates shuffle以及其他算法，所有这些都呈现得很漂亮。如果您更像是可视化师，可能会帮助您了解这些概念：Mike Bostock的可视化算法

答案 2

这是对费舍尔-耶茨的另一种解释。

请考虑以下方法：

有两个列表，A 和 B。最初，所有元素都在列表 A 上，因此列表 B 为空。
在每一步：

从列表 A 上的当前元素中以均匀的概率进行选取。

将列表 A 置换，使所选元素成为最后一个元素。

从列表 A 中删除最后一个元素，并将其追加到列表 B。
当列表 A 为空时，返回列表 B。

我发现这个算法很容易理解和可视化。

在第一步中选择给定项目的概率为。给定项目在第二步中被选中的概率是其在第一步未被选中的概率，乘以在第二步中被选中的概率，给定它仍然在列表A上，。该产品是 .1/n(n-1)/n1/(n-1)1/n

同样，在移动了两个项目后，它仍有可能在列表 A 上，因此有可能成为第三个被选中的项目。((n-1)/n)*((n-2)/(n-1)) = (n-2)/n1/n

通常，选择项目后仍在列表 A 上的概率为。假设项目仍在列表 A 上，则在下一步中选择的概率为，因此当列表 A 具有项目时，在步骤中选择的无条件概率为。k((n-1)/n)*((n-2)/(n-1))*...*((n-k)/(n-k+1)) = (n-k)/n1/(n-k)(n-k)((n-k)/n)*(1/(n-k)) = 1/n

Fisher-Yates只是一个算法，具有两个列表，其总长度始终是，串联在单个数组中。在每个步骤中，它以均匀的概率从列表 A 中选择一个元素，置换列表 A 以将该元素放在列表 B 的旁边，然后移动边界，使其从列表 A 元素更改为列表 B 中最近添加的元素。n

为什么 Collections.shuffle（） 算法比我的实现效果更好

为什么 Collections.shuffle（）算法比我的实现效果更好