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发送的消息'},
  ...
]

效果展示

JS前端千万级弹幕数据循环优化示例_第1张图片

小结

上面优化策略只有两条

发送过的消息删除,下次少循环。

当找到满足条件的数据,直接跳出循环,后面的数据不再循环。

缺点:使用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前端数据循环优化的资料请关注脚本之家其它相关文章!

你可能感兴趣的