yocto queue微型佇列資料結構原始碼解讀

2022-12-29 14:01:30

引言

yocto-queue是一個微型佇列的資料結構，根據作者的介紹，如果在你一個資料量很大的陣列上，大量的操作Array.push和Array.shift，那麼你可以考慮使用yocto-queue來替代Array。

因為Array.shift的時間複雜度是O(n)，而Queue.dequeue的時間複雜度是O(1)，這對於大量的資料來說，效能上的提升是非常明顯的。

時間複雜度和空間複雜度

學習演演算法和資料結構的時候，我們經常會聽到時間複雜度和空間複雜度，這兩個概念是什麼呢？

時間複雜度

時間複雜度是指一個演演算法執行所耗費的時間，它是一個函數，這個函數的變數是問題規模的函數；

通常會使用大O符號來表示時間複雜度，比如O(n)，O(n^2)，O(logn)等等，這就是大 O 表示法（Big O notation）。

O代表的是演演算法的漸進時間複雜度（asymptotic time complexity），也就是說，隨著問題規模的增大，演演算法的執行時間的增長率和O中的函數相同，稱作漸進時間複雜度。

O(1)表示演演算法的執行時間與問題規模無關，也就是說，不管問題規模有多大，演演算法執行所耗費的時間都是一樣的，這種演演算法稱為時間複雜度為常數階的演演算法。

O(n)表示演演算法的執行時間與問題規模成正比，也就是說，隨著問題規模的增大，演演算法執行所耗費的時間也隨之增大，這種演演算法稱為時間複雜度為線性階的演演算法。

O(n^2)表示演演算法的執行時間與問題規模成平方比，也就是說，隨著問題規模的增大，演演算法執行所耗費的時間呈二次方增長，這種演演算法稱為時間複雜度為平方階的演演算法。

通過上面的介紹，我們可以將O比喻成函數，O(1)就是一個常數函數，O(n)就是一個線性函數，O(n^2)就是一個平方函數，O(logn)就是一個對數函數。

說了這麼多概念性的問題，不如直接來看看程式碼；

例如，我們有一個陣列，我們要遍歷這個陣列，然後將陣列中的每個元素都乘以2，那麼我們可以這麼寫：

function multiplyBy2(arr) {
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    result.push(arr[i] * 2);
  }
  return result;
}

這段程式碼的時間複雜度是O(n)，因為我們遍歷了陣列，所以時間複雜度就是O(n)，O代表這個函數，n代表問題規模，也就是陣列的長度，組合起來就是O(n)。

再直觀一點，我們可以這麼理解，當陣列的長度為n時，我們需要執行n次迴圈，所以時間複雜度就是O(n)，用程式碼錶示就是：

function O(n) {
    for (let i = 0; i < n; i++) {
        // do something
    }
}
O(1); // O(1)
O(2); // O(2)
O(3); // O(3)
O(n); // O(n)

空間複雜度

空間複雜度是指一個演演算法執行所耗費的記憶體空間，它是一個函數，這個函數的變數是問題規模的函數；

和時間複雜度一樣，空間複雜度也有O(1)、O(n)、O(n^2)、O(logn)等等，它們的含義和時間複雜度一樣，只不過它們是表示演演算法執行所耗費的記憶體空間的增長率。

當然空間複雜度計算的不是記憶體消耗，而是變數的個數，例如氣泡排序的空間複雜度是O(1)，因為它只需要一個變數temp：

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

而快速排序的空間複雜度是O(logn)，因為它需要一個變數pivot，而且它是遞迴的，所以空間複雜度是O(logn)：

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const pivotIndex = Math.floor(arr.length / 2);
  const pivot = arr.splice(pivotIndex, 1)[0];
  const left = [];
  const right = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

原始碼分析

上面瞭解了時間複雜度和空間複雜度的概念，那麼我們開始正式分析yocto-queue的原始碼；

程式碼不多，可以直接通過github1s線上閱讀，然後使用瀏覽器控制檯來檢視效果；

程式碼分析

先來看一下yocto-queue的使用方式：

安裝

npm install yocto-queue

使用

import Queue from 'yocto-queue';
const queue = new Queue();
queue.enqueue('