基于Vue+nodejs实现的前后端分离疫情防控系统
作者主页：编程指南针作者简介：阿里云开发者社区特邀作者、Java领域优质创作者、CSDN博客专家 、掘金特邀作者、多年架构师设计经验、腾讯课堂常驻讲师主要内容：Java项目、毕业设计、简历模板、学习资料、面试题库、技术互助本项目主要实现校园/公司/各类组织疫情防控管理，个人健康上报功能，分为三个角色：管理员：主要管理学生、教师、班级、通知信息教师：主要管理学生的健康上报信息，通知信息，请假审批信息学生：主要进行健康上报，请假，通知查看等功能系统通过图形报表的形式来统计相关的信息，界面美观大方，功能全面，是一个难得的前端项目。可以根据需要修改为比如公司疫情防控系统、社区疫情防控系统等等。项目编号：BS-QD-0011.使用vue+element+vchar框架进行前端开发2.使用nodejs+express+mysql+socket进行后台开发3.前后端分离开发4.数据库采用MYSQL+REDIS进行信息的存储编辑编辑下面展示一下系统功能：管理员登陆： admin /111111编辑后台首页：仪表盘编辑学生管理功能编辑可以通过EXCEL表格导入学生和老师编辑老师管理：同样可以通过EXCEL表格导入学生和老师编辑通知管理：编辑班级管理编辑学生登陆系统：znzbs005/111111编辑查看通知编辑每日健康填报编辑请假编辑个人信息管理编辑老师登陆编辑通知管理编辑请假审批：只能审批本班学生编辑个人信息修改编辑在线聊天编辑编辑以上是展示的本系统的部分功能。?核心代码展示如下：const jwtUtil = require('../utils/jwtUtils')
module.exports = class admin_dao extends require('../model/admin_mod') {
/**
* 根据用户类型与查询字段模糊查询
* @param req
* @param resp
* @returns {Promise<void>}
*/
static async getUsersByTypeAndChar(req, resp) {
let query = req.query;
let type = query.type
let inputText = query.inputText
let CharType = query.CharType
let pageNum = query.pageNum
let currPage = query.currPage
let data = await this.getUsersByTypeAndCharMod(type, inputText, CharType, currPage, pageNum)
let total = await this.getUsersByTypeAndCharTotal(type, inputText, CharType)
resp.send({data, total: total[0].count})
}
/**
* 发布公告
* @param req
* @param resp
* @returns {Promise<void>}
*/
static async announce(req, resp) {
let title = req.body.title
let classes = req.body.classes
let results = await this.announceMod(title, classes)
resp.send(results)
}
/**
* 分页获取所有通知与数量
* @param req
* @param resp
* @returns {Promise<void>}
*/
static async getAllNotice(req, resp) {
let pageNum = req.query.pageNum;
let currPage = req.query.currPage;
let data = await this.getAllNoticeMod(pageNum, currPage)
let total = await this.getAllNoticeTotal()
resp.send({data, total: total[0].count})
}
/**
* 取该老师所属班级的全部请假单与数量(分页查询)
* @param req
* @param resp
* @returns {Promise<void>}
*/
static async getLeave(req, resp) {
let verify = await jwtUtil.verifysync(req.query.token, globalKey)
let classArr = verify.classes.split(';')
let data = await this.getLeaveMod(classArr, req.query.currPage, req.query.pageNum)
let total = await this.getLeaveTotal(classArr)
resp.send({data, total: total[0].count})
}
/**
* 获取该用户请假审批与数量(分页
* @param req
* @param resp
* @returns {Promise<void>}
*/
static async getuserLeave(req, resp) {
let verify = await jwtUtil.verifysync(req.query.token, globalKey)
let u_id = verify.id
let data = await this.getuserLeaveMod(u_id, req.query.currPage, req.query.pageNum)
let total = await this.getuserLeaveTotal(u_id)
resp.send({data, total: total[0].count})
}
/**
* 当前请假单审批(修改审批状态)
* @param req
* @param resp
* @returns {Promise<void>}
*/
static async upLeaveState(req, resp) {
let results = await this.upLeaveStateMod(req.query.l_id, req.query.upState)
resp.send(results)
}
/**
*******************增值功能:公告**************************
*/
static async NoticeDetails(req, resp) {
let n_id = req.query.n_id
let users = {}
//1. 获取当前公告已读人的人数
let readNum = await this.getreadNum(n_id)
readNum = readNum[0].count
//2. 获取当前公告已读的人的id数组,再通过id去查询用户数据
let readIdArr = await this.getreadId(n_id)
if (readIdArr.length != 0) users = await this.getreadByidArr(readIdArr)
//3. 获取当前通知的详情信息
let data = await this.NoticeDetailsMod(n_id)
//4. 获取当前公告通知的总人数
let total = await this.NoticeDetailsTotal(data[0].class)
total = total[0].count
//5. 获取已读人的阅读时间与uid
let idAndTime = await this.getreadTime(n_id)
//将阅读时间附加到users中
for (let i = 0; i < idAndTime.length; i++) {
for (let j = 0; j < users.length; j++) {
if (users[i].id == idAndTime[j].u_id)
users[i].readtime = idAndTime[j].readtime
}
}
resp.send({
data,
readNum,
total,
users
})
}
/**
* 当前 公告删除功能(同时清空该公告的被阅读记录)
* @param req
* @param resp
* @returns {Promise<void>}
*/
static async delNotice(req, resp) {
let results=await this.delNoticeMod(req.query.n_id)
results+=await this.delReadMod(req.query.n_id)
resp.send(results)
}
/**
* ************************增值功能:班级添加******************************
*/
static async addClasses(req,resp){
let classAll = await this.getClassMod()
let results= await this.addClassesMod(classAll,req.query.classes)
resp.send(results)
}
static async getClasses(req,resp){
let data=await this.getClassMod();
resp.send(data)
}
static async getClassesSear(req,resp){
let classes=req.query.inputText;
// console.log(req.query.pageNum)
let data =await this.getClassesSearMod(classes,req.query.pageNum,req.query.currPage)
let total=await this.getClassesSearTotal(classes)
resp.send({data,total:total[0].count})
}
}const jwtUtil = require('../utils/jwtUtils')
module.exports = class student_dao extends require('../model/student_mod') {
/**
* f分页获取我的通知与数量
* @param req
* @param resp
* @returns {Promise<void>}
*/
static async getNotice(req, resp) {
let verify = await jwtUtil.verifysync(req.query.token, globalKey)
let u_classes = verify.classes
let pageNum = req.query.pageNum
let currPage = req.query.currPage
let data = await this.getNoticeMod(u_classes, pageNum, currPage)
let total = await this.getNoticeTotal(u_classes)
resp.send({data, total: total[0].count})
}
/**
* 获取的我通知已读列表(供已读未读状态渲染
* @param req
* @param resp
* @returns {Promise<void>}
*/
static async getNoticeRead(req, resp) {
let verify = await jwtUtil.verifysync(req.query.token, globalKey)
let u_id = verify.id
let data = await this.getNoticeReadMod(u_id)
resp.send(data)
}
/**
* 已读转未读
* @param req
* @param resp
* @returns {Promise<void>}
*/
static async goweidu(req, resp) {
let verify = await jwtUtil.verifysync(req.query.token, globalKey)
let u_id = verify.id
let n_id = req.query.n_id
let results = await this.goweiduMod(u_id, n_id)
resp.send(results)
}
/**
* 未读转已读
* @param req
* @param resp
* @returns {Promise<void>}
*/
static async goyidu(req, resp) {
let verify = await jwtUtil.verifysync(req.query.token, globalKey)
let u_id = verify.id
let n_id = req.query.n_id
let results = await this.goyiduMod(u_id, n_id)
resp.send(results)
}
/**
* *************************健康填报表**************************************
*/
/**
* 健康填报表提交
* @param req
* @param resp
* @returns {Promise<void>}
*/
static async sethealth(req, resp) {
let body = req.body
let token = body.token
let temperature = body.temperature
let hot = body.hot
let gohubei = body.gohubei
let hubeiren = body.hubeiren
let fever = body.fever
let leave = body.leave
let hesuan = body.hesuan
let mask = body.mask
let masknum = body.masknum
let kill = body.kill
//解密
let verify = await jwtUtil.verifysync(token, globalKey)
let u_id = verify.id
let data = await this.sethealthMod(u_id, temperature, hot, gohubei, hubeiren, fever, leave, hesuan, mask, masknum, kill)
resp.send(data)
}
/**
* 分页获取当天填报表与总数量
* @param req
* @param resp
* @returns {Promise<void>}
*/
static async gethealthNowDayPage(req, resp) {
let date = new Date();
let Month = ""
if ((date.getMonth() + 1) < 10) Month = "0" + String((date.getMonth() + 1))
else Month = (date.getMonth() + 1) + ""
let newDate = "" + date.getFullYear() + Month + date.getDate()
let lastDate = "" + date.getFullYear() + Month + (date.getDate() + 1)
let currPage = req.query.currPage
let pageNum = req.query.pageNum
let data = await this.gethealthNowDayPageMod(newDate, lastDate, currPage, pageNum)
let total = await this.gethealthNowDayPageTotal(newDate, lastDate)
resp.send({data, total: total[0].count})
}
/**\
* 获取当天某用户报表
* @param req
* @param resp
* @returns {Promise<void>}
*/
static async getHealthNowDayByid(req, resp) {
let verify = await jwtUtil.verifysync(req.query.token, globalKey)
let u_id = verify.id
let newDate = this.getNowAndLastDate().newDate
let lastDate = this.getNowAndLastDate().lastDate
let data = await this.getHealthNowDayByidMod(u_id, newDate, lastDate)
resp.send(data)
}
/**
* 获取当天所有填报表
* @param req
* @param resp
* @returns {Promise<void>}
*/
static async gethealthNowDay(req,resp){
let nowDate=this.getNowAndLastDate().newDate
let lasDate=this.getNowAndLastDate().lastDate
let data= await this.gethealthNowDayMod(nowDate,lasDate)
resp.send(data)
}
/**
* 获取当天所有填报表
* @param req
* @param resp
* @returns {Promise<void>}
*/
static async gethealthNowMonth(req,resp){
let nowDate=this.getNowAndLastDate().nowMonth
let lasDate=this.getNowAndLastDate().lastMonth
let data= await this.gethealthNowMonthMod(nowDate,lasDate)
resp.send(data)
}
/**
* 获取所有填报表
* @param req
* @param resp
* @returns {Promise<void>}
*/
static async getAllHealth(req,resp){
let data= await this.getAllHealthMod()
resp.send(data)
}
/**
* 学生请假表申请
* @param req
* @param resp
* @returns {Promise<void>}
*/
static async setLeave(req,resp){
let body=req.body
let verify=await jwtUtil.verifysync(body.token,globalKey)
let u_id=verify.id
let classes=verify.classes
let reason =body.reason
let leavetype =body.leavetype
let starttime =body.starttime
let endtime =body.endtime
let results=await this.setLeaveMod(u_id,classes,reason,leavetype,starttime,endtime)
resp.send(results)
}
}
如何顺利通过计算机专业毕业答辩
临近毕业，很多同学项目和论文都准备的差不多了，只剩下最后一个环节，那就是决定你能否顺利毕业的毕业答辩。最后很多小伙伴咨询关于答辩的问题，也了解到了大家比较焦虑的心理，毕竟对我们来讲，努力了四年或者三年，最主要的目的还是为了这一纸毕业证，它将是我们走向社会，通向成功的第一把钥匙，今天就来给大家聊聊毕业答辩的一些问题。??????其实如果你前期的准备工作充分，比如你的毕业设计项目自己很熟悉，你的毕业设计论文自己很清楚，那么毕业答辩是水到渠成的事儿，但是我们发现很多同学在得到项目和论文后，几乎是没怎么看过，估计是比较忙吧，或许也可能是胸有成竹，不管怎样，你今天看到了这篇文章，让我们指南针的包哥来给大家聊聊毕业答辩的那些事儿，希望对大家所有帮助。? ? ? 毕业设计答辩的过程对每个人来讲都不会太长，相信你的导师，一般每个人不会超过20分钟，有例外者暂且不表，大部分10分钟左右。所以一般情况下你按10分钟左右去准备怎么比较清楚的阐述你的项目以及导师有可能问到的问题即可。????? 一，如何准备呢？????? 1、项目准备：包哥觉得首先你要对你的项目有一个差不多的了解，怎么着也得自己把程序跑两遍过一下核心功能吧？你总得能说清楚你的系统出于什么的目的，为什么样的客户服务，完成什么样的功能吧？如果不清楚，看看论文，上面一般会有描述。????? 2、论文观看：这个论文其实一般的格式就是将你项目开发的背景、目的、需求、设计、实现、测试、总结几大块全写上了，所以你认真看一遍论文，也会让你对整个软件系统的整体或局部都有一个相对清晰的认知。????? 3、技术查看：这个可能对大部分XDJM来说是最难的，看不懂，束手无措…..能看懂，自梳理清楚当然是最好了，如果实在是基础差，搞不明白，我觉得你可以先查一下看系统用到的相关技术是做什么用的，比如论文可能会有你项目所涉及技术的描述，Springboot框架，SSM框架，Shiro 框架等等，可能还有前端的什么EasyUI,Bootstrap,Vue,Layui等等，还有我们新爱的MYSQL数据库，先有个大概的了解。答辩不是面试，所以一般不会问你具体的技术，但一般会考察你系统的实现。???? 4、核心模块：这是我们准备的重点，你必须要将项目中的二三个你认为是亮点的地方，或者值得一提的地方能说个大概。比如可能你项目中大部分都有这个登陆功能，但它是不是核心功能呢？我觉得值得商榷，因为它基本是每个系统都有的，能有什么亮点？但你说这么一个普通的功能，如果老师问了，你答不上来，尴尬不？所以我觉得你可以看一看，通过个登陆把整个系统的交互流程搞明白了。然后就是准备核心业务模块和系统的核心技术应用。对大部分系统来讲，其实大多的功能还是基本的增删改查，这个你熟悉一个模块即可。但像其它的，比如系统中所拥有的图形报表功能、数据导入导出功能，这些是不是值得一说？我觉得是可以的。当然这要看每个系统的具体情况，比如你的是基于XXX的推荐系统，那就主要准备介绍一下你这个推荐的算法，业务流程的实现；比如你的是基于XXX的大数据分析，那你可能就主要放在你这个大数据是如何分析的业务模块和流程上了。???? 5、答辩PPT：这是一个最终的总结性步骤，你前面的所有的努力，其实都可以汇总到这个PPT上，它是你展示项目和进行答辩的一个思路凝聚，也是你答辩时因为不熟练而忘记时给你救场的救星。一般来讲，一个答辩PPT的制作无法这么几个环节，项目介绍，技术说明，功能实现，主要亮点，项目展示，最后总结。你准备的越充分，胜率也就越大，但是你的导师不可能让你把整个论文都粘贴上去的，所以它就是一个答辩的思路的梳理，你可以把核心的一些东西放上去给自己做提醒。二、如何答辩?? 1、首先人是感情动物，导师会对你有平时的印像分和现场感受分，它是一个综合体，这时候一方面是考验你平时和导师的互动关系，一方面是考验你多年积赞的实力。所以在答辩时我觉得最重要的是要学会控制自己的情绪，言谈举卡给导师和答辩组一个良好的印像，千万不要逞一时之勇，和答辩组老师刚起来了----流泪。? ?2、答辩不是要拿满分，及格就行。所以在答辩时如果有答不上来的，千万不要有心理压力，你想，如果你都答上来了，老师多没面子？哈哈，所以放松。但放松不等于放弃，如果碰到一个自己答不上来的，可以引导老师提问你比较熟悉的功能或知识。比如老师问你在项目中使用到的MVC设计模式，是如果实现的，让你讲讲他的流程，如果你此时答不上来，可以说我在使用MVC的时候也同时使用了三层架构，我来介绍一下三层架构吧。我觉得也是可以的。?? 3、答辩时主要求稳。当然，如果你很优秀，那其实不需要包哥挂念。稳的意思是最好按你前期准备的PPT来按部就班的去介绍和讲解，不要突然心血来潮，去讲解或演示前期没有准备的一些知识点和功能。从小概率事件来讲，如果这样做，几乎都会出问题，从而造成自己的信心一落千仗，对后面的答辩不利。?? 4、最后的总结很重要。可能前面答辩进行的有点糟糕，但最后的总结如果你能好好总结原因，真诚的打动答辩组，让他们觉得你是一个可造之才，还是有挽回的余地的。真的，相信我，有用的。三、常见答辩点1、请说明一下你项目中所说的C/S和B/S架构有什么区别呢？2、请说明一下你项目设计的整体架构什么结构的？3、你系统中用到了什么算法，请说一下？4、你系统中用到的R edis数据库主要是在哪个地方用的，为什么要用它？5、你的系统的安全性是如何保障的？6、你在开发时遇到什么技术难题，是如何解决的？7、请您介绍一下XX模块的基本业务流程，讲解一下相关代码。8、你说说你项目是如何实现前后端分离开发的。9、你的小程序端开发和运行需要什么样的条件？10、你这个商城中的购物车功能是如何进行实现的？11、你这个系统中有没有用到什么设计模式？请说明一下。12、你的这个图形统计报表是如何进行实现的？13、你介绍一下你项目中所用到的各个表以及他们之间的业务关联。14、你能否介绍一下你用的这个SSM框架中三个框架各自的职责是什么？15、你觉得你的这个系统有什么比较新颖的地方？技术或功能点都可以。四，总结? ? ?对于毕业答辩来讲，七分准备，三分讲解，还是要做足准备，其实并不复杂。主要基于项目本身和论文即可参系统有一个熟悉的过程。再掌握一些常见答辩问题，相信各位老铁能都顺利通过答辩。
【贪心思想】兄弟总爱贪小便宜，原来是把贪心算法掌握得如此熟练【经典例题讲解】
??小剧场??你去到一个幼儿园里做活动，一群小朋友围着你转，你发现你的口袋里有一些大小不一的饼干，你想分给孩子们。对每个孩子，都有一个胃口值 ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干，都有一个尺寸 ?。如果 ，我们可以将这个饼干 分配给孩子 ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。（一定要认真将自己代入成这个家长，你会怎样去分？）答案及解析在下题目连接：分发饼干https://leetcode-cn.com/problems/assign-cookies/🍋1.什么是贪心算法？ ? ? ? ?贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。 ? ? ? ?说这么多，用题目来演示学习才是最快的，我将由简到难，一步步带大家做一个够贪的刷题者🍋2.贪心的经典基础例题 ?PS：建议先读完题目通过链接思考后看能否想到如何贪心，没有头绪再看下方的贪心考虑，理解后再自己去尝试用代码实现。🍈1.两个数对之间的最大乘积差（易） ?两个数对 (a, b) 和 (c, d) 之间的 乘积差 定义为 (a * b) - (c * d) 。例如，(5, 6) 和 (2, 7) 之间的乘积差是 (5 * 6) - (2 * 7) = 16 。给你一个整数数组 nums ，选出四个 不同的 下标 w、x、y 和 z ，使数对 (nums[w], nums[x]) 和 (nums[y], nums[z]) 之间的 乘积差 取到 最大值 。返回以这种方式取得的乘积差中的 最大值 。题目连接：两个数对之间的最大乘积差https://leetcode-cn.com/problems/maximum-product-difference-between-two-pairs/ ? ? ? ?代码展示：class Solution {
public int maxProductDifference(int[] nums) {
Arrays.sort(nums);
int n=nums.length;
return nums[n-1]*nums[n-2]-nums[0]*nums[1];//最大的相乘减去最小的相乘
}
} ? ? ? ?🌰贪心考虑：要获得一个最大的差值，那我们肯定想着需要用一个最大的值减去一个最小的值。那如何从获得一个乘积最大和一个乘积最小的值呢？那肯定是最大的数乘第二大的数的和最小的数乘以第二小的数。所以我们直接排序后，用最大的两个数相乘减去最小的两个数相乘就是答案啦。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?🍈2.三角形的最大周长(易）给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。如果不能形成任何面积不为零的三角形，返回 0。题目链接：三角形的最大周长https://leetcode-cn.com/problems/largest-perimeter-triangle/ 代码展示：class Solution {
public int largestPerimeter(int[] nums) {
Arrays.sort(nums); //先排序
int n=nums.length;
for(int i=n-1;i>=2;i--){ //倒叙遍历（从最大的开始判断）
int x=nums[i-1]+nums[i-2]; //判断后两条边是否能满足围成三角形
if(x>nums[i]){
return x+nums[i];
}
}
return 0;
}
} ? ? ? ?🌰贪心考虑：又是一道题目中包含最大字眼的例题。先思考如何让三角形周长最大？那肯定三条边越长越好呀。我们可以直接将三条边捆绑着来看，比如有一个排序好的数组[1,2,2,3,4,7]，你肯定先判断3,4,7能否围成三角形，发现不能，那你觉得7这条边还能用上吗？肯定不能了，因为除了7最长的3和4加起来都构不成三角形，其他更加不可能。所以我再考虑2,3,4三条边，这次发现可以了，所以2,3,4就是能围成最大三角形的三条边。 ?🍈3.数组拆分|（易）给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。返回该 最大总和 。题目链接：数组拆分| https://leetcode-cn.com/problems/array-partition-i/代码展示：class Solution {
public int arrayPairSum(int[] nums) {
Arrays.sort(nums); //同样先将数组从小到大排序
int n=nums.length;
int count=0;
for(int i=0;i<n;i+=2){ //只取偶数位相加即为答案
count+=nums[i];
}
return count;
}
} ? ? ? ?🌰贪心考虑：题目要求将数组两两配对，每一对只取更小的那个数，另外一个将会被浪费掉。假设有个排好序的数组(a1,a2,a3.....an)，a1作为最小的数，那么和它匹配的数，肯定要被浪费掉，那我们肯定希望被浪费的数越小越好，那除了a1最小的就是a2了呀，所以a1和a2匹配。这样同理又从a3开始匹配，a3把a4带走浪费掉，所以最后我们取得的数下标都是从0开始的偶数位，所以将索引为偶数位相加就是最大的值了。 ?🍈4.救生艇（中）第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。返回载到每一个人所需的最小船数。(保证每个人都能被船载)。题目链接：救生艇 https://leetcode-cn.com/problems/boats-to-save-people/?class Solution {
public int numRescueBoats(int[] people, int limit) {
int ans = 0;
Arrays.sort(people);//让人从轻到重排好序站好
int light = 0;
int heavy = people.length - 1;//利用双指针
while (light <= heavy) {
if (people[light] + people[heavy] <= limit) {//判断此时最轻的和最重的能否坐一起
++light; //可以的话左指针右移（说明最轻的跟着最重的一起走了）
}
--heavy; //右指针左移，无论能不能带一个最轻的，这个重的都得走
++ans;
}
return ans;
}
} ? ? ? ?🌰贪心考虑：首先我们要明白，人肯定是全都要带走的，它也不可能有一个人的体重直接超过船的承受重量的，这样的话题目就出错了。为了减少船的次数，我们无非只能希望在带最重的人的同时再带走一个人，带谁呢？那最有可能的当然是场上最轻的人，如果这个最重的人和最轻的人加一起都超重，那这个最重的人自己注定只能自己走了。然后再继续重复判断剩下里面的人最重的能否和最轻的走，直到所有人走完。所以我们可以通过双指针来分别指向场上最轻的和最重的来进行选人。 ?🍈5.分发饼干（小剧场解答） ? ? ? ?🌰贪心考虑：同样是求最值问题，这道理和上一题有异曲同工之妙。我们的目标是为了满足更多的孩子，那当然是优先满足容易吃饱的孩子，所以我们需要将孩子排好序。对于饼干呢？我们当然更想先把尺寸较小的饼干给孩子们吃掉，而不是一上来就把大饼干拿出来，所以我们同样要给饼干也排序。综合两种贪心的思想：我们就想要尽可能用尺寸最小的饼干去喂饱最容易吃饱的孩子。既然如此就会出现两种情况：1.最小的饼干能喂饱最容易吃饱的孩子，这种情况我们是我们希望见到的。2.最小的饼干满足不了最容易吃饱的孩子，那你这块饼干说明就没用了，你连最容易喂饱的都喂不饱，那还有什么用，那只能考虑尺寸更大一定的饼干。综上考虑，我们同样得用双指针，分别指向此时最容易吃饱的孩子和尺寸最小的饼干。 ? ? ? ? ? ? ? ? ? ? ? ?代码展示：class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int n1=g.length;//孩子的个数
int n2=s.length;//饼干的个数
int l=0;//指向最容易吃饱的孩子的指针
int r=0;//指向尺寸最小的饼干的指针
int count=0;
while(l<n1&&r<n2){ //如果孩子喂完了或者饼干吃完都会结束
if(s[r]>=g[l]){ //如果最小的饼干能满足最容易吃饱的孩子
r++; //孩子指针右移
l++; //饼干指针右移
count++;
}else{ //如果满足不了最小的孩子
r++; //舍弃当前饼干，饼干指针右移再次继续判断
}
}
return count;
}
}🍈6. 最少操作使数组递增（易）给你一个整数数组 nums （下标从 0 开始）。每一次操作中，你可以选择数组中一个元素，并将它增加 1 。比方说，如果 nums = [1,2,3] ，你可以选择增加 nums[1] 得到 nums = [1,3,3] 。请你返回使 nums 严格递增 的 最少 操作次数。我们称数组 nums 是 严格递增的 ，当它满足对于所有的 0 <= i < nums.length - 1 都有 nums[i] < nums[i+1] 。一个长度为 1 的数组是严格递增的一种特殊情况。题目链接：最少操作使数组递增https://leetcode-cn.com/problems/minimum-operations-to-make-the-array-increasing/代码展示：class Solution {
public int minOperations(int[] nums) {
int n=nums.length;
if(n==1) return 0;
int count=0; //用于统计操作的次数
for(int i=1;i<n;i++){ //从下标为1的位置开始判断
int x=nums[i-1]-nums[i]; //计算差值
if(x>=0){
count=count+x+1; //加上操作的次数
nums[i]=nums[i-1]+1;
}
}
return count;
}
} ? ? ? ?🌰贪心考虑：既然要严格递增，又要最少次数。因为我们是通过变大使数组递增，所以我们得从左向右判断，会出现两种情况：1.当nums[i]比nums[i-1]大时，这时已经递增，不需要操作。2.当nums[i]比nums[i-1]小时，为了形成严格递增，用时为了减少操作次数，我们应该nums[i]变得正好比nums[i-1]大1即可。此时操作的次数就是nums[i-1]-nums[i]+1。遍历完数组后将每次的操作次数加起来即可。 ? ? ? ?🍋3.贪心思想适用于哪些题目？ ? ? ? ?如果仔细的兄弟肯定发现上面的例题都包含着最少，最多，尽可能等字眼，这确实是可以尝试用贪心思想的重要标志之一 。一般适用于最优化等问题，当然我这例举的题目都是非常简单和基础的，能帮助兄弟们快速感受贪心思想的题目。贪心之所以难，是因为你根本想不到如何去贪，它没有固定模板，所以需要大家从最开始刷题就尝试去练习这种思想 ? ?
神经网络基础（二）
1.2.3 导数理解梯度下降的过程之后，我们通过例子来说明梯度下降在计算导数意义或者说这个导数的意义。1.2.3.1 导数导数也可以理解成某一点处的斜率。斜率这个词更直观一些。各点处的导数值一样我们看到这里有一条直线，这条直线的斜率为4。我们来计算一个例子例：取一点为a=2,那么y的值为8，我们稍微增加a的值为a=2.001,那么y的值为8.004，也就是当a增加了0.001，随后y增加了0.004，即4倍那么我们的这个斜率可以理解为当一个点偏移一个不可估量的小的值，所增加的为4倍。可以记做\frac{f(a)}{da}daf(a)或者\frac{d}{da}f(a)dadf(a)各点的导数值不全一致例：取一点为a=2,那么y的值为4，我们稍微增加a的值为a=2.001,那么y的值约等于4.004（4.004001），也就是当a增加了0.001，随后y增加了4倍取一点为a=5,那么y的值为25，我们稍微增加a的值为a=5.001,那么y的值约等于25.01（25.010001），也就是当a增加了0.001，随后y增加了10倍可以得出该函数的导数2为2a。更多函数的导数结果1.2.3.2 导数计算图那么接下来我们来看看含有多个变量的到导数流程图，假设J(a,b,c) = 3{(a + bc)}J(a,b,c)=3(a+bc)我们以下面的流程图代替这样就相当于从左到右计算出结果，然后从后往前计算出导数导数计算问题：那么现在我们要计算J相对于三个变量a,b,c的导数？假设b=4,c=2,a=7,u=8,v=15,j=45\frac{dJ}{dv}=3dvdJ=3增加v从15到15.001，那么J\approx45.003J≈45.003\frac{dJ}{da}=3dadJ=3增加a从7到7.001,那么v=\approx15.001v=≈15.001，J\approx45.003J≈45.003这里也涉及到链式法则1.2.3.3 链式法则\frac{dJ}{da}=\frac{dJ}{dv}\frac{dv}{da}=3*1=3dadJ=dvdJdadv=3?1=3J相对于a增加的量可以理解为J相对于v*v相对于a增加的接下来计算\frac{dJ}{db}=6=\frac{dJ}{du}\frac{du}{db}=3*2dbdJ=6=dudJdbdu=3?2\frac{dJ}{dc}=9=\frac{dJ}{du}\frac{du}{dc}=3*3dcdJ=9=dudJdcdu=3?31.2.3.4 逻辑回归的梯度下降逻辑回归的梯度下降过程计算图，首先从前往后的计算图得出如下z = w^Tx + bz=wTx+b\hat{y} =a= \sigma(z)y^=a=σ(z)L(\hat{y},y) = -(y\log{a})-(1-y)\log(1-a)L(y^,y)=?(yloga)?(1?y)log(1?a)那么计算图从前向过程为,假设样本有两个特征问题：计算出JJ 关于zz的导数dz = \frac{dJ}{da}\frac{da}{dz} = a-ydz=dadJdzda=a?y
\frac{dJ}{da} = -\frac{y}{a} + \frac{1-y}{1-a}dadJ=?ay+1?a1?y
\frac{da}{dz} = a(1-a)dzda=a(1?a)所以我们这样可以求出总损失相对于w_1,w_2,bw1,w2,b参数的某一点导数，从而可以更新参数\frac{dJ}{dw_1} = \frac{dJ}{dz}\frac{dz}{dw_1}=dz*x1dw1dJ=dzdJdw1dz=dz?x1
\frac{dJ}{dw_2} = \frac{dJ}{dz}\frac{dz}{dw_1}=dz*x2dw2dJ=dzdJdw1dz=dz?x2
\frac{dJ}{db}=dzdbdJ=dz相信上面的导数计算应该都能理解了，所以当我们计算损失函数的某个点相对于w_1,w_2,bw1,w2,b的导数之后，就可以更新这次优化后的结果。w_1 := w_1 - \alpha\frac{dJ(w_1, b)}{dw_1}w1:=w1?αdw1dJ(w1,b)
w_2 := w_2 - \alpha\frac{dJ(w_2, b)}{dw_2}w2:=w2?αdw2dJ(w2,b)
b := b - \alpha\frac{dJ(w, b)}{db}b:=b?αdbdJ(w,b)1.2.4 向量化编程每更新一次梯度时候，在训练期间我们会拥有m个样本，那么这样每个样本提供进去都可以做一个梯度下降计算。所以我们要去做在所有样本上的计算结果、梯度等操作J(w,b) = \frac{1}{m}\sum_{i=1}^mL({a}^{(i)},y^{(i)})J(w,b)=m1∑i=1mL(a(i),y(i))计算参数的梯度为：d(w_1)^{i}, d(w_2)^{i},d(b)^{i}d(w1)i,d(w2)i,d(b)i,这样，我们想要得到最终的d{w_1},d{w_2},d{b}dw1,dw2,db，如何去设计一个算法计算？伪代码实现：初始化，假设{J} = 0, dw_1=0, dw_2=0, db={0}J=0,dw1=0,dw2=0,db=0
forfor i inin m:
z^i = w^Tx^i+{b}zi=wTxi+b
a^i = \sigma(z^i)ai=σ(zi)
J +=-[y^ilog(a^i)+(1-y^i)log(1-a^i)]J+=?[yilog(ai)+(1?yi)log(1?ai)] 每个梯度计算结果相加dz^i = a^i-y^{i}dzi=ai?yi
dw_1 += x_1^idz^idw1+=x1idzi
dw_2 +=x_2^idz^idw2+=x2idzi
db+=dz^idb+=dzi最后求出平均梯度J /=mJ/=m
dw_1 /= mdw1/=m
dw_2 /= mdw2/=m
db /= mdb/=m1.2.4.1 向量化优势什么是向量化由于在进行计算的时候，最好不要使用for循环去进行计算，因为有Numpy可以进行更加快速的向量化计算。在公式z = w^Tx+bz=wTx+b中w,xw,x 都可能是多个值，也就是\bar w = \left(w1?wn
w1?wn
\right), \bar x= \left(
x1?xn
x1?xn
\right)w?=??w1?wn??,x?=??x1?xn??import numpy as np
import time
a = np.random.rand(100000)
b = np.random.rand(100000)第一种方法# 第一种for 循环
c = 0
start = time.time()
for i in range(100000):
c += a[i]*b[i]
end = time.time()
print("计算所用时间%s " % str(1000*(end-start)) + "ms")第二种向量化方式使用np.dot# 向量化运算
start = time.time()
c = np.dot(a, b)
end = time.time()
print("计算所用时间%s " % str(1000*(end-start)) + "ms")
Numpy能够充分的利用并行化，Numpy当中提供了很多函数使用所以上述的m个样本的梯度更新过程，就是去除掉for循环。原本这样的计算1.2.4.2 向量化实现伪代码思路可以变成这样的计算\bar w = \left(
w1?wn
w1?wn
\right)w?=??w1?wn??， \bar{x} = \left(
?x1??x2??x3?????xm?
?????x1x2x3?xm?????
\right)x?=???x1??x2??x3?????xm???注：w的形状为(n,1), x的形状为(n, m)，其中n为特征数量，m为样本数量我们可以让Z= {W^T}X + b=\left(z^1, z^2,z^3\cdots z^m \right)+b=np.dot(W^T,X)+bZ=WTX+b=(z1,z2,z3?zm)+b=np.dot(WT,X)+b，得出的结果为(1, m)大小的矩阵 注：大写的W,XW,X为多个样本表示实现多个样本向量化计算的伪代码初始化，假设n个特征,m个样本J = 0, W=np.zeros([n,1]), b={0}J=0,W=np.zeros([n,1]),b=0
Z= np.dot(W^T,X)+{b}Z=np.dot(WT,X)+b
A = \sigma(Z)A=σ(Z)每个样本梯度计算过程为：dZ = {A}-{Y}dZ=A?Y
dW = \frac{1}{m}X{dZ}^{T}dW=m1XdZT
db=\frac{1}{m}np.sum(dZ)db=m1np.sum(dZ)更新W := W - \alpha{dW}W:=W?αdW
b := b - \alpha{db}b:=b?αdb这相当于一次使用了M个样本的所有特征值与目标值，那我们知道如果想多次迭代，使得这M个样本重复若干次计算1.2.5 正向传播与反向传播前面我们所做的整个过程分为两个部分，一个是从前往后的计算出梯度与损失，另外一部分是从后往前计算参数的更新梯度值。所以在神经网络当中会经常出现两个概念，正向传播与反向传播。
pyEcharts安装及详细使用指南(一）
ECharts是一个纯Javascript的图表库，可以流畅的运行在PC和移动设备上，兼容当前绝大部分浏览器，底层依赖轻量级的Canvas类库ZRender，提供直观、生动、可交互、可高度个性化定制的数据可视化图表。ECharts提供了常规的折线图、柱状图、散点图、饼图、K线图，用于统计的盒形图，用于地理数据可视化的地图、热力图、线图，用于关系数据可视化的关系图、treemap，多维数据可视化的平行坐标，还有用于BI的漏斗图、仪表盘，并且支持图与图之间的混搭。pyEcharts目前有0.5及以下版本和1.0以上版本，新版的pyecharts发生了许多变化。最为明显的是以前调整变量的命令现在都发生了改变。width是旧版本中对图表调整的参数，在新版本这一功能被调整到了option里面。网上大部分教程都是0.5及以下版本。pip install -i https://pypi.tuna.tsinghua.edu.cn/simple pyecharts==0.5.10自从 v0.3.2 开始，为了缩减项目本身的体积以及维持 pyecharts 项目的轻量化运行，pyecharts 将不再自带地图 js 文件。如用户需要用到地图图表，可自行安装对应的地图文件包。下面介绍如何安装。全球国家地图: echarts-countries-pypkg (1.9MB): 世界地图和 213 个国家，包括中国地图中国省级地图: echarts-china-provinces-pypkg (730KB)：23 个省，5 个自治区中国市级地图: echarts-china-cities-pypkg (3.8MB)：370 个中国城市中国县区级地图: echarts-china-counties-pypkg (4.1MB)：2882 个中国县·区中国区域地图: echarts-china-misc-pypkg (148KB)：11 个中国区域地图，比如华南、华北。选择自己需要的安装pip install -i https://pypi.tuna.tsinghua.edu.cn/simple echarts-countries-pypkg
pip install -i https://pypi.tuna.tsinghua.edu.cn/simple echarts-china-provinces-pypkg
pip install -i https://pypi.tuna.tsinghua.edu.cn/simple echarts-china-cities-pypkg
pip install -i https://pypi.tuna.tsinghua.edu.cn/simple echarts-china-counties-pypkg
pip install -i https://pypi.tuna.tsinghua.edu.cn/simple echarts-china-misc-pypkg
pip install -i https://pypi.tuna.tsinghua.edu.cn/simple echarts-united-kingdom-pypkg // 如果提示缺少这个就安装一下
pip install pyecharts_snapshot教育网用户在install 增加 –i https://pypi.tuna.tsinghua.edu.cn/simple注意：1.如果不知道安装那个，就全部安装，反正不会错，安装版本一定是要在0.5及以下。2.如果你安装的是1.0及以上版本，请自行阅读官方文档。https://pyecharts.org/#/zh-cn/intro3.安装完一定要重启pycharm！！！1.柱状图代码如下：# -*- coding:utf-8 -*-
from pyecharts import Bar
bar = Bar("贵州GDP柱状图", "副标题")
bar.add("GDP",["贵阳市", "遵义市", "六盘水市", "安顺市", "黔东南州"],[40, 30, 26, 22, 15])
bar.show_config()
bar.render()代码运行之后，会在本地生成一个render.html文件，打开输出如下所示图形。from pyecharts import Bar
#从pyecharts库中导入Bar子类
bar = Bar("贵州GDP柱状图", "副标题")
#定义Bar()柱状图，同时设置主标题和副标题
bar.add()
#调用add()函数添加图表的数据和设置各种配置项
bar.show_config()
#打印输出图表的所有配置项
bar.render()
#生成render.html文件，也可以设置路径和文件名2.横向柱状图代码如下：# -*- coding:utf-8 -*-
from pyecharts import Bar
bar = Bar("贵州GDP柱状图", "副标题")
city = ["贵阳市", "遵义市", "六盘水市", "安顺市", "黔东南州"]
data1 = [40, 30, 26, 22, 15]
data2 = [13, 43, 32, 38, 20]
bar.add("2017年GDP", city, data1)
bar.add("2016年GDP", city, data2, is_convert=True)
bar.show_config()
bar.render()输出如下图所示：3.带有涟漪特效动画的散点图这段代码参考简书网 https://www.jianshu.com/p/b718c307a61c ，强烈推荐大家学习chenjiandongx大神的文章。完整代码如下：# -*- coding:utf-8 -*-
from pyecharts import EffectScatter
es = EffectScatter("动态散点图各种图形示例")
es.add("", [10], [10], symbol_size=20, effect_scale=3.5, effect_period=3, symbol="pin")
es.add("", [20], [20], symbol_size=12, effect_scale=4.5, effect_period=4, symbol="rect")
es.add("", [30], [30], symbol_size=30, effect_scale=5.5, effect_period=5, symbol="roundRect")
es.add("", [40], [40], symbol_size=10, effect_scale=6.5, effect_brushtype='fill', symbol="diamond")
es.add("", [50], [50], symbol_size=16, effect_scale=5.5, effect_period=3, symbol="arrow")
es.add("", [60], [60], symbol_size=6, effect_scale=2.5, effect_period=3, symbol="triangle")
es.render()运行结果如下图所示：4.绘制3D图形绘制3D折线图代码如下：# -*- coding:utf-8 -*-
from pyecharts import Line3D
import random
data = [[1,2,3,4], [1,2,3,4], [0,4,8,16]]
Line3D = Line3D("3D 折线图示例", width=1200, height=600)
Line3D.add("", data, is_visualmap=True)
Line3D.render()输出图形如下所示：绘制3D散点图，并设置随机散点坐标，代码如下所示：# -*- coding:utf-8 -*-
from pyecharts import Scatter3D
import random
data = [[random.randint(0, 100), random.randint(0, 100), random.randint(0, 100)] for _ in range(80)]
range_color = ['#313695', '#4575b4', '#74add1', '#abd9e9', '#e0f3f8', '#ffffbf',
'#fee090', '#fdae61', '#f46d43', '#d73027', '#a50026']
scatter3D = Scatter3D("3D 散点图示例", width=1200, height=600)
scatter3D.add("", data, is_visualmap=True, visual_range_color=range_color)
scatter3D.render()输出结果非常美观，如下图所示：?
路上，小胖问我：Redis 主从复制原理是怎样的？
00 前言我负责我司的报表系统，小胖是我小弟。随着业务量的增加，单实例顶不住，我就搭建了多个 Redis 实例，实现主从模式。好学的小胖就问我啊，远哥，多实例之间的数据是怎么保持同步的呀？你教教我好不好嘛～我拿起手中 82 年的开水抿了一口，跟小胖说：你先看这篇文章，学会了操作，我再给你讲讲原理吧。https://juejin.cn/post/6844903650175746056#heading-0老规矩，还是先上脑图：（PS：文末有我准备的大厂面试题）01 主从复制Redis 的高可靠主要由两点保证，一是数据尽量少丢失，二是服务尽量少中断。持久化保证了第一点；而第二点则由 Redis 集群保证，Redis 的做法就是多实例保持数据同步。1.1 读写分离Redis 提供了主从库模式，以保证数据副本的一致，主从库之间采用的是读写分离的方式。读操作：主库、从库都可以接收；写操作：首先到主库执行，然后，主库将写操作同步给从库。为什么要读写分离呢？看看上图，如果所有库都可以写，那将会发生一个 key 在不同实例就有不同的值。比如上图对应的键 k1 在不同实例就有不同的 v1、v2、v3 值，这是绝对不能接受的。有人说，，可以加锁呀但是这会涉及到加锁、实例间协商是否完成修改等一堆操作，带来巨额的开销，Redis 以快著称，这也是不能接受的。那咋办呀？读写分离咯主从库模式采用读写分离，所有数据修改只会在主库进行。主库有最新数据，会同步给从库，这样，主从库的数据就是一致的。问题就在同步了，主从库之间是怎么同步的呢？一起来探讨下1.2 全量复制当我们启动多个 Redis 实例的时候，它们相互之间就通过 replicaof（Redis 5.0 之前使用 slaveof）命令形成主库和从库的关系，之后会按照三个阶段完成数据的第一次同步。比如现在有实例 1（127.0.0.1）和实例 2（127.0.0.2），在实例 2 执行 replicaof 后，实例 2 就变成实例 1 的从库啦。replicaof 127.0.0.2 6379建立关系之后，Redis 会进行第一次全量复制。过程如下：第一步，主从库建立连接、协商同步的过程，主要是为全量复制做准备。从库给主库发送 psync 命令，表示要进行数据同步，主库根据这个命令的参数来启动复制。psync 命令包含了主库的 runID 和复制进度 offset 两个参数。runID，是每个 Redis 实例启动时都会自动生成的一个随机 ID，用来唯一标记这个实例。当从库和主库第一次复制时，因为不知道主库的 runID，所以将 runID 设为 “？”。offset，此时设为 -1，表示第一次复制。主库收到 psync 命令后，会用 FULLRESYNC 响应命令带上两个参数：主库 runID 和主库目前的复制进度 offset，返回给从库。FULLRESYNC 响应表示第一次复制采用的全量复制，也就是说，主库会把当前所有的数据都复制给从库。第二步，主库执行 bgsave 命令，生成 RDB 文件，发送给从库。从库收到后，先清空自己的数据（避免主从不一致），在本地完成数据加载。主库在将数据同步给从库的过程中，仍然可以正常接收请求。但是，这些请求中的写操作并没有记录到刚刚生成的 RDB 文件中。为了保证主从一致性，主库会在内存中用 replication buffer 记录 RDB 文件生成后收到的所有写操作。第三步，主库会把 replication buffer 中的修改操作发给从库，从库再重新执行这些操作。如此，主从就实现了同步。1.3 主从级联分散压力以上还有个问题：如果直接跟主库建立关系的从库非常多，那么主库会 fork 很多线程去生成 RDB 和 发送 RDB 文件，这将会造成主库阻塞。那咋办？主从级联的模式就来了：选一个资源较多的实例作为级联的从库，作为叶子节点的从库执行以下命令将所选从库作为主库，这样就形成了级联关系。replicaof 所选从库的IP 6379如上图，主库就跟两个实例做主从关系，从库又跟另外的从库建立主从关系，类似于树结构。如此，主库便可减少压力。就上图来说，主库原来要跟 4 个从库建立主从关系；加了级联之后，只需要建立两个主从关系，剩下的由某一个从库去承担。这颇有点父养子，子又养子的意思。这个过程也称为基于长连接的命令传播，可以避免频繁建立连接的开销。1.4 增量复制细想一下，上面的主从复制还有问题：如果主从之间的网络断开了咋办？其实 Redis 2.8 之前，主从断开了，做的是全量复制。但这种方式开销太大，已被淘汰。2.8 之后的 Redis 采用的是增量复制。增量复制依赖一个环形缓冲区 repl_backlog_buffer（只要有从库存在，就会有这个缓存区），主从断连后，主库会把断连期间的写操作命令，写入 repl_backlog_buffer 缓冲区。repl_backlog_buffer 是一个环形缓冲区，主库会记录自己写到的位置，从库则会记录自己已经读到的位置。如上图所示，还没断连时，主从指向同一个位置；主库写，从库读，一直往前走。突然，断连了，从库没法写、主库继续读。恢复连接后，从库发送 psync {runID}{offset} 告诉主库，自己上次读到哪。主库通过 offset 在 repl_backlog_buffer 中找到从库断开的位置，主从之间的偏移量就是增量复制需要同步的内容。比如上图的 put d e 和 put d f 两个操作。把这部分增量数据复制到 repl_buffer 中，主库再发送给从库读入。基于此增量复制的整个流程是这样的：你可能也发现了？repl_backlog_buffer 是环形缓存区，如果从库断开时间太久，就有可能导致从库还未读取的操作被主库新写的操作覆盖了，这会导致主从库间的数据不一致。这该咋办呀？连接恢复后，主库根据从库上次读到的 offset 位置判断是否被覆盖？如果是，?从库连上主库后也只能乖乖地进行一次全量同步。为了避免全量同步，可以通过参数 repl_backlog_size 设置 repl_backlog_buffer 的大小，把它弄大点。计算公式是：缓冲空间大小 = 主库写入命令速度 * 操作大小 - 主从库间网络传输命令速度 * 操作大小repl_backlog_size = 缓冲空间大小 * 2这样一来，发生全量同步的概率就小了很多了。02 总结本文主要讲了 Redis 的主从模式为什么要读写分离？Redis 全量复制的流程以及原理；从库很多时，如何降低主库复制的压力？如果主从断开了，Redis 是怎么进行数据同步的？希望你看完能有所收获。好啦，以上就是狗哥关于 Redis 主从复制的总结。感谢各技术社区大佬们的付出，尤其是极客时间，真的牛逼。如果说我看得更远，那是因为我站在你们的肩膀上。希望这篇文章对你有帮助，我们下篇文章见～
最新 | 10 道 BAT 大厂海量数据面试题（附题解+方法总结）
先来看一下都有哪些题目：?如何从大量的 URL 中找出相同的 URL？（百度）?如何从大量数据中找出高频词？（百度）?如何找出某一天访问百度网站最多的 IP？（百度）?如何在大量的数据中找出不重复的整数？（百度）?如何在大量的数据中判断一个数是否存在？（腾讯）?如何查询最热门的查询串？（腾讯）?如何统计不同电话号码的个数？（百度）?如何从 5 亿个数中找出中位数？（百度）?如何按照 query 的频度排序？（百度）?如何找出排名前 500 的数？（腾讯）答案呢？往下看~题目1题目描述给定 a、b 两个文件，各存放 50 亿个 URL，每个 URL 各占 64B，内存限制是 4G。请找出 a、b 两个文件共同的 URL。解答思路每个 URL 占 64B，那么 50 亿个 URL占用的空间大小约为 320GB。5,000,000,000 * 64B ≈ 5GB * 64 = 320GB由于内存大小只有 4G，因此，我们不可能一次性把所有 URL 加载到内存中处理。对于这种类型的题目，一般采用分治策略，即：把一个文件中的 URL 按照某个特征划分为多个小文件，使得每个小文件大小不超过 4G，这样就可以把这个小文件读到内存中进行处理了。思路如下：首先遍历文件 a，对遍历到的 URL 求 hash(URL) % 1000，根据计算结果把遍历到的 URL 存储到文件 a0, a1, a2, ..., a999，这样每个大小约为 300MB。使用同样的方法遍历文件 b，把文件 b 中的 URL 分别存储到文件 b0, b1, b2, ..., b999 中。这样处理过后，所有可能相同的 URL 都在对应的小文件中，即 a0 对应 b0, ..., a999 对应 b999，不对应的小文件不可能有相同的 URL。那么接下来，我们只需要求出这 1000 对小文件中相同的 URL 就好了。接着遍历 ai( i∈[0,999])，把 URL 存储到一个 HashSet 集合中。然后遍历 bi 中每个 URL，看在 HashSet 集合中是否存在，若存在，说明这就是共同的 URL，可以把这个 URL 保存到一个单独的文件中。方法总结1.分而治之，进行哈希取余；2.对每个子文件进行 HashSet 统计。题目2题目描述有一个 1GB 大小的文件，文件里每一行是一个词，每个词的大小不超过 16B，内存大小限制是 1MB，要求返回频数最高的 100 个词(Top 100)。解答思路由于内存限制，我们依然无法直接将大文件的所有词一次读到内存中。因此，同样可以采用分治策略，把一个大文件分解成多个小文件，保证每个文件的大小小于 1MB，进而直接将单个小文件读取到内存中进行处理。思路如下：首先遍历大文件，对遍历到的每个词x，执行 hash(x) % 5000，将结果为 i 的词存放到文件 ai 中。遍历结束后，我们可以得到 5000 个小文件。每个小文件的大小为 200KB 左右。如果有的小文件大小仍然超过 1MB，则采用同样的方式继续进行分解。接着统计每个小文件中出现频数最高的 100 个词。最简单的方式是使用 HashMap 来实现。其中 key 为词，value 为该词出现的频率。具体方法是：对于遍历到的词 x，如果在 map 中不存在，则执行 map.put(x, 1)；若存在，则执行 map.put(x, map.get(x)+1)，将该词频数加 1。上面我们统计了每个小文件单词出现的频数。接下来，我们可以通过维护一个小顶堆来找出所有词中出现频数最高的 100 个。具体方法是：依次遍历每个小文件，构建一个小顶堆，堆大小为 100。如果遍历到的词的出现次数大于堆顶词的出现次数，则用新词替换堆顶的词，然后重新调整为小顶堆，遍历结束后，小顶堆上的词就是出现频数最高的 100 个词。方法总结1.分而治之，进行哈希取余；2.使用 HashMap 统计频数；3.求解最大的 TopN 个，用小顶堆；求解最小的 TopN 个，用大顶堆。题目3题目描述现有海量日志数据保存在一个超大文件中，该文件无法直接读入内存，要求从中提取某天访问百度次数最多的那个 IP。解答思路这道题只关心某一天访问百度最多的 IP，因此，可以首先对文件进行一次遍历，把这一天访问百度 IP 的相关信息记录到一个单独的大文件中。接下来采用的方法与上一题一样，大致就是先对 IP 进行哈希映射，接着使用 HashMap 统计重复 IP 的次数，最后计算出重复次数最多的 IP。注：这里只需要找出出现次数最多的 IP，可以不必使用堆，直接用一个变量 max 即可。方法总结1.分而治之，进行哈希取余；2.使用 HashMap 统计频数；3.求解最大的 TopN 个，用小顶堆；求解最小的 TopN 个，用大顶堆。题目4题目描述在 2.5 亿个整数中找出不重复的整数。注意：内存不足以容纳这 2.5 亿个整数。解答思路方法一：分治法与前面的题目方法类似，先将 2.5 亿个数划分到多个小文件，用 HashSet/HashMap 找出每个小文件中不重复的整数，再合并每个子结果，即为最终结果。方法二：位图法位图，就是用一个或多个 bit 来标记某个元素对应的值，而键就是该元素。采用位作为单位来存储数据，可以大大节省存储空间。位图通过使用位数组来表示某些元素是否存在。它可以用于快速查找，判重，排序等。不是很清楚？我先举个小例子。假设我们要对 [0,7] 中的 5 个元素 (6, 4, 2, 1, 5) 进行排序，可以采用位图法。0~7 范围总共有 8 个数，只需要 8bit，即 1 个字节。首先将每个位都置 0：0 0 0 0 0 0 0 0然后遍历 5 个元素，首先遇到 6，那么将下标为 6 的位的 0 置为 1；接着遇到 4，把下标为 4 的位 的 0 置为 1：0 0 0 0 1 0 1 0依次遍历，结束后，位数组是这样的：0 1 1 0 1 1 1 0每个为 1 的位，它的下标都表示了一个数：for i in range(8): if bits[i] == 1: print(i)这样我们其实就已经实现了排序。对于整数相关的算法的求解，位图法是一种非常实用的算法。假设 int 整数占用 4B，即 32bit，那么我们可以表示的整数的个数为 232。那么对于这道题，我们用 2 个 bit 来表示各个数字的状态：?00 表示这个数字没出现过；?01 表示这个数字出现过一次（即为题目所找的不重复整数）；?10 表示这个数字出现了多次。那么这 232 个整数，总共所需内存为 232*2b=1GB。因此，当可用内存超过 1GB 时，可以采用位图法。假设内存满足位图法需求，进行下面的操作：遍历 2.5 亿个整数，查看位图中对应的位，如果是 00，则变为 01，如果是 01 则变为 10，如果是 10 则保持不变。遍历结束后，查看位图，把对应位是 01 的整数输出即可。方法总结判断数字是否重复的问题，位图法是一种非常高效的方法。题目5题目描述给定 40 亿个不重复的没排过序的 unsigned int 型整数，然后再给定一个数，如何快速判断这个数是否在这 40 亿个整数当中？解答思路方法一：分治法依然可以用分治法解决，方法与前面类似，就不再次赘述了。方法二：位图法40 亿个不重复整数，我们用 40 亿个 bit 来表示，初始位均为 0，那么总共需要内存：4,000,000,000b≈512M。我们读取这 40 亿个整数，将对应的 bit 设置为 1。接着读取要查询的数，查看相应位是否为 1，如果为 1 表示存在，如果为 0 表示不存在。方法总结判断数字是否存在、判断数字是否重复的问题，位图法是一种非常高效的方法。题目6题目描述搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询床的长度不超过 255 字节。假设目前有 1000w 个记录（这些查询串的重复度比较高，虽然总数是 1000w，但如果除去重复后，则不超过 300w 个）。请统计最热门的 10 个查询串，要求使用的内存不能超过 1G。（一个查询串的重复度越高，说明查询它的用户越多，也就越热门。）解答思路每个查询串最长为 255B，1000w 个串需要占用 约 2.55G 内存，因此，我们无法将所有字符串全部读入到内存中处理。方法一：分治法分治法依然是一个非常实用的方法。划分为多个小文件，保证单个小文件中的字符串能被直接加载到内存中处理，然后求出每个文件中出现次数最多的 10 个字符串；最后通过一个小顶堆统计出所有文件中出现最多的 10 个字符串。方法可行，但不是最好，下面介绍其他方法。方法二：HashMap 法虽然字符串总数比较多，但去重后不超过 300w，因此，可以考虑把所有字符串及出现次数保存在一个 HashMap 中，所占用的空间为 300w*(255+4)≈777M（其中，4表示整数占用的4个字节）。由此可见，1G 的内存空间完全够用。思路如下：首先，遍历字符串，若不在 map 中，直接存入 map，value 记为 1；若在 map 中，则把对应的 value 加 1，这一步时间复杂度 O(N)。接着遍历 map，构建一个 10 个元素的小顶堆，若遍历到的字符串的出现次数大于堆顶字符串的出现次数，则进行替换，并将堆调整为小顶堆。遍历结束后，堆中 10 个字符串就是出现次数最多的字符串。这一步时间复杂度 O(Nlog10)。方法三：前缀树法方法二使用了 HashMap 来统计次数，当这些字符串有大量相同前缀时，可以考虑使用前缀树来统计字符串出现的次数，树的结点保存字符串出现次数，0 表示没有出现。思路如下：在遍历字符串时，在前缀树中查找，如果找到，则把结点中保存的字符串次数加 1，否则为这个字符串构建新结点，构建完成后把叶子结点中字符串的出现次数置为 1。最后依然使用小顶堆来对字符串的出现次数进行排序。方法总结前缀树经常被用来统计字符串的出现次数。它的另外一个大的用途是字符串查找，判断是否有重复的字符串等。题目7题目描述已知某个文件内包含一些电话号码，每个号码为 8 位数字，统计不同号码的个数。解答思路这道题本质还是求解数据重复的问题，对于这类问题，一般首先考虑位图法。对于本题，8 位电话号码可以表示的号码个数为 108 个，即 1 亿个。我们每个号码用一个 bit 来表示，则总共需要 1 亿个 bit，内存占用约 100M。思路如下：申请一个位图数组，长度为 1 亿，初始化为 0。然后遍历所有电话号码，把号码对应的位图中的位置置为 1。遍历完成后，如果 bit 为 1，则表示这个电话号码在文件中存在，否则不存在。bit 值为 1 的数量即为 不同电话号码的个数。方法总结求解数据重复问题，记得考虑位图法。题目8题目描述从 5 亿个数中找出中位数。数据排序后，位置在最中间的数就是中位数。当样本数为奇数时，中位数为 第 (N+1)/2 个数；当样本数为偶数时，中位数为 第 N/2 个数与第 1+N/2 个数的均值。解答思路如果这道题没有内存大小限制，则可以把所有数读到内存中排序后找出中位数。但是最好的排序算法的时间复杂度都为 O(NlogN)。这里使用其他方法。方法一：双堆法维护两个堆，一个大顶堆，一个小顶堆。大顶堆中最大的数小于等于小顶堆中最小的数；保证这两个堆中的元素个数的差不超过 1。若数据总数为偶数，当这两个堆建好之后，中位数就是这两个堆顶元素的平均值。当数据总数为奇数时，根据两个堆的大小，中位数一定在数据多的堆的堆顶。class MedianFinder {
private PriorityQueue<Integer> maxHeap; private PriorityQueue<Integer> minHeap;
/** initialize your data structure here. */ public MedianFinder() { maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); minHeap = new PriorityQueue<>(Integer::compareTo); }
public void addNum(int num) { if (maxHeap.isEmpty() || maxHeap.peek() > num) { maxHeap.offer(num); } else { minHeap.offer(num); }
int size1 = maxHeap.size(); int size2 = minHeap.size(); if (size1 - size2 > 1) { minHeap.offer(maxHeap.poll()); } else if (size2 - size1 > 1) { maxHeap.offer(minHeap.poll()); } }
public double findMedian() { int size1 = maxHeap.size(); int size2 = minHeap.size();
return size1 == size2 ? (maxHeap.peek() + minHeap.peek()) * 1.0 / 2 : (size1 > size2 ? maxHeap.peek() : minHeap.peek()); }}见 LeetCode No.295：https://leetcode.com/problems/find-median-from-data-stream/以上这种方法，需要把所有数据都加载到内存中。当数据量很大时，就不能这样了，因此，这种方法适用于数据量较小的情况。5 亿个数，每个数字占用 4B，总共需要 2G 内存。如果可用内存不足 2G，就不能使用这种方法了，下面介绍另一种方法。方法二：分治法分治法的思想是把一个大的问题逐渐转换为规模较小的问题来求解。对于这道题，顺序读取这 5 亿个数字，对于读取到的数字 num，如果它对应的二进制中最高位为 1，则把这个数字写到 f1 中，否则写入 f0 中。通过这一步，可以把这 5 亿个数划分为两部分，而且 f0 中的数都大于 f1 中的数（最高位是符号位）。划分之后，可以非常容易地知道中位数是在 f0 还是 f1 中。假设 f1 中有 1 亿个数，那么中位数一定在 f0 中，且是在 f0 中，从小到大排列的第 1.5 亿个数与它后面的一个数的平均值。提示，5 亿数的中位数是第 2.5 亿与右边相邻一个数求平均值。若 f1 有一亿个数，那么中位数就是 f0 中从第 1.5 亿个数开始的两个数求得的平均值。对于 f0 可以用次高位的二进制继续将文件一分为二，如此划分下去，直到划分后的文件可以被加载到内存中，把数据加载到内存中以后直接排序，找出中位数。注意，当数据总数为偶数，如果划分后两个文件中的数据有相同个数，那么中位数就是数据较小的文件中的最大值与数据较大的文件中的最小值的平均值。方法总结分治法，真香！题目9题目描述有 10 个文件，每个文件大小为 1G，每个文件的每一行存放的都是用户的 query，每个文件的 query 都可能重复。要求按照 query 的频度排序。解答思路如果 query 的重复度比较大，可以考虑一次性把所有 query 读入内存中处理；如果 query 的重复率不高，那么可用内存不足以容纳所有的 query，这时候就需要采用分治法或其他的方法来解决。方法一：HashMap 法如果 query 重复率高，说明不同 query 总数比较小，可以考虑把所有的 query 都加载到内存中的 HashMap 中。接着就可以按照 query 出现的次数进行排序。方法二：分治法分治法需要根据数据量大小以及可用内存的大小来确定问题划分的规模。对于这道题，可以顺序遍历 10 个文件中的 query，通过 Hash 函数 hash(query) % 10 把这些 query 划分到 10 个小文件中。之后对每个小文件使用 HashMap 统计 query 出现次数，根据次数排序并写入到零外一个单独文件中。接着对所有文件按照 query 的次数进行排序，这里可以使用归并排序（由于无法把所有 query 都读入内存，因此需要使用外排序）。方法总结?内存若够，直接读入进行排序；?内存不够，先划分为小文件，小文件排好序后，整理使用外排序进行归并。题目10题目描述有 20 个数组，每个数组有 500 个元素，并且有序排列。如何在这 20*500 个数中找出前 500 的数？解答思路对于 TopK 问题，最常用的方法是使用堆排序。对本题而言，假设数组降序排列，可以采用以下方法：首先建立大顶堆，堆的大小为数组的个数，即为 20，把每个数组最大的值存到堆中。接着删除堆顶元素，保存到另一个大小为 500 的数组中，然后向大顶堆插入删除的元素所在数组的下一个元素。重复上面的步骤，直到删除完第 500 个元素，也即找出了最大的前 500 个数。为了在堆中取出一个数据后，能知道它是从哪个数组中取出的，从而可以从这个数组中取下一个值，可以把数组的指针存放到堆中，对这个指针提供比较大小的方法。import lombok.Data;
import java.util.Arrays;import java.util.PriorityQueue;
/** * @author https://github.com/yanglbme */@Datapublic class DataWithSource implements Comparable<DataWithSource> { /** * 数值 */ private int value;
/** * 记录数值来源的数组 */ private int source;
/** * 记录数值在数组中的索引 */ private int index;
public DataWithSource(int value, int source, int index) { this.value = value; this.source = source; this.index = index; }
/** * * 由于 PriorityQueue 使用小顶堆来实现，这里通过修改 * 两个整数的比较逻辑来让 PriorityQueue 变成大顶堆 */ @Override public int compareTo(DataWithSource o) { return Integer.compare(o.getValue(), this.value); }}
class Test { public static int[] getTop(int[][] data) { int rowSize = data.length; int columnSize = data[0].length;
// 创建一个columnSize大小的数组，存放结果 int[] result = new int[columnSize];
PriorityQueue<DataWithSource> maxHeap = new PriorityQueue<>(); for (int i = 0; i < rowSize; ++i) { // 将每个数组的最大一个元素放入堆中 DataWithSource d = new DataWithSource(data[i][0], i, 0); maxHeap.add(d); }
int num = 0; while (num < columnSize) { // 删除堆顶元素 DataWithSource d = maxHeap.poll(); result[num++] = d.getValue(); if (num >= columnSize) { break; }
d.setValue(data[d.getSource()][d.getIndex() + 1]); d.setIndex(d.getIndex() + 1); maxHeap.add(d); } return result;
}
public static void main(String[] args) { int[][] data = { {29, 17, 14, 2, 1}, {19, 17, 16, 15, 6}, {30, 25, 20, 14, 5}, };
int[] top = getTop(data); System.out.println(Arrays.toString(top)); // [30, 29, 25, 20, 19] }}方法总结求 TopK，不妨考虑一下堆排序？以上，完。
《MySQL》系列 - 小胖问我：MySQL 日志到底有啥用？菜！
01 前言事情是这样的，我负责我司的报表系统，小胖是我小弟。某天他手贱误删了一条生产的数据。被用户在群里疯狂投诉质问，火急火燎的跑来问我怎么办。我特么冷汗都出来了，训斥了他一顿：蠢，蠢得都可以进博物馆了，生产的数据能随便动？小胖看我平常笑嘻嘻的，没想到发这么大的火。心一急，居然给我跪下了：远哥，我上有老，下有小，中有女朋友，不要开除我呀。我一听火更大了：合着就你有女朋友？？？这个时候我们 DBA 老林来打圆场：别慌，年轻人管不住下本身，难免做错事。我可以把数据恢复到一个月内任意时刻的状态。听到这，小胖忙抱着老林大腿哭爹喊娘地感谢。听到这你是不是很奇怪？能恢复到半个月前的数据？DBA 老林到底是如何做到的？我跟他细聊了一番。老林点燃了手中 82 年的华子，深深吸了一口说到：事情还得从 update 语句是如何执行的说起。1.1 从更新语句说起假设我现在有建表语句，如下：CREATE TABLE `student` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(100) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL,
`age` int(11) NULL DEFAULT NULL,
PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB AUTO_INCREMENT = 66 CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Compact;表数据如下：今天恰好张三生日，我要把它的 age 加一岁。于是执行以下的 sql 语句：update student set age = age + 1 where id = 2;前面聊过查询语句是如何执行的？错过的同学看这篇《工作三年：小胖连 select 语句是如何执行的都不知道，真的菜！》，里面的查询语句流程，更新语句也会走一遍，如下流程图：update 语句发起：首先连接器会连接数据库。接着分析器通过词法、语法分析知道这是更新语句。所以查询缓存失效。之前的文章提到：如果表有更新。那么它的查询缓存会失败。这也是为啥，我不建议你使用查询缓存的原因。优化器则决定使用 ID 索引去更新，最后执行器负责找到这行数据，执行更新。重点来了：与查询流程不一样，更新还涉及两个重要的日志模块。一是重做日志：redo log，二是归档日志：binlog。要解答文章开头的问题，必须要明白这两日志的原理才能整明白 DBA 是怎么做到的。02 事务日志：redo log什么是 redo log？为了方便理解，先举个来自极客时间的例子：还记得《孔乙己》这篇文章，饭店掌柜有一个粉板，专门用来记录客人的赊账记录。如果赊账的人不多，那么他可以把顾客名和账目写在板上。但如果赊账的人多了，粉板总会有记不下的时候，这个时候掌柜一定还有一个专门记录赊账的账本。如果有人要赊账或者还账的话，掌柜一般有两种做法：一种做法是直接把账本翻出来，把这次赊的账加上去或者扣除掉；另一种做法是先在粉板上记下这次的账，等打烊以后再把账本翻出来核算。在生意红火柜台很忙时，掌柜一定会选择后者，因为前者操作实在是太麻烦了。首先，你得找到这个人的赊账总额那条记录。你想想，密密麻麻几十页，掌柜要找到那个名字，可能还得带上老花镜慢慢找，找到之后再拿出算盘计算，最后再将结果写回到账本上。这整个过程想想都麻烦。相比之下，还是先在粉板上记一下方便。你想想，如果掌柜没有粉板的帮助，每次记账都得翻账本，效率是不是低得让人难以忍受？2.1 为什么需要 redo log？同样，在 MySQL 中，如果每一次的更新要写进磁盘，这么做会带来严重的性能问题：因为 Innodb 是以页为单位进行磁盘交互的，而一个事务很可能只修改一个数据页里面的几个字节，这时将完整的数据页刷到磁盘的话，太浪费资源了！一个事务可能涉及修改多个数据页，并且这些数据页在物理上并不连续，使用随机 IO 写入性能太差！为了解决这个问题，MySQL 的设计者就用了类似掌柜粉板的思路来提升更新效率。这种思路在 MySQL 中叫 WAL（Write-Ahead Logging），意思就是：先写 redo log 日志，后写磁盘。日志和磁盘就对应上面的粉板和账本。具体到 MySQL 是这样的：有记录需要更新，InnDB 把记录写到 redo log 中，并更新内存中的数据页，此时更新就算完成。同时，后台线程会把操作记录更新异步到磁盘中的数据页。PS：当需要更新的数据页在内存中时，就会直接更新内存中的数据页；不在内存中时，在可以使用 change buffer（篇幅有限，这个后面写文章再聊） 的情况下，就会将更新操作记录到 change buffer 中，并将这些操作记录到 redo log 中；如果此时有查询操作，则触发 merge 操作，返回更改后的记录值。有些人说 InnoDB 引擎把日志记录写到 redo log 中，redo log 在哪，不也是在磁盘上么？对，这也是一个写磁盘的过程，但是与更新过程不一样的是，更新过程是在磁盘上随机 IO，费时。而写 redo log 是在磁盘上顺序 IO，效率要高。PPS：redo log 的存在就是把全局的随机写，变换为局部的顺序写，从而提高效率。2.2 redo log 的写入过程redo log 记录了事务对数据页做了哪些修改。它包括两部分：分别是内存中的日志缓冲（redo log buffer）和磁盘上的日志文件（redo logfile）。mysql 每执行一条 DML 语句，先将记录写入 redo log buffer，后续某个时间点再一次性将多个操作记录写到 redo log file。也就是我们上面提到的 WAL 技术。计算机操作系统告诉我们：用户空间下的缓冲区数据是无法直接写入磁盘的。因为中间必须经过操作系统的内核空间缓冲区（OS Buffer）。所以，redo log buffer 写入 redo logfile 实际上是先写入 OS Buffer，然后操作系统调用 fsync () 函数将日志刷到磁盘。过程如下：mysql 支持三种将 redo log buffer 写入 redo log file 的时机，可以通过 innodb_flush_log_at_trx_commit 参数配置，各参数值含义如下：建议设置成 1，这样可以保证 MySQL 异常重启之后数据不丢失。参数值含义0（延迟写）事务提交时不会将 redo log buffer 中日志写到 os buffer，而是每秒写入 os buffer 并调用 fsync () 写入到 redo logfile 中。也就是说设置为 0 时是（大约）每秒刷新写入到磁盘中的，当系统崩溃，会丢失 1 秒钟的数据。1（实时写、实时刷新）事务每次提交都会将 redo log buffer 中的日志写入 os buffer 并调用 fsync () 刷到 redo logfile 中。这种方式即使系统崩溃也不会丢失任何数据，但是因为每次提交都写入磁盘，IO 的性能差。2（实时写、延迟刷新刷新）每次提交都仅写入到 os buffer，然后是每秒调用 fsync () 将 os buffer 中的日志写入到 redo log file。写的过程如下：2.3 redo log file 的结构InnoDB 的 redo log 是固定大小的。比如可以配置为一组 4 个文件，每个文件的大小是 1GB，那么 redo log file 可以记录 4GB 的操作。从头开始写。写到末尾又回到开头循环写。如下图：上图中，write pos 表示 redo log 当前记录的 LSN (逻辑序列号) 位置，一边写一遍后移，写到第 3 号文件末尾后就回到 0 号文件开头；check point 表示数据页更改记录刷盘后对应 redo log 所处的 LSN (逻辑序列号) 位置，也是往后推移并且循环的。PS：check point 是当前要擦除的位置，它与数据页中的 LSN 应当是一致的。write pos 到 check point 之间的部分是 redo log 的未写区域，可用于记录新的记录；check point 到 write pos 之间是 redo log 已写区域，是待刷盘的数据页更改记录。当 write pos 追上 check point 时，表示 redo log file 写满了，这时候有就不能执行新的更新。得停下来先擦除一些记录（擦除前要先把记录刷盘），再推动 check point 向前移动，腾出位置再记录新的日志。2.4 什么是 crash-save ？有了 redo log ，即在 InnoDB 存储引擎中，事务提交过程中任何阶段，MySQL 突然奔溃，重启后都能保证事务的完整性，已提交的数据不会丢失，未提交完整的数据会自动进行回滚。这个能力称为 crash-safe，依赖的就是 redo log 和 undo log 两个日志。比如：重启 innodb 时，首先会检查磁盘中数据页的 LSN ，如果数据页的 LSN 小于日志中 check point 的 LSN ，则会从 checkpoint 开始恢复。2.5 回滚日志 undo log**undo log，主要提供回滚的作用，但还有另一个作用，就是多个行版本控制 (MVCC)，保证事务的原子性。** 在数据修改的流程中，会记录一条与当前操作相反的逻辑日志到 undo log 中（可以认为当 delete 一条记录时，undo log 中会记录一条对应的 insert 记录，反之亦然，当 update 一条记录时，它记录一条对应相反的 update 记录），如果因为某些原因导致事务异常失败了，可以借助该 undo log 进行回滚，保证事务的完整性，所以 undo log 也必不可少。03 归档日志：binlog上一篇聊查询语句的执行过程时，聊到 MySQL 的架构包含 server 层和引擎层。而 redo log 是 InnoDB 引擎特有的日志，而 server 层也有自己的日志，那就是 binlog。最开始 MySQL 里并没有 InnoDB 引擎。MySQ L 自带的引擎是 MyISAM，但是 MyISAM 没有 crash-safe 的能力，binlog 日志只能用于归档。而 InnoDB 是另一个公司以插件形式引入 MySQL 的，只依靠 binlog 是没有 crash-safe 能力的，所以 InnoDB 使用另外一套日志系统 —— 也就是 redo log 来实现 crash-safe 能力。3.1 binlog 日志格式？binlog 有三种格式，分别为 STATMENT 、 ROW 和 MIXED。在 MySQL 5.7.7 之前，默认的格式是 STATEMENT ， MySQL 5.7.7 之后，默认值是 ROW。日志格式通过 binlog-format 指定。STATMENT：每一条会修改数据的 sql 语句会记录到 binlog 中 ?。ROW：不记录 sql 的上下文信息，仅需记录哪条数据被修改。记两条，更新前和更新后都有。MIXED：前两种模式的混合，一般的复制使用 STATEMENT 模式保存 binlog ，对于 STATEMENT 模式无法复制的操作使用 ROW 模式保存 binlog3.2 binlog 可以做 crash-save 吗？只用一个 binlog 是否可以实现 cash_safe 能力呢？答案是可以的，只不过 binlog 中也要加入 checkpoint，数据库故障重启后，binlog checkpoint 之后的 sql 都重放一遍。但是这样做让 binlog 耦合的功能太多。有人说，也可以直接直接对比匹配全量 binlog 和磁盘数据库文件，但这样做的话，效率低不说。因为 binlog 是 server 层的记录并不是引擎层的，有可能导致数据不一致的情况：假如 binlog 记录了 3 条数据，正常情况引擎层也写了 3 条数据，但是此时节点宕机重启，binlog 发现有 3 条记录需要回放，所以回放 3 条记录，但是引擎层可能已经写入了 2 条数据到磁盘，只需要回放一条 1 数据。那 binlog 回放的前两条数据会不会重复呢，比如会报错 duplicate key。另外，binlog 是追加写，crash 时不能判定 binlog 中哪些内容是已经写入到磁盘，哪些还没被写入。而 redolog 是循环写，从 check point 到 write pos 间的内容都是未写入到磁盘的。所以，binlog 并不适合做 crash-save。3.3 两种日志的区别redo log 和 binlog 主要有三种不同：redo log 是 InnoDB 引擎特有的；binlog 是 MySQL 的 Server 层实现的，所有引擎都可以使用。redo log 是物理日志，记录的是在某个数据页上做了什么修改；binlog 是逻辑日志，记录的是这个语句的原始逻辑，比如 **"给 ID=2 这一行的 age 字段加 1"**。redo log 是循环写的，空间固定会用完；binlog 是可以追加写入的。追加写是指 binlog 文件写到一定大小后会切换到下一个，并不会覆盖以前的日志。3.4 update 语句的执行流程了解了两种日志的概念，再来看看执行器和 InnoDB 引擎在执行 update 语句时的流程：执行器取 id = 2 的行数据。ID 是主键，引擎用树搜索找到这一行。如果这一行所在的数据页本来就在内存中，就直接返回给执行器；否则，需要先从磁盘读入内存，再返回。执行器拿到引擎给的行数据，把这个值加上 1，比如原来是 N，现在就是 N+1，得到新的一行数据，再调用引擎接口写入这行新数据。引擎将这行新数据更新到内存中，同时将这个更新操作记录到 redo log 里面，此时 redo log 处于 prepare 状态。然后告知执行器执行完成了，随时可以提交事务。执行器生成这个操作的 binlog，并把 binlog 写入磁盘。执行器调用引擎的提交事务接口，引擎把刚刚写入的 redo log 改成提交（commit）状态，redo log 会写入 binlog 的文件名和位置信息来保证 binlog 和 redo log 的一致性，更新完成。整个过程如下图所示，其中橙色框表示是在 InnoDB 内部执行的，绿色框表示是在执行器中执行的：3.5 两阶段提交由于 redo log 和 binlog 是两个独立的逻辑，如果不用两阶段提交，要么就是先写完 redo log 再写 binlog，或者采用反过来的顺序。我们看看这两种方式会有什么问题。仍然用前面的 update 语句来做例子。假设当前 id=2 的行，字段 age 的值是 22，再假设执行 update 语句过程中在写完第一个日志后，第二个日志还没有写完期间发生了 crash，会出现什么情况呢？先写 redo log 后写 binlog。假设在 redo log 写完，binlog 还没有写完的时候，MySQL 进程异常重启。由于我们前面说过的，redo log 写完之后，系统即使崩溃，仍然能够把数据恢复回来，所以恢复后这一行 age 的值是 22。但是 binlog 没写完就 crash 了，这时 binlog 里面并没有记录这个语句。因此，之后备份日志的时候，存起来的 binlog 里面就没有这条语句。等到需要用这个 binlog 来恢复临时库的话，由于这个语句的 binlog 丢失，这个临时库就会少了这一次更新，恢复出来的这一行 age 值就是 22，与原库的值不同。先写 binlog 后写 redo log。如果在 binlog 写完之后 crash，由于 redo log 还没写，崩溃恢复以后这个事务无效，所以 age 的值是 22。但是 binlog 里面已经记录了 "把从 22 改成 23" 这个日志。所以，在之后用 binlog 来恢复的时候就多了一个事务出来，恢复出来的这一行 age 的值就是 23，与原库的值不同。所以，如果不使用 "两阶段提交"，数据库的状态就有可能和用 binlog 恢复出来的不一致。另外：sync_binlog 这个参数建议设置成 1，表示每次事务的 binlog 都持久化到磁盘，这样可以保证 MySQL 异常重启之后 binlog 不丢失。3.6 binlog 的应用场景主从复制 ：在 Master 端开启 binlog ，然后将 binlog 发送到各个 Slave 端， Slave 端重放 binlog 从而达到主从数据一致。数据恢复 ：通过使用 mysqlbinlog 工具来恢复数据。04 数据恢复的过程前面说过，binlog 会记录所有的逻辑操作，并且是采用 "追加写" 的形式。如果你的 DBA 承诺说一个月内可以恢复，那么备份系统中一定会保存最近一个月的所有 binlog，同时系统会定期做整库备份。这里的 "定期" 取决于系统的重要性，可以是一天一备，也可以是一周一备。当需要恢复到指定的某一秒时，比如某天下午两点发现中午十二点有一次误删表，需要找回数据，那你可以这么做：首先，找到最近的一次全量备份，如果你运气好，可能就是昨天晚上的一个备份，从这个备份恢复到临时库；然后，从备份的时间点开始，将备份的 binlog 依次取出来，重放到中午误删表之前的那个时刻。这样你的临时库就跟误删之前的线上库一样了，然后你可以把表数据从临时库取出来，按需要恢复到线上库。看到这里，小胖露出了目视父亲的笑容。巨人的肩膀《高性能 MySQL》zhihu.com/question/411272546/answer/1375199755zhihu.com/question/425750274/answer/1525436152time.geekbang.org/column/article/68633my.oschina.net/vivotech/blog/4289724hiddenpps.blog.csdn.net/article/details/10850537105 总结本文讲解了事务日志（redo og）的几个方面：为什么需要 redo log？它的写入过程、结构、存的啥以及什么是 crash-save 等等；此外还聊了 binlog 的定义、日志格式、与 redo log 的区别、update 语句的执行流程、两阶段提交、以及 binlog 的应用场景。好啦，以上就是狗哥关于 MySQL 日志的总结。感谢各技术社区大佬们的付出，如果说我看得更远，那是因为我站在你们的肩膀上。希望这篇文章对你有帮助，我们下篇文章见～
R语言数据处理120题
给大家推荐一个可以做R练习的项目，来自刘早起老师的项目，该项目包含基础20题、基本数据处理：21-50、金融数据处理：51-80、科学计算：81-100、一些补充：101-120。一共是5个部分。其中，基础题包括：1.数据创建、2.数据提取、3.数据提取、4.数据修改、5.数据统计、6.缺失值处理、7.数据提取、8.数据去重、9.数据计算、10.格式转换、11.数据保存、12.数据查看、13.提取数据、14.数据处理、15.数据提取、16.数据查看、17.数据修改、18.数据修改、19.数据排序、20.数据统计。其他详细内容可以直接点击下方网址。该项目一共涵盖了数据处理、计算、可视化等常用操作，并对部分题目给出了多种解法与注解。动手敲一遍代码一定会让你有所收获！网站中涵盖完整项目和数据集，可以直接在线上运行代码，非常方便。R语言数据处理120题https://link.zhihu.com/?target=https%3A//www.kesci.com/home/project/5f14ff3094d484002d28bbcb以下是该项目的部分截图，具体可见该网站。以后我会在科研和学习过程中，对一些最新、有趣、有用的R消息进行推送，分享。来吧，咱们一起学习数据科学，一起学习R。
快速绘制动态排序图 — Pyecharts 高级组件 Timeline 实现！
之前写过一篇关于Python 制作 动态排序图的教程，里面利用的是 Matplotlib 中的 animation 函数，文章内容可参考动态排序图的详细制作教程，动态排序图的最终部分效果如下：今天文章将用另外一种Python 软件包 Pyecharts，来实现类似效果，效果如下：在整个动态图的绘制过程，主要用到了 Pyecharts 的 Timeline 高级组件，该组件与 Matplotlib 中 animatation 函数原理相同，把数据以时间作为唯一变量，在不同时间点下其它数据条目是不一样的，一个时间点可以绘制一张可视化图表，把全部的可视化图表一帧一帧连接起来，通过帧与帧之间的数据差值变化，最终形成动态图效果而 Timeline 组件和 anaimation 函数在这里承担的角色就是 帧与帧之间可视化图表的拼接，以上原理介绍完了，接下来就来介绍一下具体怎么使用 TimelineTimeline 组件使用1，安装 Pyecharts **使用之前，请确保你已经安装好 Pyecharts ，安装方式直接利用pip 工具即可，命令如下：pip install pyechartske2，创建 Timeline 对象类先创建一个 Timeline 对象，相当于一个容器，把后面绘制的每一帧可视化报表图放在里面，然后根据放入先后顺序合成一个类似动态图的视频# 导入所需要的库函数
from pyecharts import options as opts
from pyecharts.charts import Bar,Timeline
from pyecharts.faker import Faker
import random
t1 = Timeline()# 创建 Timeline对象3，循环绘制每一帧图表，放入 Timeline利用 for 或 while 循环语句，遵守 Pyecharts 语句创建每一帧时间对应的可视化图表，然后加入了前面创建的 Timeline() 组件中，这里图表以直方图 Bar 为例for i in range(1969,2020):
attr1 = random.shuffle(list(attr))
bar = (
Bar()
.add_xaxis(random.sample(attr, len(attr)))
.add_yaxis('Data',Faker.values(),label_opts = opts.LabelOpts(position = 'right'),
)
.set_series_opts(label_opts = opts.LabelOpts(is_show = True,position = 'right'))
.reversal_axis()
.set_global_opts(title_opts = opts.TitleOpts("{}".format(i),
pos_left = '50%',
),
legend_opts = opts.LegendOpts(pos_right = '10%'))
)
t1.add(bar,'{}年'.format(i))代码解读，这里以1969-2020 作为时间段，对每一个时间节点也就是某一年创建对应的 Bar 图表，最后以t1.add(instance,str) 函数把对应时间点创建的图表加入 Timeline 组件中，为了后面更好的展示动态效果，这里把对 Bar 的坐标轴做了逆置操作(reversal_axis() ),每一帧的效果预览如下：4，美渲染化图表， html 文件另外，在 Timeline() 中 提供了函数add_schema() 用于美化组件样式，例如 时间轴方向、符号、颜色、每一帧停留时间、播放键位置、是否现实 timeline 组件、组件位置 等属性，函数使用介绍如下def add_schema(
# 坐标轴类型。可选：
# 'value': 数值轴，适用于连续数据。
# 'category': 类目轴，适用于离散的类目数据，为该类型时必须通过 data 设置类目数据。
# 'time': 时间轴，适用于连续的时序数据，与数值轴相比时间轴带有时间的格式化，在刻度计算上也有所不同，
# 例如会根据跨度的范围来决定使用月，星期，日还是小时范围的刻度。
# 'log' 对数轴。适用于对数数据。
axis_type: str = "category",
# 时间轴的类型。可选:
# 'horizontal': 水平
# 'vertical': 垂直
orient: str = "horizontal",
# timeline 标记的图形。
# ECharts 提供的标记类型包括 'circle', 'rect', 'roundRect', 'triangle', 'diamond',
# 'pin', 'arrow', 'none'
# 可以通过 'image://url' 设置为图片，其中 URL 为图片的链接，或者 dataURI。
symbol: Optional[str] = None,
# timeline 标记的大小，可以设置成诸如 10 这样单一的数字，也可以用数组分开表示宽和高，
# 例如 [20, 10] 表示标记宽为 20，高为 10。
symbol_size: Optional[Numeric] = None,
# 表示播放的速度（跳动的间隔），单位毫秒（ms）。
play_interval: Optional[Numeric] = None,
# 表示播放按钮的位置。可选值：'left'、'right'。
control_position: str = "left",
# 是否自动播放。
is_auto_play: bool = False,
# 是否循环播放。
is_loop_play: bool = True,
# 是否反向播放。
is_rewind_play: bool = False,
# 是否显示 timeline 组件。如果设置为 false，不会显示，但是功能还存在。
is_timeline_show: bool = True,
# 是否反向放置 timeline，反向则首位颠倒过来
is_inverse: bool = False,
# Timeline 组件离容器左侧的距离。
# left 的值可以是像 20 这样的具体像素值，可以是像 '20%' 这样相对于容器高宽的百分比，
# 也可以是 'left', 'center', 'right'。
# 如果 left 的值为'left', 'center', 'right'，组件会根据相应的位置自动对齐
pos_left: Optional[str] = None,
# timeline 组件离容器右侧的距离。
# right 的值可以是像 20 这样的具体像素值，可以是像 '20%' 这样相对于容器高宽的百分比。
pos_right: Optional[str] = None,
# Timeline 组件离容器上侧的距离。
# left 的值可以是像 20 这样的具体像素值，可以是像 '20%' 这样相对于容器高宽的百分比，
# 也可以是 'top', 'middle', 'bottom'。
# 如果 left 的值为 'top', 'middle', 'bottom'，组件会根据相应的位置自动对齐
pos_top: Optional[str] = None,
# timeline 组件离容器下侧的距离。
# bottom 的值可以是像 20 这样的具体像素值，可以是像 '20%' 这样相对于容器高宽的百分比。
pos_bottom: Optional[str] = "-5px",
# 时间轴区域的宽度, 影响垂直的时候时间轴的轴标签和轴之间的距离
width: Optional[str] = None,
# 时间轴区域的高度
height: Optional[str] = None,
# 时间轴的坐标轴线配置，参考 `series_options.LineStyleOpts`
linestyle_opts: Union[opts.LineStyleOpts, dict, None] = None,
# 时间轴的轴标签配置，参考 `series_options.LabelOpts`
label_opts: Optional[opts.LabelOpts] = None,
# 时间轴的图形样式，参考 `series_options.ItemStyleOpts`
itemstyle_opts: Union[opts.ItemStyleOpts, dict, None] = None,
)美化完图表之后，利用渲染命令把图表到处至本地 html 文件 t1.render( html路径)，最终效果如下(Ps ：请不要在意图表中数据的真实性，这里只是为了介绍 Timeline() 的使用方法，里面数据都是随机生成得到的)完整代码部分from pyecharts import options as opts
from pyecharts.charts import Bar,Timeline
from pyecharts.faker import Faker
import random
attr = Faker.choose()
t1 = Timeline()# 创建 Timeline对象
for i in range(1969,2020):
attr1 = random.shuffle(list(attr))
bar = (
Bar()
.add_xaxis(random.sample(attr, len(attr)))
.add_yaxis('Data',Faker.values(),label_opts = opts.LabelOpts(position = 'right'),
)
.set_series_opts(label_opts = opts.LabelOpts(is_show = True,position = 'right'))
.reversal_axis()
.set_global_opts(title_opts = opts.TitleOpts("{}".format(i),
pos_left = '50%',
),
legend_opts = opts.LegendOpts(pos_right = '10%'))
)
t1.add(bar,'{}年'.format(i))
t1.add_schema(
symbol = 'arrow',# 设置标记时间；
#orient = 'vertical',
symbol_size = 2,# 标记大小;
play_interval = 900,# 播放时间间隔；
control_position = 'right',# 控制位置;
linestyle_opts = opts.LineStyleOpts(width = 5,
type_ = 'dashed',
color = 'rgb(255,0,0,0.5)'),
label_opts = opts.LabelOpts(color = 'rgb(0,0,255,0.5)',
font_size = 15,
font_style = 'italic',
font_weight = 'bold',
font_family ='Time New Roman',
position = 'left',
interval = 20,
)
)
t1.render("D:/timeline_bar.html")Timeline 组件扩展以上通过制作 动态排序图来介绍了 Timeline 组件，本案例中图表主体类型为 Bar ，但在实际应用可以根据视觉效果、业务需求等不同应用场景把 Bar 替换为 其他图表类型，只需要把上面代码部分中的 for 循环主体代码替换即可，for i in range(1969,2020):
attr1 = random.shuffle(list(attr))
instance = ...你的图表类型
t1.add(instance,'{}年'.format(i))换一种图表类型，可能会不一样的视觉效果，例如桑葚图：圆环饼图，都有不错的动态效果，都可借助 Timeline 组件来实现好了，以上就是本篇文章的所有内容，最后感谢大家阅读！
