C#性能優化-樹形結構遞歸優化

前言大家好，我是wacky，最近在工作中遇到一個有趣的問題，同事反饋說WPF中有一個樹形結構的集合，在載入時會直接報堆棧溢出，一直沒時間(懶得)看，導致很久了也沒人解決掉。於是，組長就把這個"艱巨"的任務交給了我。作為新人中的"高手"，必然要義不容辭地接受挑戰嘍，廢話不多說，走起。分析由於同事 ...

前言

大家好，我是wacky，最近在工作中遇到一個有趣的問題，同事反饋說WPF中有一個樹形結構的集合，在載入時會直接報堆棧溢出，一直沒時間(懶得)看，導致很久了也沒人解決掉。於是，組長就把這個"艱巨"的任務交給了我。作為新人中的"高手"，必然要義不容辭地接受挑戰嘍，廢話不多說，走起。

分析

由於同事此前已經定位到出現問題的代碼段，所以到我手中時要省掉不少功夫。打開代碼後看了下，原來是這個樹形結構使用了典型的遞歸操作來對每個節點的數據進行更新，在數據量一般時一切正常，但是當數據量達到幾萬個節點後，這段代碼會直接報堆棧溢出的錯誤。

代碼示例如下所示，已簡化：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Tree
{
    internal class TreeNode
    {
        public int Value { get; set; }
        public List<TreeNode> Children { get; set; }   

        public TreeNode(int value)
        {
            Value = value;
            Children = new List<TreeNode>();
        }
    }
}

// See https://aka.ms/new-console-template for more information
// 創建一個樹形結構
using Tree;

internal class Program
{
    static void Main(string[] args)
    {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);

        root.Children.Add(node2);
        root.Children.Add(node3);
        node2.Children.Add(node4);
        node2.Children.Add(node5);
        node3.Children.Add(node6);

        PrintTreeNode(root);
        Console.Read();
    }

    static void PrintTreeNode(TreeNode node)
    {
        if (node == null)
        {
            return;
        }
        Console.WriteLine(node.Value);
        foreach (TreeNode child in node.Children)
        {
            PrintTreeNode(child);
        }
    }
}

上述代碼我們定義了一個樹形結構的類，並加入對應節點，然後使用遞歸的方式將所有節點輸出，在數據量達到前文提到的數量級時就會發生堆棧溢出。

既然是堆棧溢出，那麼我們就需要考慮減少堆棧溢出的方式，也就是降低棧的深度。這裡我們需要分析下為什麼遞歸會導致堆棧溢出？順便複習一下部分電腦基礎知識點。

在電腦中，函數調用是通過棧(stack)這種數據結構去實現的，每當程式在調用一次函數時，就會進行壓棧(push)，每當函數返回後，才會進行出棧(pop)。但是棧的大小本身並不是無限的，加上我們使用C# CLR給的預設分配也不會很大，通常是在1MB左右，這樣就會出現函數調用次數過多時，超出棧本身的大小，導致堆棧溢出。

而遞歸調用，一般都是在到達最後的結束點時，才會一層一層返回每個函數執行的結果。在本次例子中，樹形結構存在幾萬個父子節點，就會導致遞歸層數過深，函數在棧中無法及時出棧，進而報錯。

到這一步時，我們的思路就開始明朗了，既然遞歸會導致堆棧過深，那我們不妨把遞歸進行改寫，使用其他方式來進行遍歷。在通常的解法中，存在兩種方式：尾遞歸優化和迭代。

尾遞歸優化

什麼是尾遞歸優化？我們先說說什麼是尾遞歸，尾遞歸是指在一個函數中，所有遞歸的調用都出現在函數的末尾，也就是遞歸的那一句在函數執行的最後，或代碼路徑在最後一句出現，我們就可以稱之為尾遞歸。所以如果我們的遞歸調用本身不是尾遞歸的時候，可以通過改寫，讓它變成尾遞歸的方式。

為什麼尾遞歸可以進行優化？原因是堆棧需要保存每次調用的返回地址及當時所有的局部變數狀態，期間堆棧空間是無法釋放的。使用尾遞歸堆棧可以不用保存上次的函數返回地址/各種狀態值，而方法遺留在堆棧上的數據完全可以釋放掉，這是尾遞歸優化的核心思想。

回到我們本次的例子中來，我們的代碼已經是尾遞歸的形式了，但還會導致溢出，那這時我們就需要使用另外一種方法迭代去解決問題了。

迭代

迭代，在本質上就是迴圈，由於我們已經提到了遞歸在函數調用的過程中不會對棧進行彈出，那麼我們就可以用迭代來模擬入棧出棧的方式來對遍歷做優化。我們可以先定義一個棧用來存放所有父子節點，然後對父節點進行壓棧，並使用while迴圈來模擬所有遍歷操作，當棧不為空時就一直執行。在迴圈中我們可以對已經壓棧的數據進行彈棧，做完邏輯操作後，再對其子節點進行壓棧，一直重覆此過程，直到所有節點都彈棧完成。

相關代碼如下所示：

// See https://aka.ms/new-console-template for more information
// 創建一個樹形結構
using Tree;

internal class Program
{
    static void Main(string[] args)
    {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);

        root.Children.Add(node2);
        root.Children.Add(node3);
        node2.Children.Add(node4);
        node2.Children.Add(node5);
        node3.Children.Add(node6);

        IterativeTraversal(root);
        Console.Read();
    }

    static void IterativeTraversal(TreeNode root)
    {
        if (root == null)
        {
            return;
        }
        //定義一個棧，存放所有的樹節點
        Stack<TreeNode> stack = new Stack<TreeNode>();
        //把根節點壓棧
        stack.Push(root);
        while (stack.Count > 0)
        {
            TreeNode node = stack.Pop();
            Console.WriteLine(node.Value);
            //遍歷完父節點後，將子節點壓棧
            for (int i = node.Children.Count - 1; i >= 0; i--)
            {
                stack.Push(node.Children[i]);
            }
        }
    }
}

在這種方式中，我們每遍歷一層節點，都會對棧進行釋放，這樣就保證了已經在棧中的層級不會太深，進而解決了堆棧溢出的問題。

總結

探尋好思路後，我和同事做了嘗試，將代碼改寫完成後，遍歷幾萬個節點一切正常，且不會出現卡死之類的其他問題，完美解決！雖然我們本次性能優化的思路並不複雜，代碼寫起來也相對簡單，但背後其實蘊含著比較深刻的電腦原理知識。我們在日常工作中也需要多重視基礎知識，包括數據結構和演算法，這樣才可以在遇到難以解決的問題時游刃有餘，諸君共勉！

本文首發於我的公眾號【wacky的碎碎念】，喜歡的話可以微信掃碼關註喲，我們一起來聊聊技術，談談職場和人生~