JS前端千萬級彈幕資料迴圈優化範例

2022-07-14 22:01:54

引言

最近做了直播相關的業務，然後對於巨量資料相關的優化做了一下覆盤。

為了瞭解我是怎麼做這個優化的，我們先從如何按照特定的條件刪除一個陣列說起。

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前端資料迴圈優化的資料請關注it145.com其它相關文章！