引言
最近做了直播相关的业务,然后对于大数据相关的优化做了一下复盘。
为了了解我是怎么做这个优化的,我们先从如何按照特定的条件删除一个数组说起。
1、如何删除数组中的元素
场景:有一个数组,需要删除满足条件的数组。
示例:
const arr = [1,2,3,4,5,6,7,8]
删除小于5的元素,删除后的元素为
const arr2 = [5, 6, 7, 8]
代码实现:
const arr = [1,2,3,4,5,6,7,8] for(let i = 0, len = arr.length; i < len; i++) { if(arr[i] < 5) { arr.splice(i, 1) } }
结果如下
arr = [2, 4, 5, 6, 7, 8
不是我们预期的结果
分析原因:删除操作会使得对应索引值位上的元素清空,整个数组中的元素向前移动一位,补位的元素会填充到执行删除操作的索引值位置上,移位之后如果不进行任何操作继续下一个循环,会导致补位元素跳过遍历,为了防止这种补位元素跳过遍历现象,应该在删除操作后将索引值减1,对执行删除操作的索引值位置再进行一次遍历 。
改进:
const arr = [1,2,3,4,5,6,7,8] for(let i = 0, len = arr.length; i < len; i++) { if(arr[i] < 5) { arr.splice(i, 1) i--; } } // arr = [5, 6, 7, 8] 符合预期
这个是做了正序循环删除,也可以使用倒序循环删除:
const arr = [1,2,3,4,5,6,7,8] for(let i = arr.length - 1; i >= 0; i--) { if(arr[i] < 5) { arr.splice(i, 1) } } // arr = [5, 6, 7, 8] 符合预期
2、10000,000条消息如何优化?
场景
弹幕消息发送场景模拟(伪直播形式,没有进度条):假设我们有10000,000条消息,根据视频播放的进度展示对应的消息,不展示历史消息。
常规思路:
循环遍历整个消息列表,时刻监听视频播放的进度,根据视频播放的时间戳和消息发送的时间戳先相等,然后展示消息,依次循环。
产生的问题
每次视频进度变化都会循环整个消息列表,当循环还没完成,下一个播放进度监听触发了,又开始下一个循环,这样就会造成性能的损耗。
优化策略
我们从上面的分析可以看出,当消息发送了一条,就可以从原始数据删除这条消息,然后跳出循环,这样循环的次数始终控制在几次(或者几十次)的范围(有可能同一个时间段同时有几条消息甚至几十条消息)等下一个播放进度监听触发,开始循环原始数据,这是之前以后发送过得数据删除了,就不会再循环删除过的数据,始终循环需要发送的那几条,找到了就直接跳出循环。
代码实现
// 模拟原始消息列表, const newList = new Array(10000000).fill(1).map((item, index) => { return { time: (index + 1) * 1000, // 消息发送的时间,一秒一个 content: `这是第${index + 1}s发送的消息` // 消息发送的内容 } }) // 发送的消息列表 const sendList = []; function getMessage(time) { let j = 0; // 循环次数 for(let i = 0, len = newList.length; i < len; i++) { const item = newList[i]; j++; // 这里的time如果不是1000、2000,而是1234、1214这种,就需要取一个浮动范围 // 我这里就是简单用了定时器,所以比较简单 if(item.time === time) { sendList.push(newList[i]) newList.splice(i, 1) i--; } else if(sendList.length > 0) { break; } } console.log('播放进度', time) console.log('循环的次数', j); console.log('接收的消息的长度', sendList.length, sendList); console.log('原始消息的长度', newList.length); } let time = 0; // 定时器,1s触发一次 setInterval(() => { time += 1000; getMessage(time); }, 1000)
// 消息格式 newList = [ {time: 1000, content: '这是第1s发送的消息'}, {time: 2000, content: '这是第2s发送的消息'}, ... ]
效果展示
小结
上面优化策略只有两条
发送过的消息删除,下次少循环。
当找到满足条件的数据,直接跳出循环,后面的数据不再循环。
缺点:使用slice也会消耗性能,不可取,并且操作繁琐。
游标法代替splice
我们这里不再使用slice的方案,设置一个游标,记录循环的初始位置,下次循环直接从游标记录的位置开始循环,然后满足查找的条件就break,这样既不破坏原来的数组,也能有效的减少循环的次数。
let index = 0, sendList =[]; function getMessage(time) { for(let i = 0, len = newList.length; i < len; i++) { const item = newList[i]; // 这里的time如果不是1000、2000,而是1234、1214这种,就需要取一个浮动范围 // 我这里就是简单用了定时器,所以比较简单 if(item.time === time) { index = i; sendList.push(newList[i]) } else if(sendList.length > 0) { // 这里的查询结束条件为,对应的时间范围之外没有消息了,并且需要发送的消息列表有消息,才break // 这里的结束条件想不到什么更好的方案了 break; } } }
上面我们只对视频播放的时候做了优化,如果下次用户进来进度直接接近尾声了,这时候首次查找尾部消息的时候,就需要把前面所有的消息都循环一遍,所以还需要继续优化。
二分查找
当首次加载的时候,采用二分法查找到消息开始的位置,当视频播放的时候再根据查找到的index去循环消息体。
function binarySearch(arr, time) { let upperBound = arr.length - 1; // 记录长度 let lowerBound = 0; // 记录上次二分的位置 let mid; // 切半分的位置 小于或等于 1就停止循环了 while (lowerBound <= upperBound) { // (当前总长度 + 当前中间点位置长度) / 2 = 实际的中间点位置 mid = Math.floor((upperBound + lowerBound) / 2); const item = arr[mid]; const maxTime = time + 500; const minTime = time + 500; // 当输入的值大于中间值时,向后移动一位 if (time > maxTime) { lowerBound = mid + 1; } else if (time < minTime) { // 当输入值小于中间值时,向前移动一位 upperBound = mid - 1; } else { return mid; // 找到指定数据位置 } } return -1; }
function findIndex(startPlayTime: number) { const searchIndex = binarySearch(this.messageList, time); // 赋值索引,用于快速发送消息 if (searchIndex !== -1) { index = searchIndex; } }
完结
写到这里本篇文章就不再会更新了,从最开始的splice方法,然后到后面的游标法和二分法,做了逐渐的优化。
这个也是在项目中每次迭代去做的优化(前提是给你的排期你能有时间去做)。本文涉及的知识点可能并不是很重要,在这里我要跟大家说的是,我们平时在写代码的时候,要善于发现代码的可优化空间,如果你发现了并且实事求是的去做了,你的能力就会有更大的提高,而且这个发现的过程你可以找同事,找leader去给你review代码,在业务中沉淀出来的代码比你自己平时写个小demo写的代码更能让你成长。
更多关于JS前端数据循环优化的资料请关注阿兔在线工具其它相关文章!