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