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

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

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

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

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

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

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

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

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

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

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

第一種數(shù)據(jù)結構類型為數(shù)組：

Kv arrayKvs[] = {...}

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

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

第二種數(shù)據(jù)結構類型為鏈表：

std::list<Kv> listKvs;

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

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

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

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

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

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

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

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

倘若在這個類的所有節(jié)點數(shù)據(jù)里，近乎所有的 value 值皆不相同，并且 key 的長度較大，那么我們能夠對代碼中的比較順序予以調整，因為整數(shù)比較的效率更高，能夠進一步提升性能。

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

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

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

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

一方面，很多場景的領域數(shù)據(jù)是不標準的。

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

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

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

那么此刻，您需要對這個數(shù)據(jù)集進行完整排序，應當如何選擇算法呢？倘若您沒有關注到第三點特征，選擇了一個極為高效的排序算法后，確實也能夠將算法復雜度降低到 O (N*log? N)。

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

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

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

另一方面，業(yè)務算法通常是不標準的。

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

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

2：運用冒泡排序算法，對 1000 個用戶全部遍歷 10 次，選出前 10 個用戶。

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

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

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

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

權衡綜合各種操作選擇數(shù)據(jù)結構與算法

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

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

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

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

學會降低算法精確度提升性能

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

假設現(xiàn)在有一個已經排序后的鏈表：

std::list<Kv> SortedKvs;

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

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