程式設計師必練六大項目：從數據結構到作業系統，電腦教授為你畫重點
- 2019 年 12 月 19 日
- 筆記
編程這件事，光有理論是不夠的，動手實踐是必修課。
不過，從什麼項目入手，往往讓人犯了難。
如果你還在糾結，應該拿什麼項目來開始自己的編程練習，不妨來看看這份「程式設計師都應該嘗試的挑戰性項目」清單。
這是田納西大學助理教授奧斯汀·亨利（Austin Z. Henley）結合自身經驗，給出的良心推薦。不僅總結了知識要點，讓你在學習中有的放矢，還貼心整理了拓展閱讀資料。
你可以多次構建這些項目，每次從中收穫新的知識。 每當我不知道該拿什麼練手，或者想學習一種新的程式語言或框架時，我就會從以下項目中選擇一種開始coding：
每個程式設計師都應該嘗試的挑戰性項目
文本編輯器
不使用GUI框架中內置的文本框組件，要如何搭建支援游標移動、選擇、插入和刪除操作的文本框？
這個項目中，存在兩個主要挑戰：
- 如何將文本文檔存儲在記憶體中
- 學習文本游標在流行的編輯器中的行為
不要小看這些基礎的功能，其中有許多細節值得注意。比如當游標位於文本當中，按下向上箭頭，游標會移動到何處？
△圖源：Austin Z. Henley
如果你覺得這太簡單，還有進階測試：
- 撤銷/重做
- 自動換行
最後總結一下知識要點：
- 用於存儲文本的數據結構：數組，rope，gap buffer，piece table
- 文本游標的行為和實現
- 撤銷/重做的設計模式：記憶，命令
- 分離文本視覺和記憶的抽象
別忘了還有拓展閱讀喲：
2D遊戲-太空侵略者
即使是最簡單的遊戲也需要考慮數據結構和設計模式。
在這個項目中，你的任務是從頭到尾實現一個定義明確的遊戲。最好使用SDL，SFML，PyGame這樣的2D圖形庫。
△圖源：Austin Z. Henley
第一步，創建對象移動的效果。
第二步，了解有關遊戲循環的所有資訊。遊戲實際上是在繪圖、獲取用戶輸入和處理遊戲邏輯之間循環。
第三步，處理用戶輸入。
第四步，學習如何創建和管理所有遊戲對象及其狀態。比如如何生成動態數量的敵人。
第五步，學習如何應用遊戲的邏輯。子彈頭位置何時更新？什麼時候會有更多敵人出現在螢幕上？怎麼判定敵人被幹掉了？遊戲何時結束？
甚至，在進階階段，你還可以考慮引入AI，來製造更加「智慧」的敵人。
編譯器-Tiny BASIC
從頭開始編寫一種非常小的類似於BASIC的語言編譯器，然後將其編譯為任何其他語言。比如，用Python編寫可以輸出C#程式碼的Tiny BASIC編譯器。
△圖源：Austin Z. Henley
知識點：
- 詞法分析
- 句法分析
- 遞歸下降解析
- 抽象語法樹
- 語義分析
- 優化passes
- 程式碼生成
迷你作業系統
從這個項目開始，難度就加大了。
作業系統依賴於硬體，因此入門門檻比較高。但這個項目可以幫助你更好地理解電腦底層都發生了什麼。
作者亨利推薦了一本免費電子書《使用Rust構建RISC-V作業系統》作為入門教材（地址見文末）。
△圖源：Austin Z. Henley
知識點：
- 交叉編譯
- Bootloading
- BIOS中斷
- x86模式
- 記憶體管理和分頁
- 排程（Scheduling）
- 文件系統
如果以上四個項目，你都覺得so easy，那麼就來嘗試一下最後這兩個高難度項目吧。
電子表格
電子表格應用程式（如Excel）將文本編輯器和編譯器的挑戰結合在了一起。
在這個項目中，你需要學會如何在記憶體中表示單元格內容，並實現用於方程式的程式語言解釋器。
電子遊戲機模擬器
這是一個作業系統+編譯器的二合一挑戰項目。
挑戰內容是，編寫一個虛擬機，讓虛擬機可以像真實的CPU和其他硬體組件一樣運行。
亨利的建議，是從簡單的虛擬控制台入手，比如CHIP-8。
網友建言獻策
部落格一出，在Hacker News、Reddit上受到了廣大碼農們的歡迎。
有網友說：
這些項目能讓我接觸到完全不同的領域和問題，比我日常的工作更能激勵我。
並且，網友們紛紛建言獻策，又推舉出好幾個優質上手項目：
- 從零搭建資料庫
- 光線追蹤器
- 矢量圖形編輯器
- 影像解碼器
- 網頁聊天室
- pi計算器的位數
- 通用終端實用程式（如grep）
- FTP客戶端和伺服器
所以，這些項目是否激發了你的靈感？
Talk is cheap. Show me the code. 快動手練起來吧~
傳送門
部落格地址： http://web.eecs.utk.edu/~azh/blog/challengingprojects.html
Hacker News討論（內含更多項目推薦）： https://news.ycombinator.com/item?id=21790779
《使用Rust構建RISC-V作業系統》： http://osblog.stephenmarz.com/index.html
