写代码首先应该先关注其正确性,如果正确性都保证不了,会造成业务逻辑失败,上线后会引起客户投诉。这一说法听起来有些滑稽,作为前端开发工程师怎么会提交错误的代码上线呢?但在实际开发中,我们可能会写出错误的代码而不自知。比如:洗牌算法的陷阱。
实现洗牌功能,我们很自然想到使用 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);
}
复制代码
上述代码看似可以实现功能,但实际上有很大问题,这种方式洗牌不够随机,是不公平的。我们可以写个程序,执行 shuffle函数
10000次,然后将每一位数字相加求和。
const result = Array(10).fill(0);
for(let i = 0; i < 10000; i++) {
const testItems = [...cards];
shuffle(testItems);
testItems.forEach((item, idx) => result[idx] += item);
}
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;
}
// 验证随机性
const result = Array(10).fill(0);
for(let i = 0; i < 10000; i++) {
const c = shuffle(cards);
for(let j = 0; j < 10; j++) {
result[j] += c[j];
}
}
console.log(shuffle(cards));
console.log(result);
复制代码
多人协作开发,代码编程风格就会变得尤为重要。很多开发因为写不写分号、缩进不统一、花括号写在行尾还是换行等打架。其实没有那种风格是好的或是不好的,只要共同开发项目的开发者约定统一好规范就行。eslint是统一项目规范很好的工具。 我们来看个npm包left-pad,因为代码风格等槽点导致作者下线npm包,然后引发一系列事件。
left-pad作为npm包,实现了左边字符补齐功能,当时主要有以下几个槽点:
我们来认真审视下这段代码,其实可以理解作者这样实现的用意。这个依赖包在2016年发布的,当时es module还没那么成熟,tree shaking摇树去除未使用的代码也还没有那么强大,npm粒度拆细点是可以理解的。对于代码风格,其实也还好,虽然没有注释,但代码语义化挺好,代码即注释。代码质量和执行效率确实有提升的空间,当需要大量补齐字符串,通过循环遍历给 str
字符前补齐空字符串的方式时间复杂度是O(n),其实可以改进成使用es6的 repeat
方法补齐,其时间复杂度是O(logn)。
我们先来看下 repeat
源码实现:
if (!String.prototype.repeat) {
String.prototype.repeat = function(count) {
'use strict';
if (this == null) {
throw new TypeError('can\'t convert ' + this + ' to object');
}
var str = '' + this;
count = +count;
if (count != count) {
count = 0;
}
if (count < 0) {
throw new RangeError('repeat count must be non-negative');
}
if (count == Infinity) {
throw new RangeError('repeat count must be less than infinity');
}
count = Math.floor(count);
if (str.length == 0 || count == 0) {
return '';
}
// 确保 count 是一个 31 位的整数。这样我们就可以使用如下优化的算法。
// 当前(2014年8月),绝大多数浏览器都不能支持 1 << 28 长的字符串,所以:
if (str.length * count >= 1 << 28) {
throw new RangeError('repeat count must not overflow maximum string size');
}
var rpt = '';
for (;;) {
if ((count & 1) == 1) {
rpt += str;
}
count >>>= 1;
if (count == 0) {
break;
}
str += str;
}
return rpt;
}
}
复制代码
上述 repeat
源码实现,主要是使用了快速幂算法,本质是进行了二进制位运算,执行效率要相对高些。
我们在写代码时,保证正确性后,可以尽可能考虑高效率的实现方案,但需要结合应用场景去考虑是否需要高效率的编码。就像上述 left-pad
案例,字符串前面一半不需要拼接太多的空串,用 while
循环遍历完全够用,代码的可读性还高;用 repeat
反而可读性较低,不容易理解。
我们再来看个判断是否是4的幂的案例,来理解下高效率方案需要结合使用场景的说法。
判断一个数是否是4的幂,正向思维,我们会去对这个数除4,再取余,若有余数则该数不是4的幂。具体实现代码如下:
function isPowerOfFour(num){
num = parseInt(num);
while(num > 1){
if(num % 4) return false;
num /= 4;
}
return true;
}
复制代码
如果判断的数很大,使用上述方法效率并不太高,我们可以改进下代码,使用位运算右移2位替代除于4,具体代码如下:
function isPowerOfFour(num){
num = parseInt(num);
while(num > 1) {
if(num & 0b11) return false;
num >>>= 2;
}
return true;
}
复制代码
上述代码时间复杂度是O(logn),其实还可以再继续优化,让时间复杂度为常数O(1),具体代码如下:
function isPowerOfFour(num){
num = parseInt(num);
return num > 0 &&
(num & (num - 1)) === 0 &&
(num & 0xAAAAAAAA) === 0;
}
复制代码
判断的数字 num
如果是4的幂,转换为二进制,我们观察到只有首位是1,并且后面跟的是偶数个0,上述代码 num & (num - 1) === 0
就是用来判断首位是1,后面跟的都是0;num & 0xAAAAAAAA
则是用来判断跟着的0是否是偶数。
version3版本的代码执行效率较高,代码风格很简洁,适用于大数判断是否是4的幂。但如果只是较小的数字判断,则不需要太费心思去考虑高效算法。
如果判断的数字较小,我们可以利用刚转换成二进制数的特征和js的正则匹配来实现,具体代码如下:
function isPowerOfFour(num){
num = parseInt(num).toString(2);
return /^1(?:00)*$/.test(num);
}
复制代码
我们要真正写好JS代码,首先需要关注代码的正确性,保证程序在线上正常运行不出bug。开发团队规模较大的,还应该要约定好代码风格,团队协作开发也方便维护。然后就是对大规模数据计算等,还应该关注代码的效率。(考虑效率的同时,一定要结合具体使用场景,数据量规模大的尽量使用高效算法;数据量小且使用高效算法会造成代码量增多或是可读性下降的,我们就需要去权衡,看到底有没有必要使用高效算法)
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。