簡(jiǎn)介《Implementing Useful Algorithms in C》由Dmytro Kedyk撰寫(xiě)面向希望深入掌握C算法設(shè)計(jì)與實(shí)現(xiàn)的中高級(jí)開(kāi)發(fā)者與計(jì)算機(jī)專業(yè)學(xué)生幫助讀者在正確性證明、漸進(jìn)記法、機(jī)器模型等理論基礎(chǔ)上寫(xiě)出高效且可維護(hù)的代碼。全書(shū)從數(shù)據(jù)類型選擇、內(nèi)存管理、代碼優(yōu)化講到遞歸控制、多算法選型與并行化并穿插軟件工程開(kāi)發(fā)周期、測(cè)試、代碼審查等實(shí)踐內(nèi)容每章末尾還附有推薦課程、學(xué)習(xí)策略與項(xiàng)目練習(xí)。資源包為1個(gè)PDF文件大小約485.74MB內(nèi)容完整、目錄結(jié)構(gòu)清晰便于按章節(jié)檢索學(xué)習(xí)。目前已有183人學(xué)習(xí)下載。讀者可借此系統(tǒng)梳理算法實(shí)現(xiàn)思路理解隨機(jī)化算法、位運(yùn)算、并查集等具體技術(shù)的落地方式并借助書(shū)中的參考資料與項(xiàng)目建議將理論轉(zhuǎn)化為實(shí)際編程能力。1. 算法實(shí)現(xiàn)的真相為什么“會(huì)寫(xiě)代碼”和“能實(shí)現(xiàn)算法”是兩回事很多人以為算法實(shí)現(xiàn)就是把偽代碼翻譯成 C。這個(gè)認(rèn)知偏差恰恰是大量項(xiàng)目在性能上翻車的根源。一本 2020 年出版、ISBN 為 9798605325307 的 C 算法書(shū)用整整 28 章、從內(nèi)存管理講到機(jī)器學(xué)習(xí)反復(fù)在說(shuō)同一件事算法從紙面到機(jī)器之間隔著一整套關(guān)于機(jī)器模型、數(shù)據(jù)類型、內(nèi)存布局和誤差傳播的工程判斷。這些判斷不會(huì)出現(xiàn)在偽代碼里卻決定了你的實(shí)現(xiàn)是跑得比標(biāo)準(zhǔn)庫(kù)快還是慢十倍。搞懂這套判斷背后的機(jī)制比多背幾個(gè)算法模板有用得多。這本書(shū)的目錄本身就是一份“算法實(shí)現(xiàn)知識(shí)地圖”第 1 章講算法正確性證明與漸進(jìn)記法第 5 章講基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)第 6 章講隨機(jī)數(shù)生成第 11 章講圖算法第 13 章講外存算法第 22 到 24 章講數(shù)值算法第 25 到 28 章講機(jī)器學(xué)習(xí)。它沒(méi)有停留在“這個(gè)算法是什么”而是持續(xù)追問(wèn)“在真實(shí)機(jī)器上怎么讓它 work”。下面從幾個(gè)關(guān)鍵機(jī)制切入把這條從數(shù)學(xué)到硅片的鏈路拆開(kāi)看。2. 漸進(jìn)記法之外機(jī)器模型如何決定算法的真實(shí)代價(jià)2.1 大 O 符號(hào)的隱含假設(shè)以及它什么時(shí)候會(huì)騙你漸進(jìn)記法描述的是當(dāng)輸入規(guī)模趨于無(wú)窮時(shí)算法代價(jià)的增長(zhǎng)階。它成立的前提是一套機(jī)器模型每次基本操作代價(jià)相同每次內(nèi)存訪問(wèn)代價(jià)相同。這個(gè)假設(shè)在紙面上沒(méi)問(wèn)題在真實(shí)機(jī)器上卻經(jīng)常不成立。一個(gè)在漸進(jìn)意義下更優(yōu)的算法可能因?yàn)槌?shù)因子、緩存不友好或分支預(yù)測(cè)失敗在實(shí)際運(yùn)行中輸給一個(gè)“更笨”的算法。書(shū)里第 1 章專門(mén)討論了機(jī)器模型和效率測(cè)量這不是走過(guò)場(chǎng)。以矩陣乘法為例樸素三重循環(huán)是 O(n3)Strassen 算法是 O(n^2.807)但在 n 小于某個(gè)閾值時(shí)Strassen 因?yàn)檫f歸開(kāi)銷和緩存局部性差反而更慢。常見(jiàn)的實(shí)現(xiàn)思路是設(shè)置一個(gè) cutoff小規(guī)模用樸素算法大規(guī)模才切換。這個(gè) cutoff 不是拍腦袋定的而是要在目標(biāo)機(jī)器上實(shí)測(cè)出來(lái)的。注意漸進(jìn)復(fù)雜度是篩選算法的第一道門(mén)檻不是最后一道。過(guò)了這道門(mén)檻之后決定勝負(fù)的是內(nèi)存訪問(wèn)模式和指令級(jí)并行度。2.2 緩存行為為什么數(shù)組遍歷順序能帶來(lái)數(shù)倍差距考慮一個(gè)二維數(shù)組的行優(yōu)先遍歷和列優(yōu)先遍歷。兩者在漸進(jìn)復(fù)雜度上完全一樣都是 O(n2) 次訪問(wèn)。但行優(yōu)先遍歷按內(nèi)存順序訪問(wèn)每次緩存行加載都能被后續(xù)若干次訪問(wèn)復(fù)用列優(yōu)先遍歷每次訪問(wèn)都跨過(guò)一個(gè)完整的行長(zhǎng)度緩存行利用率極低。在 n 較大時(shí)兩者差距可以達(dá)到一個(gè)數(shù)量級(jí)。書(shū)里第 5 章講 Vector 和 Block Array 時(shí)核心關(guān)切就是內(nèi)存布局。Block Array 把大數(shù)組切成固定大小的塊塊內(nèi)連續(xù)存儲(chǔ)塊間用指針連接。這樣既保留了隨機(jī)訪問(wèn)能力又避免了單塊大內(nèi)存分配帶來(lái)的碎片和拷貝成本。它的代價(jià)是索引計(jì)算多了一層間接先算塊號(hào)再算塊內(nèi)偏移。這層間接在緩存命中時(shí)幾乎免費(fèi)在緩存未命中時(shí)就是額外的一次內(nèi)存訪問(wèn)。// Block Array 的索引計(jì)算示意 template typename T, size_t BlockSize T BlockArrayT, BlockSize::operator[](size_t i) { size_t block_idx i / BlockSize; // 先定位到塊 size_t offset i % BlockSize; // 再定位到塊內(nèi)偏移 return blocks_[block_idx][offset]; // 兩次間接訪問(wèn) }這段代碼里blocks_是一個(gè)指針數(shù)組每個(gè)元素指向一塊連續(xù)內(nèi)存。i / BlockSize和i % BlockSize在 BlockSize 是 2 的冪時(shí)可以被編譯器優(yōu)化成移位和掩碼這是選擇塊大小的一個(gè)隱藏約束。如果 BlockSize 是 1000 這樣的非 2 的冪除法指令的延遲就會(huì)暴露在熱路徑上。2.3 隨機(jī)化算法用概率換確定性的工程取舍書(shū)里第 1 章和第 6 章都涉及隨機(jī)化算法。隨機(jī)化算法的價(jià)值在于某些問(wèn)題在確定性算法下需要復(fù)雜的邊界處理或高昂的最壞情況代價(jià)而引入隨機(jī)性后期望代價(jià)可以做到很低且實(shí)現(xiàn)大幅簡(jiǎn)化?？焖倥判虻碾S機(jī)化版本就是典型隨機(jī)選 pivot 后最壞情況 O(n2) 的概率極低期望 O(n log n)且不需要像確定性選 pivot 那樣維護(hù)復(fù)雜的中位數(shù)邏輯。但隨機(jī)化算法有一個(gè)工程上容易被忽視的問(wèn)題隨機(jī)數(shù)生成器的質(zhì)量直接影響算法行為。書(shū)里第 6 章專門(mén)講了 Xorshift、Mersenne Twister、MRG32k3a 等生成器。Xorshift 速度極快但周期和統(tǒng)計(jì)性質(zhì)不如 Mersenne TwisterMersenne Twister 質(zhì)量好但狀態(tài)數(shù)組大、初始化慢。如果隨機(jī)化算法對(duì)隨機(jī)性質(zhì)量敏感用 Xorshift 可能在某些輸入下退化如果只是打散一下遍歷順序Xorshift 完全夠用。// Xorshift 生成器極簡(jiǎn)但周期和統(tǒng)計(jì)性質(zhì)有限 unsigned int randomNumber(unsigned int x time(0)) { x ^ x 13; x ^ x 17; x ^ x 5; return x; }這段代碼展示了 Xorshift 的核心操作三次移位和異或。它的狀態(tài)就是一個(gè) 32 位整數(shù)周期為 232-1。注意默認(rèn)參數(shù)用time(0)做種子這在需要可復(fù)現(xiàn)實(shí)驗(yàn)的場(chǎng)景下是個(gè)坑——每次運(yùn)行結(jié)果不同調(diào)試時(shí)無(wú)法復(fù)現(xiàn)。書(shū)里在實(shí)現(xiàn)筆記里應(yīng)該會(huì)提到生產(chǎn)環(huán)境要用獨(dú)立的種子管理而不是依賴時(shí)間。3. 數(shù)據(jù)結(jié)構(gòu)的選擇從接口需求反推內(nèi)存布局3.1 動(dòng)態(tài)有序序列跳表和 Treap 的取舍書(shū)里第 8 章講動(dòng)態(tài)有序序列覆蓋了跳表、Treap、Trie 等結(jié)構(gòu)。這些結(jié)構(gòu)都支持插入、刪除、查找、前驅(qū)后繼等操作漸進(jìn)復(fù)雜度也相近但工程特性差異很大。跳表的優(yōu)勢(shì)是實(shí)現(xiàn)簡(jiǎn)單、緩存局部性相對(duì)好節(jié)點(diǎn)在底層鏈表上連續(xù)分布缺點(diǎn)是隨機(jī)化層數(shù)導(dǎo)致最壞情況不確定。Treap 把堆性質(zhì)和二叉搜索樹(shù)性質(zhì)結(jié)合用隨機(jī)優(yōu)先級(jí)維持平衡期望樹(shù)高 O(log n)但每個(gè)節(jié)點(diǎn)需要額外存儲(chǔ)優(yōu)先級(jí)且指針跳轉(zhuǎn)對(duì)緩存不友好。選擇哪個(gè)取決于操作分布。如果查找遠(yuǎn)多于插入刪除且數(shù)據(jù)量不大Treap 的簡(jiǎn)單性可能更優(yōu)如果插入刪除頻繁且對(duì)最壞情況延遲敏感跳表的概率平衡更容易控制尾部延遲。書(shū)里第 8 章有性能對(duì)比小節(jié)這種對(duì)比不是學(xué)術(shù)表演而是給工程選型提供依據(jù)。3.2 哈希表鏈?zhǔn)脚c線性探測(cè)的緩存代價(jià)差異第 9 章講哈希鏈?zhǔn)焦１砗途€性探測(cè)哈希表的對(duì)比很能說(shuō)明問(wèn)題。鏈?zhǔn)焦１砻總€(gè)桶掛一個(gè)鏈表沖突時(shí)遍歷鏈表。線性探測(cè)在沖突時(shí)順序探測(cè)下一個(gè)槽位。鏈?zhǔn)焦１淼闹羔樚D(zhuǎn)對(duì)緩存不友好但刪除操作簡(jiǎn)單線性探測(cè)的探測(cè)序列在內(nèi)存上連續(xù)緩存命中率高但刪除需要墓碑標(biāo)記且負(fù)載因子不能太高。書(shū)里第 9 章還講了通用哈希函數(shù)和滾動(dòng)哈希。通用哈希函數(shù)的價(jià)值在于它對(duì)任意輸入分布都能保證沖突概率上界這在對(duì)抗性場(chǎng)景下很重要。滾動(dòng)哈希則用于字符串匹配等場(chǎng)景能在 O(1) 時(shí)間內(nèi)從上一個(gè)窗口的哈希值算出下一個(gè)窗口的哈希值。// 滾動(dòng)哈希的核心利用多項(xiàng)式哈希的遞推性質(zhì) // hash(s[i..im-1]) 可以從 hash(s[i-1..im-2]) 在 O(1) 內(nèi)推出 uint64_t rolling_hash(const string s, int start, int len, uint64_t base) { uint64_t h 0; for (int i start; i start len; i) { h h * base s[i]; // 初始窗口的哈希 } return h; } // 滑動(dòng)時(shí)h (h - s[i-1] * base^(len-1)) * base s[ilen-1]這段代碼的關(guān)鍵在于base^(len-1)這個(gè)因子。它需要在滑動(dòng)前預(yù)計(jì)算好否則每次滑動(dòng)都重新計(jì)算冪次O(1) 就退化成 O(len)。書(shū)里在實(shí)現(xiàn)筆記里應(yīng)該會(huì)強(qiáng)調(diào)這個(gè)預(yù)計(jì)算以及 base 的選擇要足夠大且與字符集互質(zhì)否則哈希碰撞率會(huì)上升。3.3 優(yōu)先隊(duì)列索引堆為什么比普通堆多一層映射第 10 章講優(yōu)先隊(duì)列普通二叉堆只支持取最小值和插入不支持按索引修改優(yōu)先級(jí)。索引堆在堆數(shù)組之外維護(hù)一個(gè)索引到堆位置的映射表使得修改某個(gè)元素的優(yōu)先級(jí)后能快速上浮或下沉。這個(gè)映射表的代價(jià)是額外的內(nèi)存和每次交換時(shí)的雙向更新。// 索引堆的交換操作同時(shí)更新堆數(shù)組和位置映射 void IndexedHeap::swap(int i, int j) { std::swap(heap_[i], heap_[j]); pos_[heap_[i].id] i; // 更新位置映射 pos_[heap_[j].id] j; }這段代碼里pos_數(shù)組是索引堆的核心。沒(méi)有它修改優(yōu)先級(jí)就只能線性搜索。有了它修改是 O(log n)。但每次交換都要更新兩個(gè)位置常數(shù)因子比普通堆大。如果應(yīng)用場(chǎng)景不需要修改優(yōu)先級(jí)普通堆更劃算。4. 避坑與排查算法實(shí)現(xiàn)中那些教科書(shū)不講的翻車點(diǎn)4.1 遞歸深度失控導(dǎo)致棧溢出現(xiàn)象遞歸實(shí)現(xiàn)的快速排序或樹(shù)遍歷在極端輸入下崩潰錯(cuò)誤信息指向棧溢出。原因遞歸深度與輸入規(guī)模成正比而默認(rèn)棧大小通常只有幾 MB每個(gè)棧幀幾十到幾百字節(jié)幾萬(wàn)層遞歸就爆了。解決要么改成迭代加顯式棧要么在遞歸前估算深度并設(shè)置閾值超過(guò)閾值切換到迭代版本。書(shū)里第 1 章講遞歸時(shí)應(yīng)該會(huì)提到尾遞歸優(yōu)化但 C 編譯器對(duì)尾遞歸的支持并不保證不能依賴。4.2 浮點(diǎn)誤差累積導(dǎo)致數(shù)值算法結(jié)果失真現(xiàn)象數(shù)值積分或矩陣分解的結(jié)果與理論值偏差越來(lái)越大甚至出現(xiàn)負(fù)的方差。原因浮點(diǎn)運(yùn)算不滿足結(jié)合律大量累加時(shí)誤差會(huì)累積。書(shū)里第 22 章講浮點(diǎn)算術(shù)和誤差傳播核心思想是誤差不可避免但可以通過(guò)算法設(shè)計(jì)控制其增長(zhǎng)。解決使用 Kahan 求和補(bǔ)償誤差或者選擇數(shù)值穩(wěn)定的算法變體如 QR 分解代替正規(guī)方程解最小二乘。4.3 哈希函數(shù)選擇不當(dāng)導(dǎo)致性能退化現(xiàn)象哈希表在特定輸入下所有元素沖突到同一個(gè)桶查找退化成 O(n)。原因哈希函數(shù)對(duì)輸入分布敏感或者被對(duì)抗性輸入針對(duì)。解決使用通用哈希函數(shù)或者在哈希函數(shù)中引入隨機(jī)種子。書(shū)里第 9 章講通用哈希函數(shù)時(shí)核心就是讓沖突概率對(duì)任意輸入分布都有上界。4.4 內(nèi)存分配成為熱路徑瓶頸現(xiàn)象算法邏輯沒(méi)問(wèn)題但性能分析顯示大量時(shí)間花在 malloc/free 上。原因頻繁的小對(duì)象分配釋放導(dǎo)致分配器鎖競(jìng)爭(zhēng)和碎片。解決使用對(duì)象池或自由列表批量預(yù)分配。書(shū)里第 5 章講垃圾回收自由列表就是針對(duì)這個(gè)問(wèn)題的。4.5 并行化后結(jié)果不確定或性能反而下降現(xiàn)象多線程版本比單線程還慢或者每次運(yùn)行結(jié)果不同。原因偽共享導(dǎo)致緩存行頻繁失效或者任務(wù)劃分粒度過(guò)細(xì)導(dǎo)致調(diào)度開(kāi)銷超過(guò)計(jì)算收益。解決對(duì)齊數(shù)據(jù)結(jié)構(gòu)到緩存行邊界調(diào)整任務(wù)粒度使用線程局部存儲(chǔ)減少共享。書(shū)里第 1 章講并行化時(shí)應(yīng)該會(huì)強(qiáng)調(diào)這些工程約束。5. 從算法到機(jī)器數(shù)值穩(wěn)定性與并行化的設(shè)計(jì)取舍數(shù)值算法和機(jī)器學(xué)習(xí)部分占了這本書(shū)近三分之一的篇幅這不是湊數(shù)。第 22 章講浮點(diǎn)算術(shù)、矩陣分解、特征值計(jì)算第 23 章講函數(shù)逼近、積分、微分方程第 24 章講優(yōu)化第 25 到 28 章講機(jī)器學(xué)習(xí)。這些內(nèi)容有一個(gè)共同主題數(shù)學(xué)上的等價(jià)變換在浮點(diǎn)世界和并行環(huán)境下并不等價(jià)。以最小二乘為例數(shù)學(xué)上解正規(guī)方程(A^T A) x A^T b和用 QR 分解解A x b是等價(jià)的。但正規(guī)方程的條件數(shù)是 A 的條件數(shù)的平方當(dāng) A 接近奇異時(shí)正規(guī)方程的數(shù)值解可能完全失真。QR 分解的條件數(shù)只與 A 本身有關(guān)數(shù)值穩(wěn)定性好得多。書(shū)里第 22 章講 LUP 分解、Cholesky 分解、QR 分解時(shí)應(yīng)該會(huì)反復(fù)強(qiáng)調(diào)條件數(shù)和穩(wěn)定性而不是只給公式。并行化的取舍同樣如此。把一個(gè)大矩陣乘法拆成多個(gè)線程理論上加速比接近線程數(shù)。但實(shí)際上線程間共享內(nèi)存的緩存一致性協(xié)議會(huì)導(dǎo)致偽共享兩個(gè)線程修改同一緩存行內(nèi)的不同變量緩存行在兩個(gè)核心之間反復(fù)彈跳性能急劇下降。解決辦法是填充對(duì)齊讓每個(gè)線程的變量獨(dú)占緩存行。這個(gè)填充浪費(fèi)了內(nèi)存換來(lái)了并行效率是典型的空間換時(shí)間。書(shū)里第 1 章講“在多種算法之間選擇”和“如何實(shí)現(xiàn)一個(gè)算法”時(shí)核心思想是算法選擇不是查表而是根據(jù)問(wèn)題特性、機(jī)器模型、精度要求和并行環(huán)境做綜合判斷。同一個(gè)問(wèn)題在單核浮點(diǎn)環(huán)境下最優(yōu)的算法在多核整數(shù)環(huán)境下可能完全不是對(duì)手。這種判斷力才是這本書(shū)真正想傳遞的東西。我自己的習(xí)慣是每次實(shí)現(xiàn)一個(gè)算法前先問(wèn)三個(gè)問(wèn)題輸入規(guī)模的實(shí)際分布是什么內(nèi)存訪問(wèn)模式是否緩存友好數(shù)值誤差會(huì)不會(huì)累積到影響決策這三個(gè)問(wèn)題答不上來(lái)代碼寫(xiě)得再漂亮也是空中樓閣。從那以后我每次做算法選型都強(qiáng)制走一遍這三個(gè)問(wèn)題翻車的次數(shù)少了很多。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取