大家好，我是wacky，最近在工作中遇到一個有趣的問題，同事反饋說WPF中有一個樹形結構的集合，在加載時會直接報堆棧溢出，一直沒時間(懶得)看，導致很久了也沒人解決掉。于是，組長就把這個"艱巨"的任務交給了我。作為新人中的"高手"，必然要義不容辭地接受挑戰(zhàn)嘍，廢話不多說，走起。
分析由于同事此前已經定位到出現問題的代碼段，所以到我手中時要省掉不少功夫。打開代碼后看了下，原來是這個樹形結構使用了典型的遞歸操作來對每個節(jié)點的數據進行更新，在數據量一般時一切正常，但是當數據量達到幾萬個節(jié)點后，這段代碼會直接報堆棧溢出的錯誤。
代碼示例如下所示，已簡化：
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 // 創(chuàng)建一個樹形結構 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); } } }
上述代碼我們定義了一個樹形結構的類，并加入對應節(jié)點，然后使用遞歸的方式將所有節(jié)點輸出，在數據量達到前文提到的數量級時就會發(fā)生堆棧溢出。
?既然是堆棧溢出，那么我們就需要考慮減少堆棧溢出的方式，也就是降低棧的深度。這里我們需要分析下為什么遞歸會導致堆棧溢出？順便復習一下部分計算機基礎知識點。
?在計算機中，函數調用是通過棧(stack)這種數據結構去實現的，每當程序在調用一次函數時，就會進行壓棧(push)，每當函數返回后，才會進行出棧(pop)。但是棧的大小本身并不是無限的，加上我們使用C# CLR給的默認分配也不會很大，通常是在1MB左右，這樣就會出現函數調用次數過多時，超出棧本身的大小，導致堆棧溢出。
而遞歸調用，一般都是在到達最后的結束點時，才會一層一層返回每個函數執(zhí)行的結果。在本次例子中，樹形結構存在幾萬個父子節(jié)點，就會導致遞歸層數過深，函數在棧中無法及時出棧，進而報錯。
?到這一步時，我們的思路就開始明朗了，既然遞歸會導致堆棧過深，那我們不妨把遞歸進行改寫，使用其他方式來進行遍歷。在通常的解法中，存在兩種方式：尾遞歸優(yōu)化和迭代。
尾遞歸優(yōu)化
什么是尾遞歸優(yōu)化？我們先說說什么是尾遞歸，尾遞歸是指在一個函數中，所有遞歸的調用都出現在函數的末尾，也就是遞歸的那一句在函數執(zhí)行的最后，或代碼路徑在最后一句出現，我們就可以稱之為尾遞歸。所以如果我們的遞歸調用本身不是尾遞歸的時候，可以通過改寫，讓它變成尾遞歸的方式。
?為什么尾遞歸可以進行優(yōu)化？原因是堆棧需要保存每次調用的返回地址及當時所有的局部變量狀態(tài)，期間堆?？臻g是無法釋放的。使用尾遞歸堆?？梢圆挥帽４嫔洗蔚暮瘮捣祷氐刂?各種狀態(tài)值，而方法遺留在堆棧上的數據完全可以釋放掉，這是尾遞歸優(yōu)化的核心思想。
回到我們本次的例子中來，我們的代碼已經是尾遞歸的形式了，但還會導致溢出，那這時我們就需要使用另外一種方法迭代去解決問題了。
迭代
迭代，在本質上就是循環(huán)，由于我們已經提到了遞歸在函數調用的過程中不會對棧進行彈出，那么我們就可以用迭代來模擬入棧出棧的方式來對遍歷做優(yōu)化。我們可以先定義一個棧用來存放所有父子節(jié)點，然后對父節(jié)點進行壓棧，并使用while循環(huán)來模擬所有遍歷操作，當棧不為空時就一直執(zhí)行。在循環(huán)中我們可以對已經壓棧的數據進行彈棧，做完邏輯操作后，再對其子節(jié)點進行壓棧，一直重復此過程，直到所有節(jié)點都彈棧完成。
相關代碼如下所示：
// See https://aka.ms/new-console-template for more information // 創(chuàng)建一個樹形結構 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; } //定義一個棧，存放所有的樹節(jié)點 Stack<TreeNode> stack = new Stack<TreeNode>(); //把根節(jié)點壓棧 stack.Push(root); while (stack.Count > 0) { TreeNode node = stack.Pop(); Console.WriteLine(node.Value); //遍歷完父節(jié)點后，將子節(jié)點壓棧 for (int i = node.Children.Count - 1; i >= 0; i--) { stack.Push(node.Children[i]); } } } }
在這種方式中，我們每遍歷一層節(jié)點，都會對棧進行釋放，這樣就保證了已經在棧中的層級不會太深，進而解決了堆棧溢出的問題。
總結
探尋好思路后，我和同事做了嘗試，將代碼改寫完成后，遍歷幾萬個節(jié)點一切正常，且不會出現卡死之類的其他問題，完美解決！雖然我們本次性能優(yōu)化的思路并不復雜，代碼寫起來也相對簡單，但背后其實蘊含著比較深刻的計算機原理知識。我們在日常工作中也需要多重視基礎知識，包括數據結構和算法，這樣才可以在遇到難以解決的問題時游刃有余，諸君共勉！
?文章來源地址http://www.zghlxwxcb.cn/news/detail-631183.html
本文首發(fā)于我的公眾號【wacky的碎碎念】，喜歡的話可以微信掃碼關注喲，我們一起來聊聊技術，談談職場和人生~
文章來源：http://www.zghlxwxcb.cn/news/detail-631183.html
?
到了這里，關于C#性能優(yōu)化-樹形結構遞歸優(yōu)化的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
