這是一份收藏量超過2萬6的計算機科學學習筆記

來自專欄機器之心285 人贊了文章

機器之心整理，作者：鄭永川，參與：思源。

這是一份收藏量超過 2 萬 6、Fork 量超過 7 千的學習筆記。近日，中山大學鄭永川構建了一個「準備秋招學習筆記」的項目，該項目包含了計算機科學的大量精要知識與教程。該項目從基礎排序演算法到編程理念展示了計算機科學的應知應會，該項目對機器學習開發者及入門讀者也非常有用，例如 Linux 系統、面向對象的編程、Git 工具和代碼可讀性等。這些筆記都是作者根據對各類書籍的理解，並記錄重要知識點而完成。

項目地址：https://github.com/CyC2018/Interview-Notebook該項目的主體內容可分為 9 部分，其中演算法介紹了基礎的棧和隊列、並查集、排序和查找等，操作系統介紹了現代計算機系統與 Linux 系統。其它如介紹了設計模式和基本思想的面向對象編程、世界上最先進的分散式版本控制系統 Git、以及 Java 和編程實踐等都有涉及。

如下是該項目各類別的基本目錄與內容，因為機器學習可能會常用到面向對象的編程方法，因此我們在後面簡要介紹了這一章節中面向對象的基本思想。

演算法

• 劍指 Offer 題解（目錄根據原書第二版進行編排）
• Leetcode 題解（做了一個大致分類，並對每種分類題型的解題思路做了總結）
• 演算法（主要參考 Robert Sedgewick 的演算法書進行實現，源代碼以及測試代碼可在另一個倉庫獲取）

操作系統

• 計算機操作系統（參考 現代操作系統、Unix 環境高級編程、深入理解計算機系統）
• Linux（參考 鳥哥的 Linux 私房菜）

網路

• 計算機網路（參考 謝希仁的計算機網路、計算機網路 自頂向下方法、TCP/IP 詳解）
• HTTP（參考 圖解 HTTP，更多的是參考網上的文檔，比如 MDN、維基百科等）
• Socket（參考 Unix 網路編程）

面向對象

• 設計模式（參考 Head First 設計模式、設計模式 可復用面向對象軟體的基礎，實現了 Gof 的 23 種設計模式）
• 面向對象思想（內容包括三大原則（繼承、封裝、多態）、類圖、設計原則）

資料庫

• 資料庫系統原理（參考 資料庫系統原理）
• SQL（參考 SQL 必知必會）
• Leetcode-Database 題解（Leetcode 上資料庫題目的解題記錄）
• MySQL（參考 高性能 MySQL）
• Redis（參考 Redis 設計與實現、Redis 實戰）

Java

• Java 基礎（參考 Effective Java、Java 編程思想，也有部分內容參考官方文檔以及 StackOverflow）
• Java 虛擬機（參考 深入理解 Java 虛擬機）
• Java 並發（參考 Java 編程思想、深入理解 Java 虛擬機）
• Java 容器（包含容器源碼的分析）
• Java I/O（包含 NIO 的原理以及實例）

分散式

• 一致性（CAP、BASE、Paxos、Raft）
• 分散式問題分析（分散式事務、分散式鎖、分散式 Session、負載均衡）

工具

• Git（一些 Git 的使用和概念）
• 正則表達式（參考 正則表達式必知必會）

編碼實踐

• 重構（參考 重構 改善既有代碼的設計）
• 代碼可讀性（參考 編寫可讀代碼的藝術）
• 代碼風格規範（Google 開源項目的代碼風格規範）

面向對象思想

具體而言例如在面向對象的基本思想中，作者介紹了封裝、繼承和多態三大特性，此外還有類圖和設計原則。這裡摘取了原項目中展開的面向對象三大特性，更信息的內容請查看原 GitHub 項目。

面向對象的編程在實現想法乃至系統的過程中都非常重要，我們不論是使用 TensorFlow 還是 PyTorch 來構建模型都或多或少需要使用類和方法。若能了解面向對象的三大特性並使用類和方法來構建模型，那麼它們可以讓我們的機器學習代碼更加美麗迷人。

封裝

利用抽象數據類型將數據和基於數據的操作封裝在一起，使其構成一個不可分割的獨立實體。數據被保護在抽象數據類型的內部，儘可能地隱藏內部的細節，只保留一些對外介面使之與外部發生聯繫。用戶無需知道對象內部的細節，但可以通過對象對外提供的介面來訪問該對象。

優點：

• 減少耦合：可以獨立地開發、測試、優化、使用、理解和修改
• 減輕維護的負擔：可以更容易被程序員理解，並且在調試的時候可以不影響其他模塊
• 有效地調節性能：可以通過剖析確定哪些模塊影響了系統的性能
• 提高軟體的可重用性
• 降低了構建大型系統的風險：即使整個系統不可用，但是這些獨立的模塊卻有可能是可用的

以下 Person 類封裝 name、gender、age 等屬性，外界只能通過 get() 方法獲取一個 Person 對象的 name 屬性和 gender 屬性，而無法獲取 age 屬性，但是 age 屬性可以供 work() 方法使用。

注意到 gender 屬性使用 int 數據類型進行存儲，封裝使得用戶注意不到這種實現細節。並且在需要修改 gender 屬性使用的數據類型時，也可以在不影響客戶端代碼的情況下進行。

public class Person { private String name; private int gender; private int age; public String getName() { return name; } public String getGender() { return gender == 0 ? "man" : "woman"; } public void work() { if (18 <= age && age <= 50) { System.out.println(name + " is working very hard!"); } else { System.out.println(name + " cant work any more!"); } }}

繼承

繼承實現了 IS-A 關係，例如 Cat 和 Animal 就是一種 IS-A 關係，因此 Cat 可以繼承自 Animal，從而獲得 Animal 非 private 的屬性和方法。

Cat 可以當做 Animal 來使用，也就是說可以使用 Animal 引用 Cat 對象。父類引用指向子類對象稱為 向上轉型。

Animal animal = new Cat();

繼承應該遵循里氏替換原則，子類對象必須能夠替換掉所有父類對象。

多態

多態分為編譯時多態和運行時多態。編譯時多態主要指方法的重載，運行時多態指程序中定義的對象引用所指向的具體類型在運行期間才確定。

運行時多態有三個條件：

• 繼承
• 覆蓋（重寫）
• 向上轉型

下面的代碼中，樂器類（Instrument）有兩個子類：Wind 和 Percussion，它們都覆蓋了父類的 play() 方法，並且在 main() 方法中使用父類 Instrument 來引用 Wind 和 Percussion 對象。在 Instrument 引用調用 play() 方法時，會執行實際引用對象所在類的 play() 方法，而不是 Instrument 類的方法。

public class Instrument { public void play() { System.out.println("Instument is playing..."); }}public class Wind extends Instrument { public void play() { System.out.println("Wind is playing..."); }}public class Percussion extends Instrument { public void play() { System.out.println("Percussion is playing..."); }}public class Music { public static void main(String[] args) { List<Instrument> instruments = new ArrayList<>(); instruments.add(new Wind()); instruments.add(new Percussion()); for(Instrument instrument : instruments) { instrument.play(); } }}

推薦閱讀：