您會感到有些奇怪：似乎在平日的編碼進(jìn)程中，單獨(dú)去留意數(shù)據(jù)結(jié)構(gòu)和算法已非必需，那為何還得依據(jù)場景來設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)和算法呢？存有這樣的念頭實(shí)屬正常，畢竟我們的確能夠察覺到，在實(shí)際的業(yè)務(wù)范疇里，需要我們開發(fā)人員直接進(jìn)行數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)的機(jī)遇愈發(fā)稀少。

例如：在互聯(lián)網(wǎng)服務(wù)場景之中，性能耗費(fèi)主要匯聚于數(shù)據(jù)庫的 CRUD 操作上，因而鮮有關(guān)注業(yè)務(wù)內(nèi)數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)的性能；隨著越來越多的核心業(yè)務(wù)算法內(nèi)置到芯片當(dāng)中，對于從事嵌入式研發(fā)工作的工程師而言，主要的工作重點(diǎn)落在了管理配置各類硬件資源方面，所以并不會時(shí)常設(shè)計(jì)和運(yùn)用數(shù)據(jù)結(jié)構(gòu)與算法；眾多語言以及標(biāo)準(zhǔn)庫當(dāng)中已然內(nèi)置了豐富的數(shù)據(jù)結(jié)構(gòu)與算法，不太需要開發(fā)人員親自去設(shè)計(jì)和開發(fā)；……

但實(shí)際上，我們過往所運(yùn)用的性能優(yōu)化手段（像是熱點(diǎn)代碼分析優(yōu)化、編譯器優(yōu)化等等），對于系統(tǒng)性能的提升是以百分制來衡量的，這屬于一種線性粒度的性能提升。舉個(gè)簡易的例子，倘若您在對代碼進(jìn)行 Profiling 分析之后，識別出了一個(gè)頻繁調(diào)用的熱點(diǎn)函數(shù)，將其內(nèi)聯(lián)或者優(yōu)化后性能提升能夠達(dá)到 3% 至 5%，就已然屬于相當(dāng)顯著的優(yōu)化提升了。而通過數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)來改良的系統(tǒng)性能，所獲取的性能收益極有可能是非線性的，甚至可能是指數(shù)級的。就拿典型的查找問題來講，使用鏈表的遍歷查找算法和數(shù)組向量的二分查找算法，在查找速度上的性能或許會有好幾倍的差距呢！

所以，合理地設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)與算法，對于軟件系統(tǒng)的性能提升而言極其關(guān)鍵當(dāng)然，也許您已經(jīng)系統(tǒng)地學(xué)習(xí)過數(shù)據(jù)結(jié)構(gòu)與算法，對相關(guān)的知識原理有著較為深入的領(lǐng)會，也可能您對于現(xiàn)有的數(shù)據(jù)結(jié)構(gòu)與算法的了解相對有限，但這都不會對您學(xué)習(xí)這節(jié)課的內(nèi)容造成影響。我僅僅聚焦于一個(gè)視角，那便是根據(jù)業(yè)務(wù)開發(fā)中數(shù)據(jù)特征和計(jì)算邏輯的典型差別，從性能維度出發(fā)，系統(tǒng)性地選取和設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)與算法，以此助力您在軟件編碼的過程中，更易于開發(fā)出高性能的軟件。那么接下來，我就從剖析計(jì)算機(jī)軟件執(zhí)行原理開始，引領(lǐng)您去知曉選擇不同的數(shù)據(jù)結(jié)構(gòu)與算法，會給系統(tǒng)性能帶來怎樣的影響。

數(shù)據(jù)結(jié)構(gòu)與算法選擇對性能的影響

提及數(shù)據(jù)結(jié)構(gòu)與算法的開銷，或許您首先想到的會是大 O 標(biāo)記表示法。誠然，這是一種極為重要的算法復(fù)雜度表示方式，然而這并非衡量數(shù)據(jù)結(jié)構(gòu)與算法性能的全部。

實(shí)際上，衡量數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)現(xiàn)復(fù)雜度，存在幾類較為常用的指標(biāo)，像是最優(yōu)時(shí)間開銷、最差時(shí)間開銷、平均時(shí)間開銷、空間使用開銷、攤銷時(shí)間開銷。此時(shí)您可能會問：平均時(shí)間開銷是決定系統(tǒng)負(fù)載的關(guān)鍵指標(biāo)，那是不是只需著重關(guān)注平均時(shí)間開銷就行？實(shí)則不然，不同的業(yè)務(wù)場景所關(guān)注的指標(biāo)各不相同。我為您舉幾個(gè)例子，您便會明白：在內(nèi)存資源極度受限的業(yè)務(wù)場景下，對空間使用開銷的關(guān)注度會更高；對于實(shí)時(shí)性要求極高的場景，通常重點(diǎn)關(guān)注的是最差時(shí)間開銷，而平均時(shí)間開銷的意義不大；針對關(guān)注最大吞吐量的業(yè)務(wù)系統(tǒng)，此時(shí)平均時(shí)間開銷則成為了最為重要的指標(biāo)。

所以，我們不能僅僅關(guān)注平均時(shí)間開銷，而是要關(guān)注對業(yè)務(wù)更具價(jià)值的指標(biāo)。那么接下來，您或許還會產(chǎn)生這樣的疑惑：是不是僅依據(jù)算法復(fù)雜度來選擇算法就行？答案是否定的，相同的算法復(fù)雜度并不意味著相同的性能。要知道，性能還會受到軟件編碼實(shí)現(xiàn)方式、數(shù)據(jù)結(jié)構(gòu)存儲特性等諸多方面的影響。例如對于二分查找算法來說，基于循環(huán)遍歷的實(shí)現(xiàn)和基于遞歸調(diào)用的實(shí)現(xiàn)，二者在性能上就會存在顯著差異。

首先我們來看一個(gè)類定義，其中包含了一個(gè)構(gòu)造函數(shù)和比較運(yùn)算符，代碼如下：

struct Kv
{
char const *key;
    unsigned int value;
    Kv(const char *key, unsigned int value) : //構(gòu)造函數(shù)
            key(key), value(value)
    {
    }
bool operator==(Kv const &rht)  // 比較運(yùn)算符，當(dāng)兩個(gè)對象實(shí)例比較時(shí)使用
    {
return (strcmp(key, rht.key) == 0) && (value == rht.value);
    }
};

那么針對這個(gè)類，我選擇了兩種數(shù)據(jù)結(jié)構(gòu)進(jìn)行記錄，然后使用相同的查詢算法來對比性能。

第一種數(shù)據(jù)結(jié)構(gòu)類型為數(shù)組：

Kv arrayKvs[] = {...}

然后，使用 STD 標(biāo)準(zhǔn)庫中的線性查找算法，算法復(fù)雜度為 O(n)，如下所示：

Kv *result = std::find(std::begin(arrayKvs), std::end(arrayKvs),  Kv("bbb", 2));

第二種數(shù)據(jù)結(jié)構(gòu)類型為鏈表：

std::list<Kv> listKvs;

然后，這里我使用的也是標(biāo)準(zhǔn)庫中的線性查找算法，算法復(fù)雜度為 O(n)，如下所示：

std::list<Kv>::iterator result = std::find(listKvs.begin(),listKvs.end(), Kv("bbb", 2));

至此，您不妨先思考一番，上述兩種實(shí)現(xiàn)選用了相同的算法，實(shí)現(xiàn)復(fù)雜度相同，那么它們的性能表現(xiàn)會是一致的嗎？答案顯然是否定的。

當(dāng)運(yùn)用數(shù)組時(shí)，順序訪問數(shù)據(jù)的局部性較高（數(shù)據(jù)內(nèi)存地址是連續(xù)的）；但使用鏈表時(shí)，鑒于鏈表中的元素位置并非相鄰，并且數(shù)據(jù)不連續(xù)，這就潛在致使內(nèi)存 Cache Miss（緩存未命中）的概率大幅增加，進(jìn)而導(dǎo)致性能開銷增大。

所以，單純的算法復(fù)雜度實(shí)際上無法精準(zhǔn)地反映性能，數(shù)據(jù)結(jié)構(gòu)對性能的影響亦十分巨大，而這一部分并未在算法復(fù)雜度上得到良好的體現(xiàn)。

OK，最后我們再來思考一個(gè)問題：選擇數(shù)據(jù)結(jié)構(gòu)與算法之后，軟件性能就決定了嗎？

答案也是否定的，因?yàn)閿?shù)據(jù)結(jié)構(gòu)和算法轉(zhuǎn)換成的二級制代碼執(zhí)行是否高效，會受到很多因素的影響，比如編碼實(shí)現(xiàn)、編譯優(yōu)化等。這里咱們再來分析一下上述業(yè)務(wù)場景中的比較邏輯：

bool Kv::operator==(Kv const &rht)
{
return (strcmp(key, rht.key) == 0) && (value == rht.value); 
/*先比較字符串key, 再比較數(shù)字value */
}

倘若在這個(gè)類的所有節(jié)點(diǎn)數(shù)據(jù)里，近乎所有的 value 值皆不相同，并且 key 的長度較大，那么我們能夠?qū)Υa中的比較順序予以調(diào)整，因?yàn)檎麛?shù)比較的效率更高，能夠進(jìn)一步提升性能。

總之，數(shù)據(jù)結(jié)構(gòu)與算法的不同編碼實(shí)現(xiàn)過程和方式，對于軟件的性能而言至關(guān)重要。您在軟件實(shí)現(xiàn)的進(jìn)程中，不但要留意數(shù)據(jù)結(jié)構(gòu)和算法的選取，還需要關(guān)注其具體的編碼實(shí)現(xiàn)過程，如此方能真正開發(fā)出高性能的軟件。

好了，在明白了數(shù)據(jù)結(jié)構(gòu)和算法怎樣影響軟件性能之后，接下來咱們就進(jìn)一步探討，如何依據(jù)領(lǐng)域數(shù)據(jù)的特征來挑選對應(yīng)的算法。

根據(jù)領(lǐng)域數(shù)據(jù)特征去選擇算法

可能你之前已經(jīng)發(fā)現(xiàn)了，我們從教科書上學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)與算法，通常都是標(biāo)準(zhǔn)的，但是在解決具體的業(yè)務(wù)問題時(shí)，我們需要處理的數(shù)據(jù)與算法卻經(jīng)常不是標(biāo)準(zhǔn)的。怎么個(gè)不標(biāo)準(zhǔn)法兒呢？我認(rèn)為主要體現(xiàn)在以下兩個(gè)方面。

一方面，很多場景的領(lǐng)域數(shù)據(jù)是不標(biāo)準(zhǔn)的。

在大 O 標(biāo)記法當(dāng)中，存在一個(gè)假定，即在任意的數(shù)據(jù)集中，通過軟件所實(shí)現(xiàn)的算法的運(yùn)行時(shí)間大致相同，然而實(shí)際上，不少算法對于數(shù)據(jù)的特性是極為敏感的。

例如針對排序算法，如果待排序的數(shù)據(jù)集已經(jīng)頗為接近有序狀態(tài)，那么相較于快速排序，選取直接插入排序算法的優(yōu)勢將會更大。咱們來看一個(gè)例子。

假設(shè)有一個(gè)數(shù)據(jù)集，其具有如下特點(diǎn)：數(shù)據(jù)集的規(guī)模為 10 萬條；數(shù)據(jù)集完全處于亂序狀態(tài)；這 10 萬條數(shù)據(jù)里，有 1/3 的數(shù)值小于 1000，另外 1/3 的數(shù)值在 1000 到 2000 之間，還有 1/3 的數(shù)值大于 2000 。

那么此刻，您需要對這個(gè)數(shù)據(jù)集進(jìn)行完整排序，應(yīng)當(dāng)如何選擇算法呢？倘若您沒有關(guān)注到第三點(diǎn)特征，選擇了一個(gè)極為高效的排序算法后，確實(shí)也能夠?qū)⑺惴◤?fù)雜度降低到 O (N*log? N)。

但是當(dāng)您留意到了第三點(diǎn)特征時(shí)，上述的排序過程就能夠拆分為 3 個(gè)子數(shù)據(jù)集的排序，而后再將排序結(jié)果合并到一起?；谶@種方式實(shí)現(xiàn)之后，算法復(fù)雜度就能夠降低到 O (N/3log?(N/3)) * 3 = O(Nlog?(N/3))，從而能夠進(jìn)一步提升性能。

除此之外，針對上面這個(gè)業(yè)務(wù)場景，我們也不難想到，采用并發(fā)模式，將數(shù)據(jù)集中的 3 個(gè)子數(shù)據(jù)集的排序過程，通過子任務(wù)并發(fā)處理，進(jìn)而就能夠進(jìn)一步降低業(yè)務(wù)的處理時(shí)延。

所以說，我們務(wù)必要仔細(xì)挖掘領(lǐng)域數(shù)據(jù)的各類特性，只要挖掘出的領(lǐng)域數(shù)據(jù)中的特性越多，其潛在的優(yōu)化數(shù)據(jù)結(jié)構(gòu)與算法的性能空間也就越大。

另一方面，業(yè)務(wù)算法通常是不標(biāo)準(zhǔn)的。

要明白，除了領(lǐng)域數(shù)據(jù)不規(guī)范之外，業(yè)務(wù)場景里的算法通常也并非標(biāo)準(zhǔn)的，因而我們需要依據(jù)具體的業(yè)務(wù)邏輯來設(shè)計(jì)算法，以實(shí)現(xiàn)性能的最大化提升，而不能僅僅照搬現(xiàn)有的標(biāo)準(zhǔn)算法實(shí)現(xiàn)。我為您舉一個(gè)真實(shí)的例子，這是我曾經(jīng)參與設(shè)計(jì)的一個(gè)資源調(diào)度子系統(tǒng)中的算法案例。為了便于您理解，我將問題進(jìn)行了簡化和抽象，即如何從 1000 個(gè)用戶中，依照優(yōu)先級選出前 10 位用戶來進(jìn)行資源分配。

那么面對這個(gè)問題，您所選擇的算法方案會是什么呢？例如，會不會是以下這兩種方案：方案 1：依據(jù) 1000 個(gè)用戶的優(yōu)先級進(jìn)行全面排序，然后選取前 10 個(gè)；方案 

2：運(yùn)用冒泡排序算法，對 1000 個(gè)用戶全部遍歷 10 次，選出前 10 個(gè)用戶。

倘若您選擇方案 1，那么您將會浪費(fèi)大量不必要的計(jì)算機(jī)資源，性能必然會很差。而此時(shí)，您可能很容易就想到了方案 2，認(rèn)為這個(gè)方案效率頗高。那么方案 2 會是最優(yōu)的解決辦法嗎？顯然不是，我們再來看另外一個(gè)方案：方案 3：首先選取前 10 個(gè)用戶作為優(yōu)先級最高的 10 個(gè)，然后對 1000 個(gè)用戶全面遍歷一次，當(dāng)某個(gè)用戶的優(yōu)先級超過這 10 個(gè)用戶時(shí)，就更新到前 10 個(gè)用戶當(dāng)中。

現(xiàn)在您可以思考一下，方案 3 在性能上是否會優(yōu)于方案 2 呢？或者是否還有其他的算法實(shí)現(xiàn)方式？相信在認(rèn)真思考了這些問題之后，您就邁出了基于業(yè)務(wù)選擇和優(yōu)化算法的第一步。

實(shí)際上，對于這個(gè)案例而言，由于它的業(yè)務(wù)計(jì)算邏輯較為特殊，所以我們需要針對典型的計(jì)算邏輯，單獨(dú)設(shè)計(jì)算法的實(shí)現(xiàn)邏輯。因此，最終我們選擇了方案 3，通過針對前 10 位用戶的資源分配，取得了較好的性能效果。

好的，在依據(jù)業(yè)務(wù)邏輯定制化設(shè)計(jì)算法和實(shí)現(xiàn)之后，我們還需要綜合考量各種典型操作，才能夠選出最符合業(yè)務(wù)邏輯的數(shù)據(jù)結(jié)構(gòu)與算法，所以接下來咱們具體看一看。

權(quán)衡綜合各種操作選擇數(shù)據(jù)結(jié)構(gòu)與算法

我們知曉，數(shù)據(jù)結(jié)構(gòu)與算法往往是一對多的關(guān)系，在業(yè)務(wù)里，針對同一個(gè)數(shù)據(jù)結(jié)構(gòu)可能存在諸如排序、搜索等不同的算法業(yè)務(wù)邏輯。然而，同一個(gè)數(shù)據(jù)結(jié)構(gòu)在不同算法上的性能差異是較大的，所以此時(shí)，我們就需要綜合各類功能操作，進(jìn)而選擇數(shù)據(jù)結(jié)構(gòu)和算法。

舉個(gè)簡單的例子，對于數(shù)據(jù)結(jié)構(gòu)，頗為典型的方法包含了刪除、增加、查找元素等等。當(dāng)然數(shù)據(jù)結(jié)構(gòu)還能夠有眾多其他方法，只是每種方法的操作頻率各不相同，優(yōu)先級也有差別，比方說：在某些業(yè)務(wù)場景中，插入和刪除操作極為頻繁，而查詢操作極少，選擇鏈表類數(shù)據(jù)結(jié)構(gòu)進(jìn)行保存會較為適宜；在有些業(yè)務(wù)場景里，插入和刪除操作非常少，而查詢操作頻繁，故而考慮選擇數(shù)組類數(shù)據(jù)結(jié)構(gòu)，系統(tǒng)的性能會相對較好；另外，當(dāng)查詢操作極為頻繁時(shí)，或許還需要考慮對數(shù)據(jù)保持實(shí)時(shí)排序，以進(jìn)一步提升性能。

所以，為了更有效地權(quán)衡，我們在設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)與算法時(shí)，有時(shí)甚至需要同時(shí)選取多種數(shù)據(jù)結(jié)構(gòu)來記錄數(shù)據(jù)。例如，把絕大部分的穩(wěn)定數(shù)據(jù)保存在序列數(shù)組中，針對偶爾變更的數(shù)據(jù)記錄保存在鏈表中，畢竟業(yè)務(wù)中并未限定必須使用相同的結(jié)構(gòu)類型來保存相同類型的數(shù)據(jù)。

那么為了更直觀地闡釋從業(yè)務(wù)操作的不同頻率出發(fā)，選擇數(shù)據(jù)結(jié)構(gòu)與算法的意義，在此我就通過兩種較為典型的數(shù)據(jù)庫類型的設(shè)計(jì)原理，為您舉例說明一下。第一種是分析數(shù)據(jù)庫，例如 ClickHouse。它絕大部分的操作請求都會聚焦在批量數(shù)據(jù)分析上，所以在設(shè)計(jì)時(shí)，就必須確保批量數(shù)據(jù)分析的性能，而這會導(dǎo)致數(shù)據(jù)的修改性能開銷較大。第二種是文檔數(shù)據(jù)庫，比如 MongoDB 等。不過很多時(shí)候，我們?yōu)榱俗非髥挝臋n級別的 CRUD 性能，就不得不在批量數(shù)據(jù)分析計(jì)算性能上做出讓步。實(shí)際上，針對大型業(yè)務(wù)系統(tǒng)，我們通常需要選取多種數(shù)據(jù)存儲方案進(jìn)行數(shù)據(jù)冗余，從而綜合滿足各種業(yè)務(wù)場景下的性能需求。同樣，我們在業(yè)務(wù)內(nèi)部設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)與算法時(shí)，不能什么都想要，必須做出取舍，只有綜合各類操作之后，才能夠權(quán)衡利弊做出選擇。

學(xué)會降低算法精確度提升性能

好了，最后我要帶你掌握的知識點(diǎn)，就是要學(xué)會降低算法精確度，以此來進(jìn)一步提升系統(tǒng)性能。我們都知道，算法通常都是精確的、嚴(yán)格的，但在很多業(yè)務(wù)場景下，我們并不需要那么高的精確性。就拿我自己來說，我過去參與的諸多項(xiàng)目中，有過太多次降低算法精度與性能之間的權(quán)衡，所以接下來，我也用一個(gè)簡單的例子來給你說明下原因。

假設(shè)現(xiàn)在有一個(gè)已經(jīng)排序后的鏈表：

std::list<Kv> SortedKvs;

隨后，它在每個(gè)周期內(nèi)都會有新數(shù)據(jù)輸入，在正常狀況下，每插入一條數(shù)據(jù)都需要進(jìn)行遍歷以尋找插入點(diǎn)，以此確保整個(gè)鏈表中的數(shù)據(jù)是有序的。通過這樣對業(yè)務(wù)的分析發(fā)現(xiàn)，排序的正確性實(shí)際上并不需要特別高，并且經(jīng)過認(rèn)真的評估分析與驗(yàn)證后，我們發(fā)覺其實(shí)能夠把待插入數(shù)據(jù)先放入鏈表的尾部，這樣當(dāng)積累了 5 到 10 條待插入數(shù)據(jù)之后，再遍歷一遍鏈表插入所有數(shù)據(jù)，通過這種實(shí)現(xiàn)方式，能夠?qū)⒉迦霐?shù)據(jù)的運(yùn)行開銷降低好幾倍。由此可見，在實(shí)際的業(yè)務(wù)場景當(dāng)中，我們務(wù)必要依照性能要求標(biāo)準(zhǔn)來選取恰當(dāng)?shù)乃惴ň_度。

好啦，我們再來看一看前面我所介紹的那個(gè)資源調(diào)度的例子，想一想，從 1000 個(gè)用戶中選擇 10 個(gè)高優(yōu)先級用戶進(jìn)行資源調(diào)度，是否還有其他通過降低算法精確度來提升系統(tǒng)性能的方案呢？實(shí)際上，我們能夠?qū)?1000 個(gè)用戶拆分成 2 個(gè)組，每個(gè)組包含 500 個(gè)用戶，接著交替在 2 個(gè)組內(nèi)選擇 10 個(gè)高優(yōu)先級用戶進(jìn)行資源分配。如此通過在代碼實(shí)現(xiàn)上較小的改動(dòng)，就能夠在性能上提升將近一倍。但在這里您要留意一點(diǎn)，那就是您還需要驗(yàn)證調(diào)整后的算法實(shí)現(xiàn)是否滿足了業(yè)務(wù)需求。存在許多種降低算法精確度的實(shí)現(xiàn)方式，您需要精確地分析并驗(yàn)證，選擇背后的業(yè)務(wù)邏輯是否依然能夠滿足業(yè)務(wù)需求。