我去年處理過一個(gè)挺有意思的活兒某內(nèi)部工具需要在上億條日志里按時(shí)間窗口做聚合統(tǒng)計(jì)數(shù)據(jù)的時(shí)間戳全部落在最近三個(gè)月內(nèi)。一開始我按教科書思路上了紅黑樹、跳表這類“高級(jí)”結(jié)構(gòu)結(jié)果在真實(shí)數(shù)據(jù)上跑得還不如后來換上的一個(gè)普通數(shù)組快。原因很簡單——我知道時(shí)間戳的確定范圍明明可以用直接定址的思路偏要去搞那些對(duì)范圍無感的通用結(jié)構(gòu)。這件事給我的教訓(xùn)很直接算法選型先看數(shù)據(jù)范圍范圍一旦已知很多“復(fù)雜度更優(yōu)”的通用方案反而會(huì)被一個(gè)最樸素的數(shù)組下標(biāo)干掉。這篇內(nèi)容就想把“根據(jù)已知數(shù)據(jù)范圍選擇算法”這個(gè)話題掰開揉碎。我適合以下人群閱讀寫業(yè)務(wù)代碼時(shí)經(jīng)常面對(duì)確定值域的數(shù)據(jù)比如用戶ID、訂單號(hào)、IP段、時(shí)間戳、固定枚舉狀態(tài)卻不太確定該用哈希、樹還是數(shù)組的人刷題或做競(jìng)賽時(shí)知道數(shù)據(jù)范圍卻總選錯(cuò)算法的人以及工作中需要評(píng)估算法選型、做性能優(yōu)化的人?？赐昴憔兔靼追秶畔⒉皇强捎锌蔁o的細(xì)節(jié)而是能把算法復(fù)雜度從 O(n log n) 拉到 O(n) 甚至 O(1) 的關(guān)鍵鑰匙。1. “已知數(shù)據(jù)范圍”為什么能改變算法抉擇——從時(shí)間復(fù)雜度的盲區(qū)說起大多數(shù)人學(xué)算法時(shí)最先接觸的是時(shí)間復(fù)雜度的漸進(jìn)分析。這個(gè)工具很強(qiáng)大但它有一個(gè)致命盲區(qū)復(fù)雜度公式里往往只出現(xiàn) n元素個(gè)數(shù)而不出現(xiàn) U值域大小。結(jié)果就是當(dāng)問題里同時(shí)存在 n 和 U 這兩個(gè)維度時(shí)僅看 n 會(huì)嚴(yán)重誤導(dǎo)選型方向。1.1 一個(gè)反直覺的例子知道范圍后“笨算法”反而最快先看一個(gè)最經(jīng)典的場(chǎng)景給 10^7 個(gè)整數(shù)排序這 10^7 個(gè)數(shù)全部落在區(qū)間 [0, 10^5] 內(nèi)。常規(guī)思路是快速排序或歸并排序復(fù)雜度 O(n log n)。n 10^7 時(shí)10^7 × log2(10^7) ≈ 10^7 × 23.25大約 2.3 億次基本操作。跑起來一般需要幾百毫秒到一秒多具體看語言和優(yōu)化情況。但如果我知道所有數(shù)都落在 [0, 10^5] 這個(gè)有限范圍內(nèi)可以用計(jì)數(shù)排序// 已知arr[0..n-1] 中所有元素滿足 0 arr[i] U_MAX (U_MAX 100000) void countingSort(vectorint arr, int U_MAX) { vectorint cnt(U_MAX 1, 0); for (int x : arr) cnt[x]; int idx 0; for (int v 0; v U_MAX; v) { while (cnt[v]--) arr[idx] v; } }這段代碼的復(fù)雜度是 O(n U)其中 U 10^5。兩層循環(huán)加起來只有 10^7 10^5 的量級(jí)大約 1010 萬次操作比快速排序的 2.3 億次少了二十多倍。這里的關(guān)鍵不是“計(jì)數(shù)排序打敗快排”而是“在范圍已知的情況下復(fù)雜度分析必須同時(shí)考慮 n 和 U 兩個(gè)變量否則會(huì)得到錯(cuò)誤結(jié)論”。如果你只會(huì)背“快排就是 O(n log n) 最優(yōu)”面對(duì)這種確定值域的數(shù)據(jù)就會(huì)錯(cuò)過一個(gè)數(shù)量級(jí)的性能提升。1.2 數(shù)據(jù)范圍如何改變“最優(yōu)解”的定義數(shù)據(jù)范圍至少包含以下幾個(gè)維度每個(gè)維度都直接影響選型維度含義示例影響的算法選擇值域上界 U元素最大可能取值0 ~ 10^5、0 ~ 2^31-1決定能否用數(shù)組直接定址連續(xù)性值域是否基本連續(xù)用戶ID是否從0遞增分配決定數(shù)組是否浪費(fèi)空間密集程度實(shí)際出現(xiàn)的元素?cái)?shù)量 vs 值域大小稀疏與密集數(shù)組 vs 哈希表重復(fù)程度是否有大量重復(fù)元素狀態(tài)枚舉值計(jì)數(shù)排序 vs 比較排序偏移量最小值是否遠(yuǎn)大于0時(shí)間戳、ID從大數(shù)開始是否做映射、平移分布形態(tài)均勻、偏斜、冪律長尾數(shù)據(jù)基數(shù)排序 vs 計(jì)數(shù)排序舉一個(gè)直觀類比假設(shè)你要給一萬個(gè)盒子貼上對(duì)應(yīng)編號(hào)的標(biāo)簽每個(gè)盒子上的編號(hào)從 1 到 10000。如果你提前知道“編號(hào)范圍就是 1 到 10000”最蠢也最有效的辦法是準(zhǔn)備一萬個(gè)空位看見幾號(hào)盒子就放到幾號(hào)位子上如果你不知道編號(hào)范圍就得把所有盒子排成一排一個(gè)個(gè)比較交換排序。前者就是“范圍已知”的威力——你不需要通過互相比較來推斷位置而是直接把“值”當(dāng)成“位置”。理解了這個(gè)前提下面就可以進(jìn)入實(shí)際操作層面的拆解了。2. 四個(gè)高頻場(chǎng)景的選型拆解排序、查找、去重、素?cái)?shù)處理范圍信息對(duì)算法選型的影響在排序、查找、去重、素?cái)?shù)這四個(gè)場(chǎng)景里體現(xiàn)得最充分。我分別把它們的決策邏輯講透。2.1 排序場(chǎng)景計(jì)數(shù)排序碾壓快排的邊界在哪里計(jì)數(shù)排序的思路本質(zhì)上是“用空間換時(shí)間”它把數(shù)據(jù)本身當(dāng)作數(shù)組下標(biāo)先統(tǒng)計(jì)每個(gè)值出現(xiàn)多少次再按值從小到大把元素回填。它成立的條件很苛刻但也很明確元素必須是非負(fù)整數(shù)值域 U 不能太大而且你能容忍排序后的元素只是數(shù)值有序大多時(shí)候這足夠了。當(dāng) U 遠(yuǎn)小于 n 時(shí)計(jì)數(shù)排序幾乎無敵當(dāng) U 和 n 同量級(jí)比如 n 10^7、U 10^7那么 O(n U) 和 O(n log n) 差別不大這時(shí)反而要考慮內(nèi)存占用和常數(shù)因子。一個(gè)實(shí)際的選擇標(biāo)準(zhǔn)可以寫成U ≤ 10^7內(nèi)存允許 4U 字節(jié)int 數(shù)組時(shí)優(yōu)先考慮計(jì)數(shù)排序如果數(shù)據(jù)中有負(fù)數(shù)先做平移把最小值變?yōu)?如果不只是簡單排序還需要按其他鍵二次排序改用基數(shù)排序或“計(jì)數(shù)排序穩(wěn)定歸并”。基數(shù)排序值得多說一句。它是計(jì)數(shù)排序的推廣把整數(shù)按位拆成多個(gè)關(guān)鍵字每一位分別做一次穩(wěn)定的計(jì)數(shù)排序。比如 32 位整數(shù)可以按 8 位一組分成 4 輪。這樣即使 U 很大接近 2^32只要數(shù)據(jù)本身分布均勻也能在 O(n × 位數(shù)/組大小) 內(nèi)排完大約就是 O(4n)。所以面對(duì) 0 到 2^32-1 的大范圍整數(shù)排序基數(shù)排序是比快速排序更貼近“工程最優(yōu)”的選擇之一。這里有一個(gè)需要警惕的誤區(qū)有些資料說“計(jì)數(shù)排序適合小范圍”但沒定義“小”到底是多少。在很多競(jìng)賽和面試場(chǎng)景里值域 10^6 以下才算“小”但在真實(shí)系統(tǒng)里如果內(nèi)存很充裕10^8 也能硬上需要約 400MB 內(nèi)存。我曾經(jīng)在某數(shù)據(jù)分析腳本里就真用 10^8 的 int 數(shù)組做過一次計(jì)數(shù)統(tǒng)計(jì)明顯比跑外部排序快得多——前提是這臺(tái)機(jī)器內(nèi)存夠大腳本是短生命周期的。2.2 查找場(chǎng)景二分、哈希、還是直接數(shù)組下標(biāo)查找問題里“范圍已知”的價(jià)值被很多人低估了。當(dāng)數(shù)據(jù)范圍是有限的連續(xù)整數(shù)時(shí)最猛的查找結(jié)構(gòu)其實(shí)是一個(gè)普通的數(shù)組。假設(shè)你有一個(gè)系統(tǒng)用戶ID從 0 遞增分配最多 10^7 個(gè)用戶需要根據(jù) ID 快速查到用戶信息。此時(shí)直接開一個(gè)大小為 10^7 的數(shù)組下標(biāo)就是 ID# 建立直接按下標(biāo)存 users [None] * MAX_USER_ID def add_user(uid, info): users[uid] info def get_user(uid): return users[uid]查找復(fù)雜度為 O(1)而且沒有任何哈希沖突、沒有鏈表指針跳轉(zhuǎn)、沒有緩存缺失問題。相比之下哈希表雖然理論也是 O(1)但它需要計(jì)算哈希、處理沖突、可能觸發(fā)擴(kuò)容常數(shù)因子比數(shù)組直接定址大不少紅黑樹和跳表理論 O(log n)更是差了一個(gè)數(shù)量級(jí)。二分查找則適合另一種場(chǎng)景數(shù)據(jù)本身已經(jīng)有序但你不知道數(shù)據(jù)的分布密度只知道范圍。比如你要在一個(gè)已排序的數(shù)組中查找某個(gè)值二分查找完全不關(guān)心值域大小只關(guān)心元素個(gè)數(shù) n這是它的天然優(yōu)勢(shì)。所以查找場(chǎng)景的決策邏輯大致如下值是連續(xù)或接近連續(xù)的整數(shù)且下界不大 → 直接數(shù)組定址值域稀疏但已知上下界 → 先離散化再用二分或哈希值域未知、數(shù)據(jù)靜態(tài)有序 → 二分查找值域未知、數(shù)據(jù)動(dòng)態(tài)插入刪除 → 哈希表或平衡樹。我不是說哈希表不好哈希表在很多場(chǎng)景確實(shí)是全能選手。但“范圍已知”這個(gè)信息經(jīng)常能把哈希表降級(jí)成一個(gè)更簡單的數(shù)組省掉一堆隱形成本。尤其是高并發(fā)讀取場(chǎng)景數(shù)組定址的局部性好CPU 緩存友好性能優(yōu)勢(shì)非常明顯。2.3 去重場(chǎng)景位圖與布爾數(shù)組的空間賬去重問題的本質(zhì)是“判斷某個(gè)值是否出現(xiàn)過”。如果值的范圍已知最簡單的辦法是布爾數(shù)組甚至位圖。給一個(gè)具體例子。某系統(tǒng)需要過濾 10^9 條請(qǐng)求里的重復(fù)設(shè)備編號(hào)設(shè)備編號(hào)是 32 位非負(fù)整數(shù)最大值約 4×10^9——這個(gè)范圍太大直接開 int 數(shù)組需要 16GB顯然不現(xiàn)實(shí)。但如果換一個(gè)角度我們不關(guān)心某個(gè)編號(hào)出現(xiàn)了多少次只關(guān)心“是否出現(xiàn)過”就可以用位圖來表示每個(gè)編號(hào)只占 1 bit4×10^9 個(gè)編號(hào)對(duì)應(yīng)約 500MB。雖然也不小但已經(jīng)比 int 數(shù)組省了 32 倍配合分段加載、多線程處理很多場(chǎng)景是可行的。如果范圍再小一些比如設(shè)備編號(hào)實(shí)際是 MAC 地址后 24 位0 ~ 2^24-1約 1600 萬個(gè)取值位圖只需要 2MB。直接用 bitset 或手工字節(jié)數(shù)組都能輕松裝進(jìn)內(nèi)存。// 位圖去重假設(shè)值域?yàn)?[0, MAX_VAL) vectoruint8_t bitmap((MAX_VAL 7) / 8, 0); bool markIfFirstSeen(uint32_t val) { uint32_t byteIdx val 3; uint8_t bitMask 1 (val 7); bool first !(bitmap[byteIdx] bitMask); bitmap[byteIdx] | bitMask; return first; }哈希 Set 也能去重但它有兩個(gè)問題內(nèi)存占用大每個(gè)元素除了值本身還有哈希桶、節(jié)點(diǎn)指針、負(fù)載因子預(yù)留空間而且哈希碰撞后還會(huì)退化。所以當(dāng)范圍可控時(shí)位圖在內(nèi)存和時(shí)間上都是更優(yōu)選擇。去重場(chǎng)景的選型邏輯可以總結(jié)為值域 ≤ 10^7直接用布爾數(shù)組約 10MB值域 ≤ 10^9考慮位圖約 125MB還是要評(píng)估內(nèi)存預(yù)算值域 10^9 且實(shí)際元素?cái)?shù)量少 → 哈希 Set 或布隆過濾器允許誤判、且數(shù)據(jù)量極大 → 布隆過濾器它本質(zhì)上也依賴“范圍預(yù)估”來設(shè)定位數(shù)組大小和哈希函數(shù)個(gè)數(shù)。布隆過濾器這里尤其值得展開它需要的位數(shù)組大小依賴于你預(yù)估的元素?cái)?shù)量 n 和可接受的誤判率 p。公式是 m ≈ -(n × ln p) / (ln 2)^2。這不就是“根據(jù)已知數(shù)據(jù)范圍預(yù)估規(guī)模選擇參數(shù)”的典型例子嗎范圍估計(jì)得越準(zhǔn)布隆過濾器就越省內(nèi)存且誤判可控。2.4 素?cái)?shù)處理大范圍區(qū)間篩的偏移存儲(chǔ)技巧素?cái)?shù)問題看起來和“數(shù)據(jù)范圍選型”沒直接關(guān)系但我做某次數(shù)論相關(guān)需求時(shí)踩過坑這里必須分享一下。如果需求是求區(qū)間 [L, R] 內(nèi)的所有素?cái)?shù)L 和 R 可能很大比如 L 10^9R 10^9 10^7。此時(shí)你沒法直接開一個(gè)大小為 R1 的布爾數(shù)組來篩——那要 1GB 以上空間。但區(qū)間長度 R - L 1 只有 10^7是可以輕松放進(jìn)內(nèi)存的。做法是埃氏篩的“區(qū)間偏移”先用普通埃氏篩把不超過 sqrt(R) 的素?cái)?shù)全部找出來再用這些素?cái)?shù)去篩 [L, R] 區(qū)間內(nèi)合數(shù)但數(shù)組下標(biāo)只需要從 0 到 R-Lvectorbool isPrime(R - L 1, true); // 先用經(jīng)典篩法得到所有 sqrt(R) 的素?cái)?shù) primes for (int p : primes) { // 找到 [L, R] 中第一個(gè)能被 p 整除的數(shù) long long start max((long long)p * p, ((L p - 1) / p) * p); for (long long j start; j R; j p) { if (j ! p) isPrime[j - L] false; } }思路核心就是把值域范圍從 [0, R] 偏移成 [0, R-L]也就是“已知區(qū)間長度而不是已知絕對(duì)最大值”。這類偏移技巧在算法競(jìng)賽和工程里都能見到本質(zhì)上是讓你不要被問題表面的大數(shù)值嚇到——多問一句“我關(guān)心的范圍到底是從哪到哪、跨度有多大”選型思路就會(huì)完全不一樣。類似的還有線性篩歐拉篩它在需要頻繁查詢前綴素?cái)?shù)個(gè)數(shù)、或需要維護(hù)每個(gè)數(shù)的最小質(zhì)因子時(shí)更好用但代價(jià)是需要完整表。如果范圍已知且不大比如 U ≤ 10^7線性篩是首選范圍很大但只查某個(gè)區(qū)間區(qū)間篩配合偏移才是正解。3. 范圍已知不等于一切稀疏、偏移、大值域的邊界處理上一章講的是“范圍已知帶來的紅利”實(shí)際操作中更常見的卻是“范圍似乎知道了但沒那么簡單”。我把最常見的邊界情況列一下。3.1 稀疏范圍是陷阱值域大而實(shí)際元素少最常見的翻車場(chǎng)景是系統(tǒng)文檔告訴你“編號(hào)范圍是 1 到 10^9”于是你想開一個(gè) 10^9 的數(shù)組然后發(fā)現(xiàn)內(nèi)存直接爆炸。但你仔細(xì)看看數(shù)據(jù)實(shí)際出現(xiàn)的編號(hào)總共只有 10^4 個(gè)——這就是稀疏范圍。在稀疏范圍面前直接定址不可行應(yīng)該轉(zhuǎn)向離散化把所有出現(xiàn)過的值收集起來排序去重后映射成 0 到 m-1 的緊湊下標(biāo)再用數(shù)組或樹狀數(shù)組處理。比如你要對(duì)一堆區(qū)間做覆蓋次數(shù)統(tǒng)計(jì)編號(hào)是 10^9 量級(jí)的離散點(diǎn)。開數(shù)組不可能但把這些點(diǎn)離散化后問題規(guī)模就變成“實(shí)際點(diǎn)數(shù) m”所有基于范圍下標(biāo)的算法都能繼續(xù)用vectorint allVals originalVals; sort(allVals.begin(), allVals.end()); allVals.erase(unique(allVals.begin(), allVals.end()), allVals.end()); // 之后要查某個(gè) val先二分定位lower_bound(allVals.begin(), allVals.end(), val)這里“范圍已知”的信息并沒有失效而是換了一種用法范圍決定了你能預(yù)判離散化后 m 的大小上限進(jìn)而決定是選樹狀數(shù)組還是線段樹、是選普通數(shù)組還是哈希。離散化后的查找用二分 O(log m)也可以再套哈希 O(1)如果 m 不超過 10^6甚至可以直接開一個(gè)大小為 m 的數(shù)組配合“反離散化映射”。我個(gè)人的經(jīng)驗(yàn)是在做任何依賴“值域大小 U”的算法之前先統(tǒng)計(jì)“實(shí)際互異元素?cái)?shù)量 m”。如果 m 遠(yuǎn)小于 U走離散化如果 m 和 U 同量級(jí)且 U 可控才考慮直接開數(shù)組。3.2 負(fù)數(shù)與起始偏移讓下標(biāo)從0開始的三種映射方式已知范圍是從負(fù)數(shù)開始或者最小值遠(yuǎn)大于 0 時(shí)不能直接使用原始值作為數(shù)組下標(biāo)。處理辦法很簡單建立從“原始值”到“數(shù)組下標(biāo)”的映射常見有三種。第一種是整體平移。如果范圍是 [-10^5, 10^5]把所有值加上 10^5變成 [0, 2×10^5]再開數(shù)組。這種方式最簡單但前提是范圍不大否則平移只是把問題延后內(nèi)存照樣過大。第二種是取?；蚬Ｓ成?。適用于大值域但稀疏的情況本質(zhì)上是哈希表不保證下標(biāo)連續(xù)。第三種是排序后二分定位。也就是前面說的離散化適合值域范圍大、但實(shí)際值集合固定且數(shù)量不多的查詢場(chǎng)景。這三種方式的選型判斷依據(jù)還是回到第一張表里那幾個(gè)維度范圍跨度、連續(xù)性、實(shí)際元素?cái)?shù)量。如果跨度小且連續(xù)平移開數(shù)組最優(yōu)跨度大且稀疏離散化加二分動(dòng)態(tài)插入且無法排序哈希。一個(gè)我曾經(jīng)忽略的細(xì)節(jié)做平移時(shí)一定要確認(rèn)映射后的最大值不超過數(shù)組邊界。比如值是 [10^6, 10^6 10^4]平移量是 10^6但有些人只平移了最小值卻忘了數(shù)組長度等于“最大值減最小值加一”導(dǎo)致越界訪問。測(cè)試時(shí)數(shù)據(jù)不靠邊界根本發(fā)現(xiàn)不了一旦上線就偶發(fā)崩潰非常難排查。3.3 分布不均時(shí)基數(shù)排序比計(jì)數(shù)排序更穩(wěn)計(jì)數(shù)排序在值域很小但分布極不均勻時(shí)有一個(gè)隱藏問題回填階段需要把所有值域遍歷一遍哪怕絕大多數(shù)值從來沒有出現(xiàn)過。如果 U 10^8n 10^6那么 O(n U) 實(shí)際約等于 1.01 億次操作大部分時(shí)間浪費(fèi)在空轉(zhuǎn)的 for 循環(huán)上。雖然也不算慢但內(nèi)存開銷已經(jīng)不小400MB 左右的 int 數(shù)組。此時(shí)可以考慮基數(shù)排序的變體按二進(jìn)制位分組做 LSD 排序。32 位整數(shù)按 8 位一桶只需 4 輪每輪 O(n)總共 O(4n)。它不要求值域連續(xù)只依賴于位寬。實(shí)測(cè)中當(dāng)數(shù)據(jù)非常集中比如所有數(shù)都在 0 到 2^20 附近時(shí)基數(shù)排序依然穩(wěn)定而計(jì)數(shù)排序則會(huì)因?yàn)?U 大而吃虧或者因?yàn)?U 小而先要掃描全范圍。還有一個(gè)更實(shí)用的組合先根據(jù)高位做一次粗分桶把數(shù)據(jù)拆到若干個(gè)區(qū)間里區(qū)間內(nèi)部如果值域跨度已經(jīng)很小再對(duì)每個(gè)區(qū)間單獨(dú)做計(jì)數(shù)排序。這種“桶排序 計(jì)數(shù)排序”的思路在很多大數(shù)據(jù)排序系統(tǒng)里都能見到本質(zhì)就是利用數(shù)據(jù)范圍的層次性——外層看范圍分桶內(nèi)層看區(qū)間跨度再細(xì)化。3.4 時(shí)間與內(nèi)存的權(quán)衡bitset、壓縮與分段處理當(dāng)范圍 U 很大但你又想保留“范圍直接定址”的好處時(shí)內(nèi)存會(huì)成為瓶頸。這時(shí)有幾個(gè)工程手段值得掌握。位壓縮前面提過值域 U 的布爾數(shù)組至少 U 字節(jié)位圖只要 U/8 字節(jié)。例如 U 10^8布爾數(shù)組 100MB位圖 12.5MB差距非常明顯。分段處理如果一次性裝不下可以考慮按值域分段。比如值域 0 到 10^9我把范圍切成 100 段每段長度 10^7每次只加載一段到內(nèi)存處理處理完寫回結(jié)果再換下一段。這種方式犧牲了隨機(jī)訪問的便利性但能把“范圍已知”的優(yōu)勢(shì)從內(nèi)存受限場(chǎng)景中拯救出來。壓縮編碼當(dāng)數(shù)據(jù)的值域連續(xù)但分布極不均勻時(shí)可以用差值編碼、前綴和編碼等方式壓縮存儲(chǔ)。這已經(jīng)進(jìn)入數(shù)據(jù)結(jié)構(gòu)的深層定制了一般只在存儲(chǔ)成本極高時(shí)才會(huì)考慮。我的建議是先別急著上壓縮先用位圖和分段扛一扛絕大多數(shù)場(chǎng)景已經(jīng)夠用。4. 從一次翻車經(jīng)歷談選型前必問的六個(gè)問題講完了原理我想用一段真實(shí)踩坑記錄收尾。某次我負(fù)責(zé)一個(gè)內(nèi)部統(tǒng)計(jì)系統(tǒng)需求是給海量請(qǐng)求按來源IP段聚合計(jì)數(shù)。IP是IPv4四個(gè)字節(jié)我當(dāng)時(shí)想當(dāng)然地以為“IPv4范圍就是 0 到 2^32-1均勻分布”于是一開始就準(zhǔn)備了一張大小為 2^32 的數(shù)組算一下 16GB直接超了內(nèi)存預(yù)算。后來又改成哈希表但因?yàn)?IP 段極不均勻地集中在少數(shù)幾個(gè)C段哈希表碰撞率很高性能又不行。最后我做了兩件事先用采樣統(tǒng)計(jì)出實(shí)際出現(xiàn)的IP段數(shù)量再把“IP地址范圍”轉(zhuǎn)換成“CIDR前綴范圍”按前綴長度分層處理。最終方案是高頻前綴用緊湊數(shù)組直接定址低頻稀疏部分用離散化加二分。整體內(nèi)存不到原來的十分之一性能還比哈希表快了三倍。這次經(jīng)歷讓我總結(jié)出選型前必問的六個(gè)問題也推薦給你問題目的不回答的后果值的確定上下界是什么判斷能否直接定址內(nèi)存浪費(fèi)或越界值域跨度多大實(shí)際出現(xiàn)多少互異值判斷稀疏程度直接開數(shù)組爆內(nèi)存值是連續(xù)還是離散分布是否均勻選擇計(jì)數(shù)排序、基數(shù)排序還是桶排序空轉(zhuǎn)/碰撞是否存在偏移、負(fù)數(shù)、大起始值決定是否平移/離散化下標(biāo)越界是否需要穩(wěn)定排序、隨機(jī)訪問、內(nèi)存受限決定工程約束算法正確但工程不可用最壞情況下的值域邊界是否可能突破預(yù)估決定是否留冗余上線后偶發(fā)崩潰這六個(gè)問題看著簡單但真到項(xiàng)目里很多人是在寫完代碼之后才開始考慮的順序反了。正確做法是寫算法前先做 5 分鐘的數(shù)據(jù)分析哪怕是粗略估算也遠(yuǎn)比憑感覺選結(jié)構(gòu)要可靠。選完算法之后還有一步容易被漏掉用多組不同規(guī)模的數(shù)據(jù)做基準(zhǔn)測(cè)試而不是只看理論復(fù)雜度。理論分析只告訴我們?cè)鲩L趨勢(shì)常數(shù)因子、緩存行為、內(nèi)存分配開銷只有實(shí)測(cè)才能暴露。具體做法我一般是這樣先把數(shù)據(jù)規(guī)模從小到大各測(cè)一輪比如 n 10^4、10^5、10^6、10^7同一規(guī)模下再測(cè)分布極不均勻的情況對(duì)比時(shí)間時(shí)順帶記錄內(nèi)存峰值如果理論曲線和實(shí)測(cè)曲線偏離超過一個(gè)數(shù)量級(jí)回頭檢查是不是忽略了對(duì)數(shù)項(xiàng)或線性掃描項(xiàng)。還是拿時(shí)間戳那個(gè)例子說。當(dāng)時(shí)我把直接定址數(shù)組換成“哈希 紅黑樹”理論上排序和聚合看起來都嚴(yán)謹(jǐn)?shù)珜?shí)測(cè)下來數(shù)組版本因?yàn)榫彺嬗押梅炊炝私咏粋€(gè)數(shù)量級(jí)。這個(gè)現(xiàn)象用大O符號(hào)很難解釋但在真實(shí)硬件上就是那么殘酷——常量因子、內(nèi)存局部性往往比漸進(jìn)復(fù)雜度更能決定一個(gè)系統(tǒng)的最終性能。而“范圍已知”恰好能讓你在更多場(chǎng)景里選擇那個(gè)常量極小、局部性極好的數(shù)組方案。最后一個(gè)我個(gè)人的實(shí)操習(xí)慣在代碼注釋里把“為什么選這個(gè)算法”寫下來。記錄數(shù)據(jù)范圍是多少、為什么認(rèn)為范圍可控、如果范圍翻十倍應(yīng)該怎么切換方案。這看起來像小事但對(duì)后來維護(hù)代碼的人來說包括三個(gè)月后的自己這比寫十行“這段代碼實(shí)現(xiàn)了XXX”有用得多。算法選型不是一錘子買賣數(shù)據(jù)范圍可能隨著業(yè)務(wù)增長而變化那時(shí)就是重新評(píng)估算法的時(shí)候。以上就是我根據(jù)已知數(shù)據(jù)范圍做算法選型的完整思路和實(shí)操經(jīng)驗(yàn)。信息密度確實(shí)不低但如果你在真實(shí)項(xiàng)目中遇到確定值域的數(shù)據(jù)回來看一眼這六個(gè)問題應(yīng)該能少走不少彎路。