3.1 什么是算法效率

算法效率主要指的是算法的時(shí)間復(fù)雜度，在第2章中提到了一種圖算法的分類方式，即按照從恒定時(shí)間、線性、多項(xiàng)式到指數(shù)級(jí)復(fù)雜度的自低到高的多級(jí)分類。需要指出的是，不同的底層計(jì)算資源的規(guī)模是會(huì)影響算法的執(zhí)行效率的，例如可并發(fā)的規(guī)模。另外，也需要關(guān)注算法的空間復(fù)雜度，即用于完成算法執(zhí)行所需要的存儲(chǔ)空間，包括外存與內(nèi)存等。

評(píng)價(jià)算法效率的“金指標(biāo)”就是在相同計(jì)算與存儲(chǔ)資源條件下，運(yùn)行時(shí)耗越低，算法實(shí)現(xiàn)效率越高。換言之，如果有更高配置的計(jì)算（及存儲(chǔ)）資源，就能夠?qū)崿F(xiàn)更高的計(jì)算效率。

算法效率的提升涉及算法邏輯優(yōu)化、數(shù)據(jù)結(jié)構(gòu)優(yōu)化、系統(tǒng)架構(gòu)優(yōu)化、代碼實(shí)現(xiàn)優(yōu)化等多個(gè)方面。但是所有的優(yōu)化形式在本質(zhì)上可以總結(jié)為兩個(gè)要點(diǎn)：一是盡可能地實(shí)現(xiàn)并發(fā)，二是盡可能地讓存儲(chǔ)的數(shù)據(jù)靠近計(jì)算資源。

圖3-1中的7層存儲(chǔ)架構(gòu)示意了算法效率提升的金字塔，可以簡(jiǎn)單地理解為：

1）網(wǎng)絡(luò)化存儲(chǔ)的計(jì)算效率是最低的，特別是當(dāng)數(shù)據(jù)之間存在關(guān)聯(lián)關(guān)系時(shí)。在一個(gè)大規(guī)模分布式的系統(tǒng)中，多個(gè)存儲(chǔ)節(jié)點(diǎn)需要不斷地交換或遷移數(shù)據(jù)，所造成的時(shí)耗是驚人的。而這個(gè)時(shí)候，即便再高的網(wǎng)絡(luò)帶寬也可能于事無(wú)補(bǔ)。舉個(gè)簡(jiǎn)單的例子，假設(shè)用10Gb/s的速度傳輸100萬(wàn)個(gè)4KB的小文件與傳輸一個(gè)4GB的文件（在文件大小層面，4GB=4KB×104），兩者的傳輸時(shí)間差異是多少？答案是前者的時(shí)耗至少是后者的100倍以上，這是多實(shí)例間大量頻繁的I/O操作使然。

2）磁盤的效率較網(wǎng)絡(luò)存儲(chǔ)已經(jīng)大幅（10倍）提升，因?yàn)樗呀?jīng)是一種存儲(chǔ)與計(jì)算較緊密耦合的架構(gòu)模式，盡管磁盤I/O依然存在，但是不再需要考慮網(wǎng)絡(luò)造成的延遲。

3）固態(tài)硬盤（包括大容量固態(tài)硬盤和高性能固態(tài)硬盤）的特點(diǎn)是規(guī)避了傳統(tǒng)磁盤的可移動(dòng)的機(jī)械部件，而獲得了10～100倍于磁盤存儲(chǔ)訪問(wèn)的性能提升。盡管固態(tài)硬盤經(jīng)過(guò)多次擦寫后可能會(huì)出現(xiàn)數(shù)據(jù)遺失的問(wèn)題，但是在真正追求高性能的系統(tǒng)中，可以通過(guò)各種數(shù)據(jù)冗余與保護(hù)機(jī)制來(lái)規(guī)避這個(gè)問(wèn)題。如果只因?yàn)閾?dān)心固態(tài)硬盤在經(jīng)過(guò)7000次擦寫后可能會(huì)遺失數(shù)據(jù)就徹底規(guī)避使用，無(wú)異于因噎廢食。

4）持久化內(nèi)存（Persistent Memory）是圖3-1的7層堆棧中出現(xiàn)最晚的一種產(chǎn)品形態(tài)，本質(zhì)上它融合了固態(tài)硬盤與動(dòng)態(tài)隨機(jī)存儲(chǔ)內(nèi)存（DRAM）的特點(diǎn)，同時(shí)兼具了數(shù)據(jù)持久化的能力與內(nèi)存級(jí)的訪問(wèn)速度。持久化內(nèi)存相對(duì)于固態(tài)硬盤也有了10倍的性能提升。

5）內(nèi)存相對(duì)于固態(tài)硬盤有100～1000倍的讀寫性能提升，但是單位價(jià)格卻便宜10～20倍。從投入產(chǎn)出比上來(lái)說(shuō)，如果你聽(tīng)過(guò)“內(nèi)存就是新的存儲(chǔ)”（Memory is the New Disk!）的說(shuō)法，背后的原因就在這里。

6）多級(jí)存儲(chǔ)計(jì)算架構(gòu)中的最后一層是CPU，如果覺(jué)得CPU僅僅是用來(lái)計(jì)算的，就顯得有些不求甚解了。實(shí)際上，現(xiàn)代CPU的架構(gòu)設(shè)計(jì)中都會(huì)有多級(jí)內(nèi)置緩存，而多級(jí)緩存的價(jià)值在于每一層都給CPU與內(nèi)存之間的數(shù)據(jù)遷移和加載進(jìn)行了提速，畢竟內(nèi)存和CPU之間還存在著千倍級(jí)的性能差（圖3-1中只體現(xiàn)了10倍差異），而每層緩存都大概有10倍的提速效果。

圖3-2示意了這種多級(jí)存儲(chǔ)加速的效果。

? 機(jī)械硬盤：?jiǎn)未尾僮餮訒r(shí)如果是3ms，進(jìn)行一個(gè)四千萬(wàn)次的迭代操作，延時(shí)就變成了120000s，即1.5天，這就是很多批處理操作的耗時(shí)都是T+1、T+2的直接原因。

? 固態(tài)硬盤：可以帶來(lái)約30倍的性能提升，與上面同樣的操作耗時(shí)會(huì)降低到1個(gè)多小時(shí)，可以算作T+0的效果。

? 內(nèi)存：在內(nèi)存上進(jìn)行同樣的操作時(shí)，可以獲得上千倍的性能提升，這個(gè)時(shí)候“批處理”的操作已經(jīng)可以以近實(shí)時(shí)的方式完成。

? CPU緩存：理論上，如果所有的數(shù)據(jù)都可以在CPU（借助多級(jí)緩存的力量）內(nèi)完成，時(shí)間會(huì)縮短到毫秒級(jí)，如40ms。

事實(shí)上，在存儲(chǔ)與計(jì)算加速的道路上，CPU也不是終點(diǎn)，通過(guò)對(duì)數(shù)據(jù)結(jié)構(gòu)、系統(tǒng)架構(gòu)、最大化并發(fā)執(zhí)行等進(jìn)行優(yōu)化，還有可能獲得更低的耗時(shí)與更高的效率。