安德魯的部落格

該如何學好 "寫程式" #2. 為什麼 programmer 該學資料結構 ??

Summary 查看原始文章

該如何學好 “寫程式” #2. 為什麼 programmer 該學資料結構 ??

摘要提示

  • 內功與工具: 成為合格 programmer 的關鍵在於資料結構與演算法等「內功」，而非只熟悉語言與框架。
  • 基本功檢核: 透過排序、搜尋、路徑規劃等題目檢視把概念轉為可執行程式碼的能力。
  • 資料結構選型: 面對百萬級資料搜尋，選對集合型別比單純精通語法更重要。
  • List 的侷限: List<T> 搜尋為 O(n)，在資料量擴張時效能迅速惡化。
  • Dictionary 的優缺: Dictionary<TKey,TValue> 憑雜湊達成近 O(1) 的精確查找，但不適合排序與範圍查找。
  • 時間複雜度觀念: 透過 MSDN 文件的 time complexity 註記，可正確評估演算法與結構的伸縮性。
  • 排序+二分搜尋: 「先排序、後 Binary Search」是滿足多種索引與區間查詢的標準解。
  • Sorted 結構選擇: SortedList/SortedDictionary 皆可排序儲存，依情境選取以取得最佳讀寫平衡。
  • 實測差異: 百萬筆資料下，SortedList 搜尋可比 List 快 ~80 倍；放大一百倍資料差異達近 6000 倍。
  • 學用接軌: 把學校的資料結構知識（HashTable、Binary Search、複雜度）與 MSDN 文件結合，才能寫出可擴充的程式。

全文重點

作者延續「如何學好寫程式」系列，強調合格的 programmer 必須具備將規格落實為穩定高效程式碼的能力，而真正的關鍵在於資料結構與演算法等基礎「內功」，而非只追逐新技術。文中以通訊錄的百萬筆資料搜尋為主題，示範不同 .NET 集合在效能與可用性上的差異，以及如何運用 MSDN 的時間複雜度說明做出正確選擇。

作者先以三個基本功檢核說明實作力的重要：能把排序概念寫成實碼；能在記憶體中快速搜尋百萬筆通訊錄；能用程式找出高速公路兩點之間的建議路徑。接著以 C# 範例實測：多數人直覺使用 List<ContactData> 再用 Find/FindAll 搜尋，但這是 O(n) 線性掃描，資料倍增時耗時亦線性放大。進階者會加上 Dictionary<string,ContactData> 作姓名索引，精確查找可達近 O(1)，但無法滿足排序與前綴/區間搜尋需求。

作者引導讀者回到資料結構的核心：先理解時間複雜度（如 O(1)、O(n)、O(log n) 等），再從 MSDN 的 Collections 文件找出合適結構。Dictionary 基於雜湊表，擅長精確比對；若要同時滿足排序與範圍查詢，標準作法是「依多個欄位分別排序，配合二分搜尋」。.NET 中可選 SortedList 或 SortedDictionary；作者依需求選用 SortedList 建立 name 與 phone 兩組排序索引，插入時完成排序，搜尋時以 Binary Search 鎖定範圍，達成前綴查找。

實測顯示：在百萬筆資料下，List 搜尋耗時為 O(n)，SortedList 則為 O(log n)，兩者差距約 80 倍；若擴大至一億筆，差距可達近 6000 倍，顯示演算法與資料結構的選擇遠比微幅最佳化更關鍵。文章最後強調：學校的資料結構並非無用，反而是把框架文件（如 MSDN）讀懂、用對的基礎。作者鼓勵讀者養成以複雜度思考、以結構選型的習慣，並預告後續系列內容。

段落重點

寫程式的「內功」是什麼：從實作到穩定高效

作者回應前文迴響，指出合格的 programmer 不只是能把規格寫成可執行程式，更要能寫得「又快又好」，即在正確性、穩定性與效能間取得平衡。這些能力的核心不在於新潮技術，而是資料結構與演算法。常見錯誤如迴圈層次擺錯、重複計算等，源自基本功不足與邏輯觀念薄弱。為了界定「基本功」，作者提出三題：能把排序方法如 Bubble/Quick 轉成實作；能在記憶體容納的前提下快速搜尋百萬筆通訊錄；能為高速公路網找出兩點之間的路徑。第一題偏向將概念轉譯為程式，第二、三題則涉及搜尋策略與圖路徑規劃，牽涉資料結構選型與演算法選擇。作者接著以第二題（通訊錄搜尋）為例，展示在 .NET 中如何用合適的集合型別與演算法達到效能與功能兼顧。

直覺做法：使用 List 與 Find 的侷限

多數開發者會以 List<ContactData> 儲存資料，並利用 Find/FindAll 搜尋單筆或符合條件的多筆。此作法在語法上簡潔且具備委派、匿名方法等技巧，看似成熟，但本質為線性掃描，時間複雜度 O(n)。在百萬筆資料下仍可接受，但當資料成長一至兩個數量級，搜尋延時將等比例放大，導致使用體驗惡化。同時，List 本身不維持排序，若要依不同欄位排序，需要重複呼叫 Sort() 或建立額外結構，成本高也不利於頻繁查詢。作者透過計時器展示建立資料與搜尋所需時間與記憶體占用，為後續比較提供基準，並指出單靠語言熟練無法彌補結構選錯的本質問題。

進一步優化：加入 Dictionary 作精確索引

進階者會為姓名建立 Dictionary<string, ContactData>，以鍵值直接索引到聯絡人，精確查找可達近 O(1) 的時間複雜度。實測顯示，新增建立索引雖提升建置時間與記憶體占用，但查找單一姓名的耗時幾近為零，效能大幅改善。然而，該方式仍無法解決排序與前綴/範圍查詢（如電話以「0928-1234」開頭）的需求；Dictionary 的雜湊特性決定它擅長精確匹配，卻不提供有序遍歷與區間定位。此外，若要同時支援多欄位排序與查詢，必須另建其他索引結構。此處引出核心命題：應依查詢需求挑選能滿足排序與搜尋複合要求的資料結構。

回到本質：時間複雜度與 MSDN 文件的價值

作者強調學術觀念在實務中的價值：從時間複雜度出發，理解 O(1)、O(n)、O(log n)、O(n^2) 在資料放大時的效應，據此評估方案長期伸縮性。MSDN 的集合文件皆標註操作的複雜度，例如 List<T>.Add 平均 O(1) 但 Find 是 O(n)；Dictionary 的索引存取近 O(1)，原因是其底層使用 HashTable。若能讀懂這些註記並連結到資料結構知識，就能在設計時預判瓶頸與風險，而不是等到效能出問題才事後補救。作者以「若資料從百萬增至億級」的產品經理提問為例，說明用複雜度就能推估未來表現，並據以做出正確的架構選擇，避免走錯路。

滿足「多種排序＋快速精確或範圍查找」的標準解，是為不同欄位建立排序結構，並使用 Binary Search。排序好的資料相當於資料庫索引，可高效 order by，也能快速鎖定區間。於 .NET 中可選 SortedList 或 SortedDictionary：兩者皆維持排序，差異在底層實作與插入/存取特性。作者最終選擇 SortedList 為姓名與電話各建一組索引：插入時即維持排序，查找單筆可直接索引，前綴查找（如「0928-1234*」）則以自寫的 Binary Search 找到起訖邊界後做區間遍歷。這種設計使讀取與排序需求一次滿足，代價是載入資料較慢（插入成本 O(n) 或 O(log n) 視情況而定），但對以讀為主的應用非常合適。

實測與推論：從 80 倍到近 6000 倍的差距

作者提供實測結果：以百萬筆資料比較 List 與 SortedList 的搜尋時間，List 需 O(n) 而 SortedList 透過排序後的 Binary Search 為 O(log n)，實際差距約 80 倍。進一步用複雜度外推至一億筆規模，List 的搜尋時間等比例放大，而 SortedList 僅隨對數成長，差距擴大至近 6000 倍。這證明演算法與資料結構的選擇遠比微觀最佳化更能決定系統的可擴充性與使用體驗。作者再次提醒：當資料成長，錯誤的結構選擇會讓程式在記憶體尚未耗盡前就因效能崩潰，唯有選對演算法與結構才能從根本解決問題。

結語：基礎最有用，學校所學要用在對的地方

作者總結，本篇以簡單需求串接到資料結構觀念與 MSDN 文件閱讀，證明基礎的重要性與實用性。許多效能與正確性的關鍵，不在 API 花式用法，而在是否能用複雜度思考、挑對資料結構，並把需求拆解為合適的索引與演算法。作者也分享學習來源多半仍是課本基礎，鼓勵讀者以此心法面對多執行緒、作業系統等更進階主題。最後邀請讀者分享是否在看文前就使用過 SortedList，並預告系列後續內容，期待更多交流與回饋。

資訊整理

知識架構圖

  1. 前置知識：
    • 基本程式能力：變數、陣列、迴圈、函式、類別
    • 基本排序與搜尋：Bubble/Quick sort 概念、線性搜尋、二分搜尋
    • 讀懂官方文件（如 MSDN）與量測工具（Stopwatch、記憶體觀察）
  2. 核心概念：
    • 資料結構與演算法的配對：選對結構才能解對問題（如 exact match 用哈希、範圍/排序用有序結構）
    • 時間複雜度（Big-O）：O(1)、O(log n)、O(n)、O(n log n)、O(n^2) 對規模擴張的影響
    • .NET Collections 的特性差異：List、Dictionary、SortedList、SortedDictionary 與其複雜度
    • 索引化思維：為不同查詢建立對應索引（名字、電話、Email 等）
    • 可擴展性與實務取捨：建立資料成本 vs 查詢效率、記憶體成本 vs 速度
  3. 技術依賴：
    • 基礎演算法與資料結構 -> 了解 Big-O -> 能讀懂/選擇 .NET Collections -> 正確設計索引與查詢
    • .NET/ C# 語法 -> 使用泛型集合 System.Collections.Generic -> 利用 Comparer、IComparer、委派/匿名方法
    • 量測與驗證 -> Stopwatch、WorkingSet -> 根據數據修正結構/演算法
  4. 應用場景：
    • 通訊錄/聯絡人管理：多鍵排序（姓名/Email/電話）、前綴搜尋（如電話開頭）
    • 文字自動完成/過濾列表：邊輸入邊篩選
    • 後端服務查詢：大量資料的精確查詢與範圍查詢
    • 圖與路徑問題（高速公路路徑規劃）：需使用圖結構與最短路徑演算法（如 Dijkstra）

學習路徑建議

  1. 入門者路徑：
    • 練習將想法轉為程式：用陣列與迴圈完成排序（Bubble、Quick）與線性搜尋
    • 熟悉 C# 泛型集合的基本使用：List 增刪查、Find/FindAll、Sort
    • 寫小實作：把一疊數字排序並印出、在 List 中找到指定值
  2. 進階者路徑：
    • 系統性學 Big-O 與常見資料結構：Array、LinkedList、HashTable、Binary Search Tree、Heap
    • 比較 .NET 各集合與複雜度：List、Dictionary、SortedList、SortedDictionary
    • 實作與應用 Binary Search；理解 Comparer/IComparer 與自訂排序鍵
    • 學會讀 MSDN 複雜度標示並用 Stopwatch/記憶體指標做量測
  3. 實戰路徑：
    • 實作大型通訊錄：建立 ContactData 類，為不同欄位建立索引（Dictionary 用於精確、SortedList 用於排序/範圍）
    • 支援前綴查詢：在 SortedList 上以 Binary Search 找到範圍邊界（如 “0928-1234*“）
    • 量測不同結構在 1e6 與 1e8 規模下的建置/查詢時間與記憶體占用
    • 根據需求取捨：若插入很頻繁改考慮 SortedDictionary（平衡樹）或批量建索引策略

關鍵要點清單

  • 選對資料結構決定上限：錯的結構再多微調也回不來（優先級: 高）
  • Big-O 思維：用複雜度預估規模放大後的行為（優先級: 高）
  • List 的搜尋成本：Find/FindAll 是 O(n)，大規模會成瓶頸（優先級: 高）
  • Dictionary<TKey,TValue> 適用場景：精確鍵查詢近似 O(1)，不適合排序/範圍/前綴（優先級: 高）
  • SortedList vs SortedDictionary：前者以陣列實作、索引存取快；後者平衡樹、插入/刪除穩定（優先級: 中）
  • 排序即索引：預先排序搭配 Binary Search 可達 O(log n) 查詢（優先級: 高）
  • 多索引設計：為不同查詢鍵分別建立索引（姓名、電話、Email）（優先級: 高）
  • 前綴/範圍查詢技巧：用 Sorted 結構 + Binary Search 找起訖邊界（優先級: 高）
  • 建置 vs 查詢的取捨：Sorted 結構插入較慢（O(n) 或 O(log n)），但查詢快（優先級: 中）
  • 讀官方文件的能力：MSDN 明載複雜度與結構特性，是選型依據（優先級: 高）
  • 實測與驗證：Stopwatch、WorkingSet 等數據驅動決策（優先級: 中）
  • 可擴展性評估：從 1e6 推估到 1e8 的時間/記憶體成本（優先級: 高）
  • 代碼品質與邏輯細節：迴圈順序、重複計算等基本功仍關鍵（優先級: 中）
  • 映射到更廣問題：從查詢到圖路徑（如高速公路），依需求選圖結構與演算法（優先級: 中）
  • 比較與取捨示例：List O(n) 搜尋 vs Sorted 結構 O(log n)，差距可達數十至數千倍（優先級: 高）




Facebook Pages

AI Synthesis Contents

- 原始文章內容
- 問答集
- 文章摘要
- 解決方案 / Case Study

Edit Post (Pull Request)

Post Directory