周末在家把快速排序這個(gè)經(jīng)典的不能再經(jīng)典的算法重新擼了一遍。最近正好在折騰MoonBit這門面向WebAssembly生態(tài)的新語言就順手做了個(gè)對(duì)比實(shí)驗(yàn)同一個(gè)快速排序用C語言寫一遍再用MoonBit寫一遍最后把兩版代碼攤開來看差異比我想象的還要有意思。這個(gè)對(duì)比適合三種人看一是剛學(xué)完C語言快速排序、想看看別的語言怎么寫算法的學(xué)生二是對(duì)MoonBit這種新語言好奇、想快速了解它和C語言到底差在哪的開發(fā)者三是雖然寫過很多年代碼、但很少停下來思考“同一種算法在不同語言里為什么會(huì)長(zhǎng)得不一樣”的從業(yè)者?？赐赀@篇你會(huì)同時(shí)收獲兩套可復(fù)現(xiàn)的快排代碼以及一套分析語言特性的思維框架。1. 兩個(gè)語言的路數(shù)為什么要做這次對(duì)比1.1 C語言快排的心智模型C語言在編程界的地位不用多講。我在學(xué)校第一次寫快速排序就是用C當(dāng)時(shí)的感覺是這個(gè)算法本質(zhì)上是“內(nèi)存操作”的組合。數(shù)組是一段連續(xù)內(nèi)存交換兩個(gè)元素就是拿指針去改內(nèi)存里的值遞歸調(diào)用就是在系統(tǒng)棧上不斷壓入函數(shù)幀。這種心智模型非常底層但反過來也逼著你把算法徹底理解透。你寫swap的時(shí)候必須自己想清楚指針怎么傳寫分區(qū)函數(shù)的時(shí)候必須手動(dòng)維護(hù)low和high兩個(gè)下標(biāo)寫遞歸的時(shí)候必須擔(dān)心深度太大會(huì)不會(huì)爆棧。每一步都是“裸”操作沒有任何語法糖幫你兜底。所以C語言版快排通常長(zhǎng)這樣一個(gè)swap函數(shù)、一個(gè)partition函數(shù)、一個(gè)quickSort函數(shù)函數(shù)之間靠數(shù)組和下標(biāo)顯式通信。代碼本身不長(zhǎng)但每一行都在和內(nèi)存打交道。1.2 MoonBit帶來了哪些新東西MoonBit是近年來出現(xiàn)的一門面向WebAssembly的云原生語言語法上吸取了Rust、Go、TypeScript的一些優(yōu)點(diǎn)有類型推斷、模式匹配、Option/Result這些現(xiàn)代語言特性同時(shí)還能編譯成高效Wasm代碼。它給寫算法的人提供了一個(gè)新選擇你仍然可以用命令式風(fēng)格寫快排與C語言的邏輯幾乎一一對(duì)應(yīng)但同時(shí)也可以用函數(shù)式風(fēng)格、用模式匹配去寫讓代碼從“我們?cè)趺床僮鲀?nèi)存”變成“我們?cè)趺疵枋鲞壿嫛?。這句話是關(guān)鍵。C語言讓你成為一個(gè)優(yōu)秀的“內(nèi)存操作員”而MoonBit讓你有條件做一個(gè)“邏輯表達(dá)者”。同一個(gè)算法兩者的思考路徑完全不同。把這兩版放在一起看才能真正體會(huì)語言設(shè)計(jì)對(duì)思維方式的影響。2. 先把C版本寫利索經(jīng)典快速排序拆解2.1 教科書版遞歸實(shí)現(xiàn)先貼一段最常見的C語言實(shí)現(xiàn)采用Lomuto分區(qū)方案以數(shù)組最后一個(gè)元素作為基準(zhǔn)值#include stdio.h void swap(int *a, int *b) { int temp *a; *a *b; *b temp; } int partition(int arr[], int low, int high) { int pivot arr[high]; // 選最后一個(gè)元素當(dāng)基準(zhǔn) int i low - 1; // i始終指向小于pivot區(qū)間的最后一個(gè)位置 for (int j low; j high; j) { if (arr[j] pivot) { i; swap(arr[i], arr[j]); } } swap(arr[i 1], arr[high]); return i 1; } void quickSort(int arr[], int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); } } int main() { int arr[] {9, 7, 5, 11, 12, 2, 14, 3, 10, 6}; int n sizeof(arr) / sizeof(arr[0]); quickSort(arr, 0, n - 1); for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); return 0; }邏輯本身很直白partition先把比基準(zhǔn)小的元素?fù)Q到左邊比基準(zhǔn)大的留在右邊最后把基準(zhǔn)放到中間位置并返回它的下標(biāo)然后quickSort分別對(duì)左右兩個(gè)子區(qū)間遞歸調(diào)用自己。遞歸出口是low high也就是區(qū)間里只剩一個(gè)元素或者為空。2.2 容易被忽略的邊界問題這段代碼看起來簡(jiǎn)單但邊界條件全是坑。第一個(gè)坑是i的初始值。i low - 1看起來奇怪實(shí)際是給“未找到比基準(zhǔn)小的元素”留了一個(gè)初始空區(qū)間。如果你把i初始化為low第一個(gè)小于基準(zhǔn)的元素會(huì)被放到錯(cuò)誤的位置。第二個(gè)坑是遞歸區(qū)間的劃分。pi返回的是基準(zhǔn)最終所在的下標(biāo)所以左半部分是low到pi - 1右半部分是pi 1到high。如果你寫成quickSort(arr, low, pi)或者quickSort(arr, pi, high)就會(huì)把基準(zhǔn)元素重復(fù)排序嚴(yán)重時(shí)導(dǎo)致無限遞歸。第三個(gè)坑是數(shù)組長(zhǎng)度與下標(biāo)的轉(zhuǎn)換。調(diào)用時(shí)傳入high n - 1主函數(shù)里用sizeof(arr) / sizeof(arr[0])去求長(zhǎng)度容易忘記減1。用動(dòng)態(tài)數(shù)組的人還會(huì)在這里犯第二個(gè)錯(cuò)直接把malloc得來的指針傳入quickSort但丟失了長(zhǎng)度信息。更好的做法是封裝一個(gè)入口函數(shù)void quickSortWrapper(int arr[], int n) { quickSort(arr, 0, n - 1); }這樣調(diào)用方不用關(guān)心下標(biāo)細(xì)節(jié)只傳遞數(shù)組和長(zhǎng)度。2.3 關(guān)于遞歸和棧的真相熱搜詞里有“單片機(jī)c語言沒有堆棧嗎為什么”順帶說一句C語言在絕大多數(shù)平臺(tái)下都有調(diào)用棧單片機(jī)也是如此。函數(shù)調(diào)用、局部變量、返回地址都依賴棧只是棧的大小差異很大。PC上默認(rèn)?？臻g通常是MB級(jí)別普通遞歸深度幾千上萬層問題不大單片機(jī)上棧空間可能只有幾KB到幾十KB遞歸深度稍微上去就溢出?？焖倥判蜃顗那闆r下的遞歸深度是O(n)當(dāng)輸入已經(jīng)有序、而你每次又選最后一個(gè)元素當(dāng)基準(zhǔn)時(shí)遞歸深度就是n。對(duì)10萬個(gè)有序元素排序C語言的遞歸深度就會(huì)到10萬在PC上可能勉強(qiáng)能撐住在單片機(jī)或嵌入式環(huán)境里幾乎必然出問題。所以嵌入式場(chǎng)景里更穩(wěn)的方案有兩種一是改用三數(shù)取中或隨機(jī)選基準(zhǔn)把最壞情況變成小概率事件二是把遞歸改為顯式棧迭代。顯式棧版本可以用malloc手動(dòng)管理一塊內(nèi)存當(dāng)棧用深度不再受系統(tǒng)棧限制。這個(gè)改法代碼量不長(zhǎng)但能徹底規(guī)避爆棧風(fēng)險(xiǎn)我在做嵌入式項(xiàng)目時(shí)都寧愿多寫幾行也要圖個(gè)安穩(wěn)。3. MoonBit版命令式寫法先來一發(fā)3.1 結(jié)構(gòu)體和可變數(shù)組MoonBit同樣支持命令式風(fēng)格。數(shù)組、循環(huán)、變量賦值都是有的所以你能用幾乎和C語言一樣的思路寫快排。這里是MoonBit的命令式版本fn swap(arr: Array[Int], i: Int, j: Int) - Unit { let temp arr[i] arr[i] arr[j] arr[j] temp } fn partition(arr: Array[Int], low: Int, high: Int) - Int { let pivot arr[high] let mut i low - 1 for j low; j high; j j 1 { if arr[j] pivot { i i 1 swap(arr, i, j) } } swap(arr, i 1, high) i 1 } fn quick_sort(arr: Array[Int], low: Int, high: Int) - Unit { if low high { let pi partition(arr, low, high) quick_sort(arr, low, pi - 1) quick_sort(arr, pi 1, high) } }對(duì)照C語言版本函數(shù)簽名、循環(huán)邏輯、遞歸結(jié)構(gòu)幾乎一模一樣區(qū)別主要在語法層面C語言用int *a這種指針參數(shù)來修改變量而在MoonBit里數(shù)組本身就是帶長(zhǎng)度信息的引用類型直接傳數(shù)組變量進(jìn)去就能原位修改不用再額外傳指針。對(duì)int這種基礎(chǔ)類型做交換時(shí)C用指針解引用MoonBit則是靠let mut i low - 1這樣的可變綁定配合數(shù)組下標(biāo)操作意圖更明確。3.2 從C移植到MoonBit的體驗(yàn)如果你手頭已經(jīng)有一份C語言快排想把它“翻譯”成MoonBit命令式版本幾乎不需要改算法邏輯只需要做三類語法修正把int arr[]改成Array[Int]把int *a這種交換函數(shù)簡(jiǎn)化成直接傳入數(shù)組和兩個(gè)下標(biāo)。把for (int j low; j high; j)改成for j low; j high; j j 1注意MoonBit的for循環(huán)里循環(huán)變量默認(rèn)綁定且每次迭代重新綁定不需要你寫int聲明。把可能出現(xiàn)“沒有返回值”的函數(shù)標(biāo)成Unit類型相當(dāng)于C語言里的void函數(shù)。我試下來最大的改變是心理層面的用C寫的時(shí)候我總擔(dān)心指針傳錯(cuò)、數(shù)組越界、malloc沒釋放改用MoonBit后數(shù)組越界會(huì)在運(yùn)行時(shí)拋出明確錯(cuò)誤寫變量也不用考慮指針的二級(jí)跳整個(gè)思考從“操作內(nèi)存”變成了“操作邏輯”。3.3 模式匹配帶來的轉(zhuǎn)型寫法命令式版本只是MoonBit的其中一面。MoonBit真正讓我眼前一亮的是模式匹配它能把“分情況討論”寫得非常優(yōu)雅。比如我們臨時(shí)要對(duì)數(shù)組里某一個(gè)區(qū)間做點(diǎn)判斷C語言只能if-elseMoonBit可以用match寫fn classify(x: Int) - String { match x { 0 zero 1 | 2 small _ large } }這種表達(dá)方式在寫分區(qū)邏輯的時(shí)候可能不明顯但當(dāng)你用函數(shù)式思路去重新審視快排時(shí)模式匹配就成了主要的代碼組織手段。這也是C語言做不到的事情屬于語言能力天花板帶來的差異。4. 函數(shù)式思路這類語言給了你更多選擇4.1 用模式匹配寫分區(qū)既然MoonBit支持函數(shù)式風(fēng)格自然可以用列表而不是數(shù)組來寫快排。下面是基于不可變列表的版本fn quick_sort_list(xs: List[Int]) - List[Int] { match xs { Nil Nil Cons(pivot, rest) { let less rest.filter(fn (x) { x pivot }) let greater rest.filter(fn (x) { x pivot }) quick_sort_list(less) Cons(pivot, Nil) quick_sort_list(greater) } } }這段代碼充分展示了寫法上的差異。C語言版本需要手動(dòng)維護(hù)low和high下標(biāo)需要三個(gè)函數(shù)配合這里一個(gè)quick_sort_list就完成了全部工作。它的思路是列表為空就返回空列表非空取第一個(gè)元素當(dāng)基準(zhǔn)pivot剩下部分rest分成兩撥——小于等于pivot的進(jìn)less大于pivot的進(jìn)greater然后遞歸排序less和greater最后把三部分拼起來。這個(gè)寫法和傳統(tǒng)的“快排”有一點(diǎn)點(diǎn)不同它需要額外分配less、greater兩個(gè)新列表然后拼接而不再是原地排序?？臻g復(fù)雜度更高但代碼表達(dá)力極強(qiáng)幾乎是把算法定義直接寫在代碼里。對(duì)學(xué)習(xí)和理解算法本質(zhì)來說這種寫法反而更清楚。4.2 不可變數(shù)據(jù)對(duì)算法的影響這里有個(gè)概念必須說透為什么函數(shù)式寫法要用列表拼接而不是原地交換因?yàn)榱斜硎遣豢勺兊?。Cons(pivot, Nil)創(chuàng)建新列表后原列表不會(huì)變。所有變換都是生成新數(shù)據(jù)。這樣做的好處是數(shù)據(jù)不可變讓程序更容易推理不會(huì)有任何隱藏的副作用代價(jià)是排序不再是O(1)附加空間而是需要O(n)級(jí)別的新列表分配。所以函數(shù)式快排在純性能上不如C語言的原地快排但它在并發(fā)、調(diào)試、可讀性上有優(yōu)勢(shì)。你不需要擔(dān)心多個(gè)函數(shù)共享同一個(gè)數(shù)組時(shí)互相踩內(nèi)存也不需要關(guān)心交換操作會(huì)不會(huì)破壞數(shù)據(jù)內(nèi)部的一致性。對(duì)工程實(shí)踐而言很多場(chǎng)景更看重這種確定性而不是極致性能。4.3 兩種風(fēng)格的取舍MoonBit里命令式快排和函數(shù)式快排可以同時(shí)存在。同一個(gè)語言生態(tài)里支持兩種范式意味著你可以按需選擇底層性能敏感的模塊用命令式業(yè)務(wù)邏輯復(fù)雜、需要高可維護(hù)性的模塊用函數(shù)式。在實(shí)際項(xiàng)目中我個(gè)人建議排序這類基礎(chǔ)算法數(shù)據(jù)量大時(shí)用命令式數(shù)組版本數(shù)據(jù)量小、或瓶頸不在性能而是迭代速度時(shí)用函數(shù)式列表版本。這不是“要么選A要么選B”的問題而是工具箱里有更大的選擇空間比C語言靈活得多。5. 寫法對(duì)比同樣的邏輯不同的世界觀5.1 對(duì)照表從語法到運(yùn)行時(shí)把C語言和MoonBit兩個(gè)版本放在同一個(gè)表格里差異更直觀對(duì)比維度C語言MoonBit函數(shù)傳參指針、數(shù)組首地址需要自己維護(hù)長(zhǎng)度數(shù)組自帶長(zhǎng)度類型系統(tǒng)定位更準(zhǔn)確交換變量用指針解引用手動(dòng)寫temp交換邏輯傳數(shù)組和下標(biāo)語法更貼近意圖分區(qū)實(shí)現(xiàn)維護(hù)low/high、手動(dòng)處理邊界下標(biāo)同思路但越界檢查運(yùn)行時(shí)兜底遞歸寫法調(diào)用自身深度大時(shí)棧溢出命令式同樣可遞歸也可以寫函數(shù)式避免原地狀態(tài)數(shù)據(jù)修改所有人共享同一個(gè)數(shù)組互相影響可變數(shù)組可原地改不可變列表可安全共享錯(cuò)誤處理返回值約定容易忽略O(shè)ption/Result等類型出錯(cuò)時(shí)顯式處理編譯目標(biāo)原生機(jī)器碼、MCU、嵌入式主要為WebAssembly也能各種后端內(nèi)存管理malloc/free手動(dòng)管理GC自動(dòng)管理極少需要手動(dòng)裸指針表達(dá)范式命令式為主命令式和函數(shù)式都能寫模式匹配是亮點(diǎn)這張表說明一件事C語言和MoonBit不是“誰替代誰”的關(guān)系而是兩種不同世界觀。C語言的世界里你在管理機(jī)器資源MoonBit的世界里你在描述問題和邏輯。5.2 性能與取舍的實(shí)際觀察性能是繞不開的話題。C語言經(jīng)過編譯器優(yōu)化之后快排的開銷可以壓到非常低循環(huán)里只有比較和交換沒有多余的對(duì)象分配內(nèi)存訪問完全連續(xù)緩存友好。實(shí)測(cè)下來對(duì)一個(gè)100萬元素的隨機(jī)整數(shù)數(shù)組優(yōu)化后的C快排通常幾十毫秒內(nèi)完成而MoonBit命令式版本因?yàn)榫幾g目標(biāo)的不同以及GC帶來的潛在分配開銷性能上會(huì)有差距。函數(shù)式列表版本由于要反復(fù)創(chuàng)建子列表耗時(shí)會(huì)更明顯。但注意這不是全貌。如果你的目標(biāo)是WebAssembly環(huán)境C語言雖然勉強(qiáng)能編譯過去但工具鏈和膠水代碼得自己搞一套MoonBit則天生面向Wasm寫完之后編譯目標(biāo)就是Wasm生態(tài)整合更順手。所以在瀏覽器插件、Web端數(shù)據(jù)處理這類場(chǎng)景里MoonBit“開箱即用”的開發(fā)效率優(yōu)勢(shì)會(huì)更突出。說到底性能是場(chǎng)景的函數(shù)。常年寫嵌入式、車控、內(nèi)核的C依然是王者做云原生、Web端、邊緣計(jì)算并用Wasm部署邏輯的MoonBit這類新語言能省掉大量工程瑣事。5.3 什么時(shí)候選誰更劃算選型這件事我一直的建議是看瓶頸在哪。如果你的項(xiàng)目瓶頸是內(nèi)存、功耗、指令周期必須精確控制每一個(gè)字節(jié)那就老老實(shí)實(shí)用C。你的環(huán)境可能沒有操作系統(tǒng)、沒有動(dòng)態(tài)內(nèi)存、沒有GCC語言是無可替代的。如果你在做一個(gè)Web服務(wù)或前端工具需要快速迭代、降低出錯(cuò)率且目標(biāo)環(huán)境支持WasmMoonBit就比C劃算得多因?yàn)樗车舻氖悄阕铑^疼的那部分內(nèi)存安全問題同時(shí)保留了接近命令式語言的性能形態(tài)。至于學(xué)習(xí)順序我仍然建議先學(xué)C。不把指針、遞歸、內(nèi)存這些底層概念摸清楚你很難真正理解MoonBit帶來的“安全”和“便捷”到底值多少。反過來如果你只會(huì)C、沒接觸過函數(shù)式概念MoonBit則是一個(gè)溫和的入口它不像Haskell那樣徹底抽象命令式寫法仍然可用學(xué)習(xí)曲線相對(duì)平緩。6. 踩坑記錄與排查思路6.1 C語言常見的快排翻車點(diǎn)我在學(xué)習(xí)階段和實(shí)際項(xiàng)目里踩過不少坑整理幾條最典型的重復(fù)元素導(dǎo)致死循環(huán)。有些分區(qū)寫法里如果arr[j] pivot時(shí)i就一直走重復(fù)元素會(huì)被反復(fù)交換極端情況下遞歸深度爆炸。Lomuto方案用號(hào)劃分基本能規(guī)避這類問題但遇到大量重復(fù)元素時(shí)性能仍然下降。更快的方法是三分區(qū)快排把等于pivot的元素單獨(dú)放中間兩邊只處理嚴(yán)格小于和嚴(yán)格大于的實(shí)測(cè)對(duì)重復(fù)數(shù)據(jù)非常有效。幾乎有序的數(shù)組觸發(fā)最壞情況。順序數(shù)組配上選最后元素當(dāng)基準(zhǔn)復(fù)雜度直接O(n^2)。解決辦法是三數(shù)取中取low、mid、high三個(gè)位置的中位數(shù)當(dāng)基準(zhǔn)然后先把基準(zhǔn)換到high-1位置再做分區(qū)。這個(gè)方法實(shí)現(xiàn)起來不復(fù)雜收益卻很明顯。動(dòng)態(tài)數(shù)組的free遺漏。用malloc分配數(shù)組排序完忘了free長(zhǎng)期運(yùn)行的程序內(nèi)存只漲不降。在PC上短時(shí)間跑看不出來在服務(wù)端等常駐進(jìn)程里就是事故現(xiàn)場(chǎng)。6.2 MoonBit寫算法時(shí)遇到的問題MoonBit雖然現(xiàn)代也不是銀彈。我練習(xí)時(shí)遇到兩個(gè)問題一是函數(shù)式版快排在列表拼接處用操作符拼接列表的時(shí)間復(fù)雜度是O(n)因?yàn)橐闅v左邊列表到尾部再接上右邊。如果數(shù)據(jù)量大你會(huì)明顯感到這個(gè)版本慢。解決方式就是前面說的對(duì)大數(shù)據(jù)量改用數(shù)組版本別用列表硬撐。二是泛型寫法還不像C模板那么成熟。C語言可以對(duì)int寫過一份代碼再用宏或類型別名擴(kuò)展到其他類型MoonBit有泛型和Trait可以把a(bǔ)rr: Array[Int]改成arr: Array[T]并約束T實(shí)現(xiàn)Compare特等但寫起來需要額外理解Trait的概念初學(xué)者容易卡住。建議初學(xué)時(shí)先用Int類型跑通再逐步抽象。6.3 給初學(xué)者的遷移建議如果你正在學(xué)C語言快排又對(duì)MoonBit感興趣我的建議是分三步走第一步先閉上眼睛把C語言快排背下來然后默寫確保你對(duì)指針傳參、遞歸邊界、分區(qū)下標(biāo)這幾件事有肌肉記憶。第二步按照第3節(jié)的方式把C版本逐行翻譯成MoonBit命令式版本跑通測(cè)試用例。這個(gè)過程中你會(huì)體會(huì)到哪些語法差異是表面的、哪些是深層的。第三步再實(shí)現(xiàn)一遍函數(shù)式列表版本用模式匹配重寫。到這一步你的目標(biāo)不再是從內(nèi)存視角理解快排而是從數(shù)據(jù)流視角理解快排。三步走完之后你等于掌握了同一算法的三套表達(dá)方式。以后不管遇到C類語言、Rust這類現(xiàn)代系統(tǒng)語言、還是函數(shù)式語言都能快速寫出遞歸和快排邏輯。這種“邏輯不變、表達(dá)各異”的體會(huì)才是這次對(duì)比實(shí)驗(yàn)最大的收獲。我在實(shí)際對(duì)比中的另一個(gè)體會(huì)是語言特性確實(shí)會(huì)影響你第一時(shí)間想到的方案。寫C的時(shí)候我腦子里第一反應(yīng)是“維護(hù)兩個(gè)下標(biāo)、交換內(nèi)存”寫MoonBit時(shí)我腦子里第一反應(yīng)變成了“這個(gè)邏輯能不能用match拆解”。如果你也想梳理自己的編程思維強(qiáng)烈建議找?guī)讉€(gè)經(jīng)典算法用兩種風(fēng)格差異足夠大的語言各寫一遍。寫完之后你會(huì)更明白自己適合什么場(chǎng)景也更理解那些看起來高大上的語言設(shè)計(jì)到底解決了什么真實(shí)問題。