🥧 一次意外的 Bug 竟然是因为它 ？！Array.sort 使用避坑
!本篇文章过于久远，其中观点和内容可能已经不准确，请见谅!~
当你想要排序的时候，肯定会需要用到 sort 方案，但是请切忌排序结果没问题，但是过程是一个黑盒。
需求是随机获得 0-16 的数字组合，用处是来打乱一副牌，但是需要保证两人相同的随机过程。所以做了一个种子随机数，两个人实现同样的打乱过程，初步想法。
于是：
// 得到一个种子随机数（只要随机，不需要均匀分布，所以直接 sin）const seedrandom = (seed: number): () => number => {let order = 0;return () => Math.abs(Math.sin(seed + order++))}// 生成一个 0-16 的随机序列，只要指定 seed，无论什么时候得到的都是这个结果const getRandom = seedrandom(10086);(new Array(16).fill(0).map((v, i) => i)).sort((a, b) => getRandom() > 0.5 ? 1 : -1)// -> [0, 1, 4, 2, 5, 7, 14, 9, 8, 11, 12, 13, 15, 10, 6, 3]
上面的程序在浏览器里面运行没问题，重复 n 次还是这个结果。
结果在测试的时候出现了问题，两个人的结果不同。排查了数据同步问题等，发现问题出在这个随机序列的生成上。怎么回事，相同的代码啊？？
详细询问了用户环境，出问题的浏览器版本比较老，看了下是 chrome 62 的内核，自己跑一下：
const getRandom = seedrandom(10086);(new Array(16).fill(0).map((v, i) => i)).sort((a, b) => getRandom() > 0.5 ? 1 : -1)// -> [2, 11, 13, 7, 8, 9, 15, 1, 10, 4, 12, 3, 14, 5, 6, 0]
复现了问题，同时也能够在 chrome vs safari，或者 chrome 80 vs chrome 62，不同的浏览器上看到这个问题的出现，所以这个一定是浏览器引擎的问题。
找到问题的过程很简单，这里分析下：
// seedrandom 没问题const seedrandom = (seed: number): () => number => {let order = 0;return () => Math.abs(Math.sin(seed + order++))}const getRandom = seedrandom(10086);const orderedList = (new Array(16).fill(0).map((v, i) => i))// [ 0, 1, 2, 3,..., 15 ]const compareFunc = (a, b) => getRandom() > 0.5 ? 1 : -1// --- 以上都没问题，运行都相同// 经过这个函数调用输出就不一样了orderedList.sort(compareFunc)
之前有听说过排序算法在浏览器内部不同版本的不同实现，今天是着实遇到了。
具体来说，chrom v80 的 sort 和 chrom v62 的 sort 不同，导致调用 getRandom 的顺序不同，最后产生不同的结果：
// <-- v80([1,2,3,4]).sort((a, b) => {console.log(a, b)return a - b})// --> 输出2 13 24 3// <-- v62([1,2,3,4]).sort((a, b) => {console.log(a, b)return a - b})// --> 输出1 22 33 4
在知道这个问题之后，这个随机洗牌这么生成算法就是有问题的了，sort 本身是一个排序函数，实际引擎黑盒执行的时候，调用比较函数是不固定的，排序是从头到尾还是二分的顺序有不同的实现，不能作为可依赖的算法一部分。
// 最终洗牌算法变成了这样，不使用排序，而是直接取值，不依赖浏览器内部export const generateRandomArray = (seed: number, length: number) => {let orderedList = new Array(length).fill(0).map((v, i) => i)let output: number[] = []let getRandom = seedrandom(seed)for (let i = 0; i < length; i++) {const pick = Math.floor(getRandom() * orderedList.length)output.push(orderedList[pick])orderedList.splice(pick, 1)}return output}
先看下 MDN 文档：
里面就明确说这个排序的实现并不是每个浏览器都相同。
而我们看源码：
V8_6.2 内置的 js 方法实现：https://github.com/v8/v8/blob/6.2-lkgr/src/js/array.js#L1005
上面明确说了小于等于 10 的数组用插入排序，不然使用快速排序：
快排里面小于 10 会调用插入排序：
Stack Overflow 有指向文章 官方博客 ，明确说了:
Array.prototype.sort was among the last builtins implemented in self-hosted JavaScript in V8. Porting it offered us the opportunity to experiment with different algorithms and implementation strategies and finally make it stable in V8 v7.0 / Chrome 70.
V8 7.0 将排序算法改成了稳定排序。
在我们测试的 v8 8.0 sort 中：
具体就不分析了，tq 语言也没有高亮，反正就是算法的实现变更了：
最后就是这个排序算法的实现历史，不能依靠排序算法的过程黑盒来参与业务内容。
2022.8
论：如何拯救一个濒临崩溃的实习生
最近用户上报来了一个新的页面游戏的 Bug，是实习生最近提交的，测试的时候可能不是很认真，导致 Bug 流到了线上，先下线把 Bug 指给了实习生。
描述下问题，房主会在客户端生成一个游戏地图，包含随机的雷点，用户扫雷得分。出问题的用户生成的地图会有很奇怪的布局，就是那些雷大部分都分布在地图最底部两层，有随机性，但是非常大概率会集中在那两层，很明显是个 Bug。
问题的关键是：他盯着自己的代码，包括身边的同事帮他 Review 代码都没有发现逻辑上有什么大的问题，总不能说出问题的用户真的随机到了那个不随机的地图吧。
实习生做的游戏本身是没问题的，不然测试也不可能通过，所以他自己接着测了很多遍，没复现出问题，又问询了出问题的用户反馈，发现出问题的是 IOS 用户，借来了 Iphone 测试机测了下发现出现了问题。
很神奇的测出了结果，就是地图生成结果出现了问题。
原话：“生成80个坑位的每个号牌，然后把这些号牌打乱，拿出前25个号牌，生成实际地图的时候在对应位置上放上地雷。”，其实算法本身的描述没问题，直接给 80 个坑位前25个位置放雷后再打乱也是同样的效果，号牌的逻辑不影响核心算法。
原话是没问题的，实现其实说起来也问题不大，代码虽然很奇怪但是看起来也不是很容易出错，实习生没见过这么玄乎的事：
// 整理后的核心代码片段new Array(80).fill(0) // 生成坑位.map((_, i) => i) // 填号牌.sort(() => .5 - Math.random()) // “打乱排列”.slice(0, 25) // 抽取前 25 个
就是结果的这 25 个数字，在 Safari 浏览器中几乎每次生成都会包含 60-80 之间密集的数字分布。
实习生“排除”了自己的问题后，想确认下是不是这些内置函数的问题，于是一起讨论了下。
先说最终的结论：
不可预测 !== 均匀分布 、随机 !== 均匀分布 、随机 !== 不可预测
所以：这个洗牌算法是不对的，不是 random 的随机不够，而是 sort 的比较不充分。
从性能的角度来说，面对的是确定结果的比较函数，排序算法本身追求的也是元素比较和排列的次数越少越好，因此两两比较一定会严重不充分，排序的复杂度越低，那么比较的占比就越少，导致了元素的分布不均匀。
所以使用 random 作为比较结果能够让 sort 变得随机，但是分布问题还是依赖于比较算法的实现过程黑盒。
相关的 sort 函数，在不同的浏览器内核中有不同的实现，最核心的还是两两比较，其实仔细想一下也能够明白确定大小之后的排列移动过程肯定不会频繁发生。
其中的核心逻辑：
numberList.sort(() => .5 - Math.random())
就这么跑一遍，实际上是得不出来真的随机分布的，尤其是 Safari 浏览器上。可以测试下面这段代码的多次运行结果，或者收集多次排序后的分布规律，会显示出过程中比较大的“套路”性：
new Array(80).fill(0).map((a, b) => b).sort((a, b) => {console.log(a, b)return .5 - Math.random()})
最简单低成本的：多跑几次 sort，让之前没碰面的元素有更大的概率碰到，来随机交换。
相同的算法，多调用几次 sort，在总元素数不大的前提下，即时不是均匀排布也是会比单次比较充分得多：
// 整理后的核心代码片段new Array(80).fill(0).map((_, i) => i).sort(() => .5 - Math.random()).sort(() => .5 - Math.random()).sort(() => .5 - Math.random()).sort(() => .5 - Math.random()).sort(() => .5 - Math.random()).sort(() => .5 - Math.random()).sort(() => .5 - Math.random()).slice(0, 25)
让“位置”随机，而不是“比较”随机。
// 找到剩下的空插槽，随机一个位置放入var target = new Array(80).fill(0)target.forEach((_, ind) => {const slots = target.map((v, i) => v == 0 ? i : null).filter(v => v !== null)const pos = slots[Math.floor(Math.random()*slots.length)]target[pos] = ind})target.slice(0, 25)
感谢您的阅读，本文由 Ubug 版权所有。如若转载，请注明出处：Ubug（https://ubug.io/blog/random-and-sort）
