关键词:
如何写好JavaScript是每一个前端工程师一直以来在思考的问题,月影老师告诉我们一些写好JavaScript的原则,同时也教了一些我们如何写好JavaScript的技巧,今天来继续跟着月影老师学JavaScript吧~~
起步
我们在编写代码的时候,最重要的是要保证我们的代码的正确性,然而,在有些情况下,代码可以正常运行,看上去也挺对的,但实际上代码可能不是那么正确~
我们来看一个例子
洗牌算法
让你实现一个洗牌算法,你会怎么实现,很快就能想到我们可以直接对数组进行随机排序,就是洗牌了,代码如下
function shuffle(cards)
return [...cards].sort(() => (Math.random() > 0.5 ? -1 : 1));
const cards = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(shuffle(cards)); // [3, 1, 5, 4, 8, 7, 2, 6, 9, 0]
多运行几次看上去效果不错,确实打乱了顺序
这个算法真的正确吗?或者说这个算法真的公平吗?
验证正确性
我们来验证这个洗牌算法的正确性,如何验证呢?
我们将这个洗牌程序重复一百万次,result数组用来记录每个位置出现过的数字之和,如果这是一个公平的算法的话,result数组中的数字应该都很相近。
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);
得到的结果是
[3863812, 3862770, 4544657, 4648808, 4669379, 4364000, 4362095, 4722847, 4852688, 5108944]
可以看出这个结果是呈现递增的,而且第一个和最后一个位置的所有数字之和相差还比较大,也就是说,越大的数字出现在数组后面的概率要大一些。每个元素被安排在每个位置的概率是不同的,这是一个不公平的算法。
如何解决这个问题呢?
解决方案一:多洗几次
洗两次
const result = Array(10).fill(0);
for (let i = 0; i < 1000000; i++)
const c = shuffle(shuffle(cards));
for (let j = 0; j < 10; j++)
result[j] += c[j];
console.log(result);
[4431933, 4414334, 4501168, 4514001, 4527342, 4493793, 4496849, 4537253, 4540943, 4542384]
洗三次
const result = Array(10).fill(0);
for (let i = 0; i < 1000000; i++)
const c = shuffle(shuffle(shuffle(cards)));
for (let j = 0; j < 10; j++)
result[j] += c[j];
console.log(result);
[4487963, 4491386, 4495428, 4499063, 4494726, 4505270, 4498303, 4510195, 4508869, 4508797]
可以看出,多洗几次之后,result数组中的数字基本相当,也就是我们的算法相对公平了!
解决方案二: 随机采样
重复洗牌总是没有在算法层面解决问题,我们希望通过修改洗牌算法来从根本上解决问题
之前的算法之所以存在问题,是因为我们使用了sort方法,他在两两进行交换的时候,都是就近交换的,所以导致交换的位置不够随机
我们采用随机采样的方法来进行洗牌
- 我们从数组中随机选一个数,把他当前数组最后一个位置的数进行交换
- 去除刚刚交换的末尾的数组进行步骤1的操作
- 直到所有数字都被交换
算法实现
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;
相当于组合数学中的不放回摸球模型,假设有n个球,通过数学归纳法很容易证明这个算法对每个一球取到的概率都是1/n
用上面的验证方法验证此算法
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);
得到的结果
[4498337, 4502249, 4502001, 4498385, 4504714, 4500172, 4498057, 4502210, 4498232, 4495643]
可以看到,数字都很相近,很均匀,所以这样的算法就是公平的,是正确的
应用
抽奖
比如我们要抽奖,可以直接取一个任意位置上的元素就行了
Math.floor(Math.random() * length)
但是我们的抽奖是一个过程,比如抽出一等奖,二等奖,三等奖,幸运奖之类的,就需要封装一下,采用我们上面的洗牌算法
将函数改成生成器,将return
改成yield
,就能够实现部分洗牌,或者用作抽奖
function* shuffle(items)
items = [...items];
for (let i = items.length; i > 0; i--)
const idx = Math.floor(Math.random() * i);
[items[idx], items[i - 1]] = [items[i - 1], items[idx]];
yield items[i - 1];
可以全部展示出来
let items = [1, 2, 3, 4, 5, 6, 7, 8, 9];
items = shuffle(items);
console.log(...items); // 7 1 2 8 5 3 9 4 6
也可以只选取部分,实现部分洗牌,或者说抽奖的功能
100个号随机抽取5个
let items = [...new Array(100).keys()];
let n = 0;
// 100个号随机抽取5个
for (let item of shuffle(items))
console.log(item);
if (n++ >= 5) break;
// 24 62 60 16 42 21
分红包
在APP中的抢红包功能中,内部进行随机的分红包的算法
为了不出现,一次随机分之后,一个红包太大,导致剩下的红包不够分的情况,可以采用下面这种分法,也就是每次划分之后,都选取存在的最大的那一个红包继续进行划分,这样就能保证红包肯定能被分够
function generate(amount, count)
let ret = [amount];
while(count > 1)
//挑选出最大一块进行切分
let cake = Math.max(...ret),
idx = ret.indexOf(cake),
part = 1 + Math.floor((cake / 2) * Math.random()),
rest = cake - part;
ret.splice(idx, 1, part, rest);
count--;
return ret;
上面这种分法,会导致每次分的红包都很均匀
有时候,为了增加抢红包的趣味性,我们不希望我们红包分的那么平均
比如100元分给10个人,相当于在一个(0,100.00)的数轴上进行切分,随机切九刀在不同的位置,
所以可以转换成我们的洗牌程序,在0到100.00中间的 10000个位置中,随机抽取九个位置,将红包分成了十份,这样红包就不会被那么均匀的分配了
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]];
yield c[i - 1];
function generate(amount, count)
if(count <= 1) return [amount];
const cards = Array(amount - 1).fill(0).map((_, i) => i + 1);
const pick = shuffle(cards);
const result = [];
for(let i = 0; i < count; i++)
result.push(pick.next().value);
result.sort((a, b) => a - b);
for(let i = count - 1; i > 0; i--)
result[i] = result[i] - result[i - 1];
return result;
总结
我们写好程序,一定要确保它的正确性!
使用sort方法来随机洗牌,可能会导致算法不公平
更多相关博文
【青训营】月影老师告诉我写好JavaScript的三大原则——各司其责
【青训营】月影老师告诉我写好JavaScript的三大原则——组件封装
青训营月影老师告诉我写好javascript的四大技巧——风格优先(代码片段)
如何写好JavaScript肯定是每一个前端工程师一直以来要思考的问题,月影老师告诉我们一些写好JavaScript的原则,同时也教了一些我们如何写好JavaScript的技巧,今天来继续跟着月影老师学JavaScript吧~~我们在写代码的时候... 查看详情
青训营月影老师告诉我写好javascript的四大技巧——风格优先(代码片段)
如何写好JavaScript肯定是每一个前端工程师一直以来要思考的问题,月影老师告诉我们一些写好JavaScript的原则,同时也教了一些我们如何写好JavaScript的技巧,今天来继续跟着月影老师学JavaScript吧~~我们在写代码的时候... 查看详情
青训营月影老师告诉我写好javascript的四大技巧——妙用特性(代码片段)
...版一些小技巧转进制交换元素总结更多相关博文如何写好JavaScript是每一个前端工程师一直以来在思考的问题,月影老师告诉我们一些写好JavaScr 查看详情
青训营月影老师告诉我写好javascript原则与技巧大总结
文章目录各司其责保证正确风格优先封装函数过程抽象组件封装妙用特性相关博文YK菌花了十几天的时间总结了月影老师三个小时的课程,对大部分案例都进行了自己的复现,并且进行了一些思考,今天来对之前博文&... 查看详情
青训营月影老师告诉我写好javascript的三大原则之——过程抽象(代码片段)
文章目录0.起步1.案例引入限制操作Once一次性执行函数2.高阶函数定义拓展HOF0等价范式常见高阶函数throttle函数debounce函数consumer函数iterative函数拦截函数3.纯函数定义纯函数的优势可测试性拓展4.编程范式分类Toggle案例命令式声明... 查看详情
青训营月影老师告诉我写好javascript的三大原则之——各司其责(代码片段)
...习了挺多语言的(C/java/matlab/pathon/),最后终于确定了JavaScript是我的本命语言,刚开始学的时候觉得JavaScript上手真的很快,很简单,但是随着自己学习的深入,发现JavaScript真的特别有意思,原型、闭包等特... 查看详情
青训营月影老师告诉我写好javascript的三大原则之——组件封装(代码片段)
文章目录1.起步2.轮播图案例版本一:API无交互版结构:HTML表现:CSS行为:JS——API版本二控制流交互版结构HTML表现:CSS行为:JS——控制流3.总结:基本方法4.重构重构一:解耦JS——插件化重构二&... 查看详情
青训营月影老师告诉我写好javascript原则与技巧大总结
...了,这是第八篇!!!我们一共讲了写好JavaScript的七个原则或技巧,它们分别是:各司其责2.组件封装3.过程抽象4.风格优先5.保证正确6.封装函数7.妙用特性各司其责首先要做到各司其责,如果遇到纯UI... 查看详情
青训营html基础-语义化标签-浏览器渲染过程-笔记及拓展(代码片段)
...)博主还是很久之前学习的,这次趁着字节跳动青训营的活动,就再学习一遍HTML。一小时的课程,巩固了之前的一些知识,也学到了很多新知识。我把这次课程的内容与我这一年来学习前端的经验相结合,... 查看详情
go语言上手|青训营笔记(代码片段)
这是我参与「第三届青训营-后端场」笔记创作活动的的第一篇笔记。文章目录语法速览基础语法第一:类型第二:内置库部分json库的使用时间库的使用字符串和数字互转os相关信息实战项目猜谜游戏(pass,过于... 查看详情
客户端容器|青训营笔记(代码片段)
...架构:所有模块运行在同一个进程里,包含网络、插件、JavaScript运行环境等多进程架构(现代浏览器的常用架构):主进程、网络进程、渲染进程、GPU进程、插件进程浏览器架构浏览器架构演进单进程架构:所有模块运行在同一个... 查看详情
字节跳动青训营笔试题解(代码片段)
...圈题目思路代码四、简答题题目思路前言第五届字节跳动青训营-后端专场笔试题解,简单做了一下,选择题和简答题不知道是否正确,编程题是通过了的,有问题欢迎评论,我会及时改正的~一、单选题选AQUIC&... 查看详情
字节跳动青训营笔试题解(代码片段)
...圈题目思路代码四、简答题题目思路前言第五届字节跳动青训营-后端专场笔试题解,简单做了一下,选择题和简答题不知道是否正确,编程题是通过了的,有问题欢迎评论,我会及时改正的~一、单选题选AQUIC&... 查看详情
青训营pro自定义脚手架从1到∞-自动化思维搭建koa脚手架(代码片段)
...6.处理路径问题五、发布本文相关代码:youth_camp_ykjun:青训营&开课吧实战课程代码仓库-Gitee.com一、前言今天来复习&总结青训营实训营第二天的内容,在上次课程中我们从0到1创建了一个vue的脚手架,今天我们跟... 查看详情
字节跳动青训营每日一练编程题
1:实现一个36进制的加法0-9a-z。#include<bits/stdc++.h>typedeflonglongll;constllN=2e5+10;usingnamespacestd;ints[N];intmain()int_;stringa,b;while(cin>>a>>b)stringans;intpos 查看详情
青训营node.js基础-异步编程四种解决方案(代码片段)
文章目录异步编程概述异步编程解决方案CallbackPromiseCallback转为PromiseawaitEvent参考有异步I/O,必有异步编程!今天来学习Node.js里的异步编程!异步编程概述曾经的单线程模型在同步I/O的影响下,由于I/O调用缓慢ÿ... 查看详情
青训营node.js基础-异步编程四种解决方案(代码片段)
文章目录异步编程概述异步编程解决方案CallbackPromiseCallback转为PromiseawaitEvent参考有异步I/O,必有异步编程!今天来学习Node.js里的异步编程!异步编程概述曾经的单线程模型在同步I/O的影响下,由于I/O调用缓慢ÿ... 查看详情
青训营pro前端框架设计理念-vue3动机-手写实现mini-vue(代码片段)
...2.响应式①reactive②依赖收集3.虚拟DOM4.diffpatch更新diff对比青训营实战班的课程也结束了,今天先来撸一遍周五杨村长带来的mini-vue课程。错过课程的小伙伴一 查看详情