为什么这个简单的洗牌算法——按 random() 排序——有偏差？
Why is this simple shuffle algorithm — sorting by random() — biased?
在 this thread 中，我们看到了这个简单而漂亮的随机排列数组的算法：
function shuffle<T>(array: T[]): T[] {
return array.sort(() => Math.random() - 0.5);
}
而且我们可以看到评论说这个算法有偏见。但是我做了一个简单的脚本来创建数组的最后一个元素在洗牌后结束的索引的经验概率分布：
function shuffle(array) {
return array.sort(() => Math.random() - 0.5);
}
function generateDistribution(iterations = 10_000, arrayLength = 10) {
const testArray = Array(arrayLength - 1).fill("test");
const testTarget = "target";
testArray.push(testTarget);
const results = {};
for (let index = 0; index < iterations; index++) {
countTargetPosition();
}
return generateResult();
function countTargetPosition() {
const shuffled = shuffle(testArray);
shuffled.forEach((value, index) => {
if (value === testTarget) {
results[index] = results[index] + 1 || 1;
}
});
}
function generateResult() {
return Object.entries(results).map(([index, count]) => {
return {
[index]: count / iterations,
};
});
}
}
const result = generateDistribution()
document.write(`<h1>Result</h1>`)
document.write(JSON.stringify(result))
我们期望无偏算法具有均匀分布，结果非常接近，即使对于具有 100 个元素的数组也是如此。为什么这个算法会有偏差？
JavaScript 没有为 sort 指定特定的算法，并且根据所使用的特定排序算法，这种改组算法可能会给出非常有偏见的结果。下面，我描述了一些简单的、众所周知的排序算法，它们给出了非常有偏见的结果；我证明了 Firefox 和 Chrome 都对长度为 4 的数组给出了非常有偏见的结果；我给出了为什么 any 排序算法会给出有偏差的结果的一般性论证（尽管不一定像这些明确的例子那样 as 有偏差）。
Example #1 — selection sort. 在选择排序中，我们首先找到最小的元素并将其放在索引 0 处，然后找到第二小的元素并且将其放在索引 1 处，依此类推。需要注意的重要一点是，使用比较函数 () => Math.random() - 0.5，比较的每个参数都有相同的机会被视为“更少”。因此，如果您通过遍历数组并将每个元素与先前最少的元素进行比较来找到最少的元素，那么您有 50% 的机会认为最后一个元素是最少的，有 25% 的机会您会认为倒数第二个元素最少，有 12.5% 的机会认为倒数第三个元素最少，等等，因此给出了哪个元素先出现的偏向分布。
示例 2 — insertion sort. 在插入排序中，我们通过依次获取每个元素并将其插入到数组中来构建数组的“已排序”部分排序部分中的正确位置（将所有更大的元素移动一个以为它腾出空间）。这意味着最后一个元素有 50% 的机会被认为是最少的，有 25% 的机会被认为是第二少的，有 12.5% 的机会被认为是第三少的，等等。
示例 #3 和 #4 — 无论 Firefox 和 Chrome 用于四元素数组。
现在，实际上，我不希望 sort 的任何实现完全使用 选择排序或插入排序，因为还有其他算法比对大输入有效。但是复杂的现代排序算法，例如 Timsort，结合了多种不同的排序算法，根据输入的大小和特征（或部分输入，因为它们可以以复杂的方式组合这些算法）在它们之间进行自适应选择).因此，作为实验，我在数组 [1, 2, 3, 4] 上尝试了这种随机播放算法——一个足够短的数组，似乎 sort 实现可能只对整个数组使用插入排序。
这是我使用的代码：
const counts = {};
for (let i = 0; i < 1_000_000; ++i) {
const permutation = [1, 2, 3, 4].sort(() => Math.random() - 0.5).join('');
counts[permutation] = (counts[permutation]||0) + 1;
}
const result = [];
for (let permutation in counts) {
result.push(permutation + ': ' + counts[permutation]);
}
result.join('\n')
我在 Firefox 和 Chrome 中都试过了。
在 Firefox 中，我得到了这样的结果：
1234: 125747
1243: 62365
1324: 62299
1342: 31003
1423: 31320
1432: 15635
2134: 125380
2143: 62216
2314: 62615
2341: 31255
2413: 31509
2431: 15608
3124: 62377
3142: 31166
3214: 62194
3241: 31293
3412: 15631
3421: 15782
4123: 31056
4132: 15672
4213: 31231
4231: 15319
4312: 15727
4321: 15600
这与我对插入排序的期望不符，因此它一定做了一些不同的事情，但无论如何，它显示出非常明显的偏见。一些排列在 1/64 的时间内发生（一百万次中有 15,625 次，plus/minus 随机噪声），一些在 1/32 的时间内发生（31,250），一些在 1/16 的时间内发生（62,500），有些发生在 1/8 的时间 (125,000)；所以一些排列是其他排列的八倍。
在Chrome中，我得到了这样的结果：
1234: 187029
1243: 62380
1324: 15409
1342: 15679
1423: 62476
1432: 15368
2134: 31280
2143: 31291
2314: 15683
2341: 15482
2413: 31482
2431: 15732
3124: 15786
3142: 15692
3214: 47186
3241: 47092
3412: 15509
3421: 46600
4123: 62825
4132: 15595
4213: 31091
4231: 15763
4312: 15624
4321: 171946
也不符合我对插入排序的期望，并且比 Firefox 中的分布更复杂一点（我想我看到了大约 3/16 (187,500) 和 3/64ths (46,875)？），但实际上偏差更大，最常见和最不常见的排列之间有十二倍的差异。
示例 #5 — 任意 确定性排序算法。 我在上面给出了各种极端偏差的示例；但实际上，any 排序算法预计会产生 some 偏差，因为如果算法做最坏情况 k[=在长度为 n 的数组上进行 97=] 次比较，每次比较都有 50–50 次拆分，则任何给定排列的概率必须是 1 的倍数/2k，而无偏洗牌器必须给每个排列概率1/n!，不会是1[的倍数=110=]/2k 如果 n ≥ 3（因为 n! 将是 3 的倍数）。
也就是说，我应该承认这些偏差可能小到无关紧要；毕竟，即使 1.0 / 3.0 也不会精确计算 1/3，而是将其四舍五入为二进制近似值。更直接相关的是，Math.random() 的典型实现拥有 64 或 128 位的内部状态，这意味着它甚至没有 21 位！或35！不同的内部状态，这意味着 no 使用 Math.random() 对 21 或 35 或更多元素的数组进行洗牌的算法可以 可能 产生每个排列具有非零概率。所以我想一些偏见是不可避免的！
即使您使用的 sort 实现提供了您认为 足够好的结果，也没有理由这样做，因为 =27=] 编码简单 并且 比任何基于比较的排序算法都快。
But I made a simple script to create an empirical probability distribution of the index that the last element of the array ends after the shuffle: […]
请注意，可能存在更细微的偏差，因此并非所有排列的可能性都相同即使最后一个元素出现在任何位置的可能性相同。即使 sort 实现是固定的，在依赖此改组算法给出无偏结果之前，您还是希望进行更彻底的分析（可能包括查看其源代码）。
原因是比较结果不连贯，正如 ruakh 所详述的，这可能会使某些排序算法产生偏差。
正确的解决方案是将随机键与元素相关联并根据该键进行排序。但这需要 O(n) 额外的 space.
在 this thread 中，我们看到了这个简单而漂亮的随机排列数组的算法：
function shuffle<T>(array: T[]): T[] {
return array.sort(() => Math.random() - 0.5);
}
而且我们可以看到评论说这个算法有偏见。但是我做了一个简单的脚本来创建数组的最后一个元素在洗牌后结束的索引的经验概率分布：
function shuffle(array) {
return array.sort(() => Math.random() - 0.5);
}
function generateDistribution(iterations = 10_000, arrayLength = 10) {
const testArray = Array(arrayLength - 1).fill("test");
const testTarget = "target";
testArray.push(testTarget);
const results = {};
for (let index = 0; index < iterations; index++) {
countTargetPosition();
}
return generateResult();
function countTargetPosition() {
const shuffled = shuffle(testArray);
shuffled.forEach((value, index) => {
if (value === testTarget) {
results[index] = results[index] + 1 || 1;
}
});
}
function generateResult() {
return Object.entries(results).map(([index, count]) => {
return {
[index]: count / iterations,
};
});
}
}
const result = generateDistribution()
document.write(`<h1>Result</h1>`)
document.write(JSON.stringify(result))
我们期望无偏算法具有均匀分布，结果非常接近，即使对于具有 100 个元素的数组也是如此。为什么这个算法会有偏差？
JavaScript 没有为 sort 指定特定的算法，并且根据所使用的特定排序算法，这种改组算法可能会给出非常有偏见的结果。下面，我描述了一些简单的、众所周知的排序算法，它们给出了非常有偏见的结果；我证明了 Firefox 和 Chrome 都对长度为 4 的数组给出了非常有偏见的结果；我给出了为什么 any 排序算法会给出有偏差的结果的一般性论证（尽管不一定像这些明确的例子那样 as 有偏差）。
Example #1 — selection sort. 在选择排序中，我们首先找到最小的元素并将其放在索引 0 处，然后找到第二小的元素并且将其放在索引 1 处，依此类推。需要注意的重要一点是，使用比较函数 () => Math.random() - 0.5，比较的每个参数都有相同的机会被视为“更少”。因此，如果您通过遍历数组并将每个元素与先前最少的元素进行比较来找到最少的元素，那么您有 50% 的机会认为最后一个元素是最少的，有 25% 的机会您会认为倒数第二个元素最少，有 12.5% 的机会认为倒数第三个元素最少，等等，因此给出了哪个元素先出现的偏向分布。
示例 2 — insertion sort. 在插入排序中，我们通过依次获取每个元素并将其插入到数组中来构建数组的“已排序”部分排序部分中的正确位置（将所有更大的元素移动一个以为它腾出空间）。这意味着最后一个元素有 50% 的机会被认为是最少的，有 25% 的机会被认为是第二少的，有 12.5% 的机会被认为是第三少的，等等。
示例 #3 和 #4 — 无论 Firefox 和 Chrome 用于四元素数组。
现在，实际上，我不希望 sort 的任何实现完全使用 选择排序或插入排序，因为还有其他算法比对大输入有效。但是复杂的现代排序算法，例如 Timsort，结合了多种不同的排序算法，根据输入的大小和特征（或部分输入，因为它们可以以复杂的方式组合这些算法）在它们之间进行自适应选择).因此，作为实验，我在数组 [1, 2, 3, 4] 上尝试了这种随机播放算法——一个足够短的数组，似乎 sort 实现可能只对整个数组使用插入排序。
这是我使用的代码：
const counts = {};
for (let i = 0; i < 1_000_000; ++i) {
const permutation = [1, 2, 3, 4].sort(() => Math.random() - 0.5).join('');
counts[permutation] = (counts[permutation]||0) + 1;
}
const result = [];
for (let permutation in counts) {
result.push(permutation + ': ' + counts[permutation]);
}
result.join('\n')
我在 Firefox 和 Chrome 中都试过了。
在 Firefox 中，我得到了这样的结果：
1234: 125747
1243: 62365
1324: 62299
1342: 31003
1423: 31320
1432: 15635
2134: 125380
2143: 62216
2314: 62615
2341: 31255
2413: 31509
2431: 15608
3124: 62377
3142: 31166
3214: 62194
3241: 31293
3412: 15631
3421: 15782
4123: 31056
4132: 15672
4213: 31231
4231: 15319
4312: 15727
4321: 15600
这与我对插入排序的期望不符，因此它一定做了一些不同的事情，但无论如何，它显示出非常明显的偏见。一些排列在 1/64 的时间内发生（一百万次中有 15,625 次，plus/minus 随机噪声），一些在 1/32 的时间内发生（31,250），一些在 1/16 的时间内发生（62,500），有些发生在 1/8 的时间 (125,000)；所以一些排列是其他排列的八倍。
在Chrome中，我得到了这样的结果：
1234: 187029
1243: 62380
1324: 15409
1342: 15679
1423: 62476
1432: 15368
2134: 31280
2143: 31291
2314: 15683
2341: 15482
2413: 31482
2431: 15732
3124: 15786
3142: 15692
3214: 47186
3241: 47092
3412: 15509
3421: 46600
4123: 62825
4132: 15595
4213: 31091
4231: 15763
4312: 15624
4321: 171946
也不符合我对插入排序的期望，并且比 Firefox 中的分布更复杂一点（我想我看到了大约 3/16 (187,500) 和 3/64ths (46,875)？），但实际上偏差更大，最常见和最不常见的排列之间有十二倍的差异。
示例 #5 — 任意 确定性排序算法。 我在上面给出了各种极端偏差的示例；但实际上，any 排序算法预计会产生 some 偏差，因为如果算法做最坏情况 k[=在长度为 n 的数组上进行 97=] 次比较，每次比较都有 50–50 次拆分，则任何给定排列的概率必须是 1 的倍数/2k，而无偏洗牌器必须给每个排列概率1/n!，不会是1[的倍数=110=]/2k 如果 n ≥ 3（因为 n! 将是 3 的倍数）。
也就是说，我应该承认这些偏差可能小到无关紧要；毕竟，即使 1.0 / 3.0 也不会精确计算 1/3，而是将其四舍五入为二进制近似值。更直接相关的是，Math.random() 的典型实现拥有 64 或 128 位的内部状态，这意味着它甚至没有 21 位！或35！不同的内部状态，这意味着 no 使用 Math.random() 对 21 或 35 或更多元素的数组进行洗牌的算法可以 可能 产生每个排列具有非零概率。所以我想一些偏见是不可避免的！
即使您使用的 sort 实现提供了您认为 足够好的结果，也没有理由这样做，因为 =27=] 编码简单 并且 比任何基于比较的排序算法都快。
But I made a simple script to create an empirical probability distribution of the index that the last element of the array ends after the shuffle: […]
请注意，可能存在更细微的偏差，因此并非所有排列的可能性都相同即使最后一个元素出现在任何位置的可能性相同。即使 sort 实现是固定的，在依赖此改组算法给出无偏结果之前，您还是希望进行更彻底的分析（可能包括查看其源代码）。
原因是比较结果不连贯，正如 ruakh 所详述的，这可能会使某些排序算法产生偏差。
正确的解决方案是将随机键与元素相关联并根据该键进行排序。但这需要 O(n) 额外的 space.