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

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

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

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

數據結構與算法選擇對性能的影響

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

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

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

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

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

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

第一種數據結構類型為數組：

Kv arrayKvs[] = {...}

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

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

第二種數據結構類型為鏈表：

std::list<Kv> listKvs;

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

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

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

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

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

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

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

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

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

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

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

根據領域數據特征去選擇算法

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

一方面，很多場景的領域數據是不標準的。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

權衡綜合各種操作選擇數據結構與算法

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

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

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

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

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

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

假設現在有一個已經排序后的鏈表：

std::list<Kv> SortedKvs;

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

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