JS前端千万级弹幕数据循环优化示例

      大数据中时常都会有优化，这篇文章要和大家降的就是如何按照特定的条件删除一个数组？

　　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方法，然后到后面的游标法和二分法，做了逐渐的优化。

　　上述内容对于大家知识上可能不是非常重要，上面讲的也是我们平时在写代码的时候，在日常写代码中也是在不断的优化，也是一种negligible的提升，。例如，找leader去给你review代码，就是让我们在日常的工作业务中去不断的提升自己的能力，让自己成长。