【青训营】写好JS——保证正确

2022-06-19 98

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【青训营】写好JS——保证正确

在实际项目当中我们经常会出现以下问题：

代码可以跑通，但是业务上总出bug
业务上没有异常，但是代码执行的过程中总是出现异常
代码没问题，测试也没问题，但不能保证正确性，或者说保证公平

一个例子：洗牌

如果让你实现一个洗牌算法，你会怎么实现？

Math.random()

如果使用Math.random()我会这样实现：

const cards = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
function shuffle(cards) {
  return [...cards].sort(() => 
    Math.random() > 0.5 ? -1 : 1
  )
}
console.log(shuffle(cards))
复制代码

写完多运行几次：

可以看出确实是洗牌了，但是这样随机出来的就公平吗？我们测试一下。

测试

增大测试次数为一百万次，然后记录每个位置出现的数字之和，如果公平的话，这个结果应该都很接近。

const result = Array(10).fill(0);
for(let i = 0; i < 1000000; i++) {
  const c = shuffle(cards);
  for(let j = 0; j < 10; j++) {
    result[j] += c[j];
  }
}
console.log(result);
复制代码

测试结果如图：

可以看到每个位置的数字之和差距极大，并没有出现接近的情况，所以这个算法确实是一个不公平的算法。

改进

之前的算法之所以出现问题，是因为sort()导致交换的位置不够随机。

我们可以使用一个经典算法进行改进（如果学过概率论应该很熟悉，就是摸球拿了不放回去）：

每次随机抽取一张放到最后
剩下的重复第一步即可

而且这个算法可以通过数学归纳法证明每个位置概率都是相等的，写成代码就是这样的：

const cards = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
function shuffle(cards) {
  const c = [...cards];
  for (let i = c.length; i > 0; i--) {
    const pIdx = Math.floor(Math.random() * i);
    [c[pIdx], c[i - 1]] = [c[i - 1], c[pIdx]];
  }
  return c;
}
console.log(shuffle(cards));
复制代码