記一次生產問題的排查，讓我領略了算法的重要性

前段時間，客戶反饋，有個PC端的功能頁面，一點開就卡死，通過查看網絡請求，發現有個部門組織架構樹的請求數據有點大，共有兩萬條數據,1.57M。剛開始我以為是表單中的部門選擇框渲染的時候，一次性渲染的dom節點過多，把頁面內存撐爆了。於是我把項目中使用的antd3的TreeSelect組件，升級到具有無限滾動加載功能的antd5版本，始終只渲染10條數據，按理說頁面卡死的問題應該就消失了。結果頁面操作幾次之後，頁面仍舊百分之百會崩掉， 頁面卡死問題並未徹底解決。

於是我沉下心來，把出問題的頁面的邏輯從頭到尾看了一遍，發現有一處採用遞歸方式查找某個部門id在不在部門樹之中的邏輯，可能存在性能問題。沒優化之前的寫法是這樣的：

const findTreeItem = (data, id) => {
  for (let i = 0,len=data.length; i < len; i++) {
    let item = data[i];
    if (item.id === id) {
      return true;
    } else {
      if (item.children) {
        if (findTreeItem(item.children, id)) {
          return true;
        }
      }
    }
  }
};
const isInclude = findTreeItem(treeData,deptId);

這種寫法的缺點是，當樹的層級很深時，可能會引起暴棧。讓我們分析一下這種遞歸算法的空間複雜度。假設要判斷id="1-1-1-0"是否存在於treeData中

const treeData = [
  {
    id: "0",
    children: [
      {
        id: "1-0",
        children: [
          {
            id: "1-0-0",
            children: [
              {
                id: "1-0-0-0",
              },
              {
                id: "1-0-0-1",
              },
              {
                id: "1-0-0-2",
              },
              {
                id: "1-0-0-3",
              },
            ],
          },
          {
            id: "1-0-1",
          },
          {
            id: "1-0-2",
          },
        ],
      },
      { id: "1-1" },
    ],
  },
];

我們想知道，在遞歸調用的過程中，最大的內存占用量。那就要對遞歸調用進行拆解，每一次遞歸函數調用自己，會占用多少內存空間，從方法 findTreeItem(treeData,'1-1-1-0') 調用方法 findTreeItem(treeData[0].children,'1-1-1-0') 時，將創findTreeItem(treeData[0].children,'1-1-1-0') 相對應的堆棧幀。

該堆棧幀將保留在內存中，直到函數對findTreeItem(treeData[0].children,'1-1-1-0') 的調用終止。該堆棧幀負責保存函數findTreeItem(treeData[0].children,'1-1-1-0') 的參數，函數findTreeItem(treeData[0].children,'1-1-1-0') 中的局部變量以及調用方函數findTreeItem(treeData,'1-1-1-0')的返回地址。

接著，當此函數 findTreeItem(treeData[0].children,'1-1-1-0') 調用函數 findTreeItem(treeData[0].children[0].children,'1-1-1-0') 時，也會生成findTreeItem(treeData[0].children[0].children,'1-1-1-0') 相對應的堆棧幀，並將其保留在內存中，直到對findTreeItem(treeData[0].children[0].children,'1-1-1-0') 的調用終止。調用 findTreeItem(treeData[0].children[0].children,'1-1-1-0') 時，堆棧框架的調用堆棧如下所示：

當調用到 findTreeItem(treeData[0].children[0].children[0].children,'1-1-1-0') ，執行完畢，返回對函數 findTreeItem(treeData[0].children[0].children,'1-1-1-0') 的調用時，由於不再需要findTreeItem(treeData[0].children[0].children,'1-1-1-0') 相對應的堆棧幀，js引擎將從內存中刪除該堆棧幀。函數 findTreeItem(treeData[0].children,'1-1-1-0')和函數 findTreeItem(treeData,'1-1-1-0') 的堆棧幀也是如此。

　　通過分析可以看出遞歸算法的空間複雜度與所生成的最大遞歸樹的深度成正比。如果遞歸算法的每個函數調用都占用 O(m) 空間，並且遞歸樹的最大深度為 n，則遞歸算法的空間複雜度將為 O(n·m)。

從performance屬性可以知道，一個頁面可以使用的內存量級是30M左右，假如2萬多條數據占用1.5M左右內存空間，最理想的情況下，能支撐的遞歸深度也就20級左右，實際上要減去存儲代碼占用的空間，存儲基本類型數據和引用類型引用地址，存儲引用類型占用的空間，三下五除二，留給遞歸方法使用的空間就所剩無幾了。無怪乎會造成頁面卡死。

於是對上面的查找方法進行了一番優化，將深度遍歷優先改成廣度遍歷優先，頁面出現卡死的問題徹底解決。

findTreeItem(tree, curKey, keyField, childField, node = null) {
  const stack = [];
  for (const item of tree) {
    if (item) {
      stack.push(item);
      while (stack.length) {
        // 重點是這裡--邊查找邊釋放內存空間
        const temp = stack.pop();

        if (temp[keyField] === curKey) {
          node = temp;
          break;
        }

        const children = temp[childField] || [];
        for (let i = children.length - 1; i >= 0; i--) {
          stack.push(children[i]);
        }
      }
    }
  }
  return node;
}

當數據量比較小的時候，好的算法與差的算法，沒有致命的差別。當數據量比較大的時候，算法的優劣，有天壤之別。所以平日在寫數據處理邏輯的時候，要對數據處理的算法，保持一定的敏感度。之前對好的算法的優勢，僅僅停留在概念和理論上，實際感受不太深切。就好比讀了好多書，卻依然過不好這一生。以為對書中的道理，看過一遍，知道了就等於懂了。實際上真正要用到的時候，大概率想不起來。因為沒有特別深刻的感性認知。這次遭遇到生產問題的毒打之後，讓我感受到了好的算法與壞的算法，質的差別，算法還是要重視起來。

來源：https://www.cnblogs.com/wangpenghui522/p/16218816.html