2

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

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

    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 的原理有興趣深入了解的同學，推薦安德魯的系列文:


Comments

# by Jackson Lin

感謝大大分享如此實用的方法! 小弟這邊觀察到，Stack的部分因為push是由頂部加入 所以擴充方法那邊while迴圈裡應該要把Stack反轉 如此才能保持輸出順序是由上到下，和遞迴法輸出相同

# by 凱大

我一值想不透的是 為何在 new Stack<T>之後可以破壞iterator 的rule (也就是改變seq 本身的長度) 後來查到 stack 的 constructor 會將當下的結果產出 也就是說 stack 會做類似ToList 這樣的行為 所以 在與其他Linq Operator 串接的時候要注意此處會有一份cache 這與 SelectMany 之類的Operator 在 延遲執行上的狀況並不相同 ex: SelectMany 可能可以通過自身無法負荷的資料量SelectMany順利執行 但是這個方法在上述的情況可能會發生OutOfMemoryException ------------------------------------------------------------------------------------ 如果是這樣的話 SelectMany 我覺得就可以取代這個方法 缺少的部分是帶入的input element 這裡可以用 Prepend (after .net core 2.0), 或是乾脆自己寫一個 public static IEnumerable<T> Traverse<T>( this IEnumerable<T> seq, Func<T,IEnumerable<T>> selector) { yield return t; var enumerator = seq.GetEnumerator(); while (enumerator.MoveNext()) { var resultSeq = selector(enumerator.Current).GetEnumerator(); while(resultSeq.MoveNext()) { yield return resultSeq.Current; } } }

Post a comment