CODE-使用 Stack<T> + yield 取代遞迴

分享最近學到的遞迴邏輯的替代寫法。

舉個實例比較容易說明,假設公司組織樹狀結構以部門資料物件形式呈現:

    public class Dept
    {
        public string Name;
        public List<Dept> Children = new List<Dept>();
    }

組織架構範例如下:

{
  "Name": "總經理",
  "Children": [
    {
      "Name": "行政部",
      "Children": [
        { "Name": "人資組" },
        { "Name": "總務組" }
      ]
    },
    {
      "Name": "資訊部",
      "Children": [
        { "Name": "網路組" },
        { "Name": "研發組" }
      ]
 
    },
    {
      "Name": "業務部",
      "Children": [
        {
          "Name": "海外組",
          "Children": [
            { "Name": "海外一科" },
            { "Name": "海外二科" }
          ]
        },
        {
          "Name": "通路組",
          "Children": [
            { "Name": "行銷科" },
            { "Name": "電銷科" }
          ] 
        }
      ] 
    }
  ] 
}

若要列舉所有部門名稱,過去我慣用遞迴(Recursive,在函式中呼叫自己)來解,身為程式老鳥,不爬文不查書徒手寫遞迴是基本功,難不倒我:

using Newtonsoft.Json;
using System;
using System.Collections.Generic;
using System.IO;
 
namespace LinqRecursive
{
    class Program
    {
        static void Main(string[] args)
        {
            var root = JsonConvert.DeserializeObject<Dept>(File.ReadAllText("Org.json"));
            var deptNames = new List<string>();
            ExploreOrg(root, deptNames);
            Console.WriteLine(string.Join(",", deptNames.ToArray()));
            Console.Read();
        }
 
        static void ExploreOrg(Dept dept, List<string> list)
        {
            list.Add(dept.Name);
            dept.Children.ForEach(o => ExploreOrg(o, list));
        }
    }
 
    public class Dept
    {
        public string Name;
        public List<Dept> Children = new List<Dept>();
    }
 
}

執行成功:

最近再遇到相同案例,突發奇想有沒有更巧妙的做法? 爬文查得 LINQ 美技一枚 – 為 IEnumerable<T> 新增擴充方法 Traverse(),參數為可取得子物件 IEnumerable 集合的 Lambda 運算式,即可產出樹狀結構下所有節點的 IEnumerable<T> 集合繼續串接 LINQ 方法,十分巧妙:

    public static class LinqExt
    {
        //REF: https://stackoverflow.com/a/20975582/288936
        public static IEnumerable<T> Traverse<T>(this IEnumerable<T> items,
            Func<T, IEnumerable<T>> childSelector)
        {
            var stack = new Stack<T>(items);
            while (stack.Any())
            {
                var next = stack.Pop();
                yield return next;
                foreach (var child in childSelector(next))
                    stack.Push(child);
            }
        }

有了萬用 Traverse 擴充方法,不必花時間另寫遞迴函式,程式更簡潔,而傳回型別為 IEnumerable<T>,能與其他 LINQ 操作無縫接軌,極為方便。

        static void Main(string[] args)
        {
            var root = JsonConvert.DeserializeObject<Dept>(File.ReadAllText("Org.json"));
            Console.WriteLine(string.Join(",", 
                new List<Dept>() { root }
                .Traverse<Dept>(o => o.Children)
                .Select(o => o.Name).ToArray()));
            Console.Read();
        }

回頭看 Traverse 方法,利用 Stack<T> 資料結構,一方面取得子元素集合推入 Stack<T>,另一方面則從 Stack<T> 取出元素查詢其子元素,堆與取之間把所有元素都巡過一輪。還有一個巧妙處在於 yield,可以無腦地在迴圈裡遇到條件符合就 return 結果,交由 .NET 在背後蒐集結果彙整成 IEnumerable<T>。若不用 yield 也可以,替代做法是準備一個 List<T> 蒐集結果最後再傳回,像這個樣子:

        public static IEnumerable<T> Traverse<T>(this IEnumerable<T> items,
            Func<T, IEnumerable<T>> childSelector)
        {
            var stack = new Stack<T>(items);
            var results = new List<T>();
            while (stack.Any())
            {
                var next = stack.Pop();
                results.Add(next);
                foreach (var child in childSelector(next))
                    stack.Push(child);
            }
            return results;
        }

由此可見 yield 簡化邏輯的效果,收入工具箱,未來遇類似情境多了新武器可用。對 yield 的原理有興趣深入了解的同學,推薦安德魯的系列文:

歡迎推文分享:
Published 12 December 2017 08:32 AM 由 Jeffrey
Filed under:
Views: 7,284



意見

# Jackson Lin said on 07 January, 2018 07:25 AM

感謝大大分享如此實用的方法!

小弟這邊觀察到,Stack的部分因為push是由頂部加入

所以擴充方法那邊while迴圈裡應該要把Stack反轉

如此才能保持輸出順序是由上到下,和遞迴法輸出相同

你的看法呢?

(必要的) 
(必要的) 
(選擇性的)
(必要的) 
(提醒: 因快取機制,您的留言幾分鐘後才會顯示在網站,請耐心稍候)

5 + 3 =

搜尋

Go

<December 2017>
SunMonTueWedThuFriSat
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456
 
RSS
創用 CC 授權條款
【廣告】
twMVC

Tags 分類檢視
關於作者

一個醉心技術又酷愛分享的Coding魔人,十年的IT職場生涯,寫過系統、管過專案, 也帶過團隊,最後還是無怨無悔地選擇了技術鑽研這條路,近年來則以做一個"有為的中年人"自許。

文章典藏
其他功能

這個部落格


Syndication