P.S. 感謝@ComeIntoPower 提供了寶貴的修改意見(jiàn)。
內(nèi)存的訪問(wèn)是非常慢的，除了內(nèi)存，還有寄存器(register)、高速緩存cache，它們的訪問(wèn)速度比內(nèi)存更快。
電腦的存儲(chǔ)分級(jí)可以用一個(gè)非常形象的栗子來(lái)說(shuō)明：
我們可以以經(jīng)典的閱讀書(shū)籍為例。我在讀的書(shū)，捧在手里（寄存器），我最近頻繁閱讀的書(shū)，放在書(shū)桌上（緩存），隨時(shí)取來(lái)讀。當(dāng)然書(shū)桌上只能放有限幾本書(shū)。我更多的書(shū)在書(shū)架上（內(nèi)存）。如果書(shū)架上沒(méi)有的書(shū)，就去圖書(shū)館（磁盤）。我要讀的書(shū)如果手里沒(méi)有，那么去書(shū)桌上找，如果書(shū)桌上沒(méi)有，去書(shū)架上找，如果書(shū)架上沒(méi)有去圖書(shū)館去找?？梢詫?duì)應(yīng)寄存器沒(méi)有，則從緩存中取，緩存中沒(méi)有，則從內(nèi)存中取到緩存，如果內(nèi)存中沒(méi)有，則先從磁盤讀入內(nèi)存，再讀入緩存，再讀入寄存器。
這是一張有兩級(jí)cache的計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu)圖。
寄存器具有最高的訪問(wèn)速度，在變量前加關(guān)鍵詞register即將其加入寄存器。但如圖，寄存器的空間是有限的，不應(yīng)該濫用register，應(yīng)該僅在訪問(wèn)最頻繁的幾個(gè)變量（如循環(huán)變量）前加register。
cache即高速緩存，一般分為3級(jí)（有些電腦為兩級(jí)），訪問(wèn)速度逐級(jí)遞減。訪問(wèn)變量時(shí)，CPU會(huì)優(yōu)先在cache而不是內(nèi)存中查找，如果cache中不存在此變量，則會(huì)進(jìn)入內(nèi)存查找，這稱為cache miss。如圖，內(nèi)存訪問(wèn)的開(kāi)銷是巨大的，所以cache miss是一個(gè)重要的常數(shù)問(wèn)題。
那么如何減少cache miss？
對(duì)于cache miss優(yōu)化，有如下幾點(diǎn)：
與register一樣，cache的大小同樣有限。一些過(guò)大的內(nèi)存是不可以進(jìn)入cache的。
基數(shù)排序時(shí)，以256為基數(shù)會(huì)比256*256更快。因?yàn)?56大小的四個(gè)數(shù)組可以輕松進(jìn)入cache。
詳見(jiàn) 洛谷題庫(kù) WC2017挑戰(zhàn) Subtask1
什么是時(shí)空局部性？
時(shí)間局部性：當(dāng)一個(gè)變量被使用時(shí)，它會(huì)在短時(shí)間內(nèi)再次被使用。
空間局部性：當(dāng)一個(gè)變量被使用時(shí)，它的內(nèi)存附近的變量會(huì)再次被使用。
保證這兩樣?xùn)|西的良好有益于減少cache miss。
怎樣優(yōu)化空間局部性？
將一些關(guān)系密切，例如經(jīng)常連著使用的變量盡量定義在一起，或用結(jié)構(gòu)體封裝起來(lái)。
適當(dāng)調(diào)整變量定義順序
保證內(nèi)存連續(xù)訪問(wèn)。例如：Floyd和矩陣乘法的程序中，將第三層循環(huán)作為第一層會(huì)大大提高速度。
怎樣優(yōu)化時(shí)間局部性？
盡量使用局部變量。因?yàn)槎褩５臄?shù)據(jù)訪問(wèn)十分頻繁。
同樣是空間局部性的原理，兩個(gè)相互關(guān)聯(lián)（例如調(diào)用對(duì)方）的函數(shù)應(yīng)該定義得足夠靠近，這能使它們有機(jī)會(huì)同時(shí)被加載到指令cache中。
cache的生活應(yīng)用：DevC++編譯程序后第一遍運(yùn)行很慢，這是因?yàn)榫幾g后的程序沒(méi)有進(jìn)入緩存。運(yùn)行一次后，相關(guān)指令進(jìn)入cache，就會(huì)提高運(yùn)行速度。同樣地，對(duì)程序進(jìn)行多次測(cè)速求平均時(shí)，如果程序訪問(wèn)到了一些大數(shù)組，且它們之前沒(méi)有進(jìn)入cache，則應(yīng)該忽略掉第一次運(yùn)行，取i=2到n次的一段進(jìn)行平均。
摘自駱爺pdf的一句話：“這也是編寫優(yōu)美代碼的原則?！?/p>
指針用法：
for(register int i=1;i<=n;++i)work(a[i]);
應(yīng)化為for(register int *S=a,*E=a+n;S!=E;)work(*++S);
這樣能夠大幅度提高速度。為啥呢？
a[i]本質(zhì)上是*(a+i)，64位平臺(tái)上是long long相加，比指針的前自加運(yùn)算慢得多。
注：初始化和數(shù)組復(fù)制方面，memset和memcpy比指針具有更高的速度，因?yàn)樗鼈儗?shí)際上調(diào)用了rep movsq指令，這比一般的mov指令快很多。
對(duì)于高維數(shù)組，例如 ，則a[i][j][k]的訪問(wèn)相對(duì)而言十分慢。我們可以將它降成一維數(shù)組，a[i?h?w+j?w+k]代替，從而更快地訪問(wèn)。另外也可以利用代數(shù)方法減少乘法次數(shù)，將其化為a[(i?h+j)?w+k]。更高維的數(shù)組也可以用這種方法優(yōu)化。
更多內(nèi)容請(qǐng)參考：
http://nadeausoftware.com/articles/2012/06/c_c_tip_how_loop_through_multi_dimensional_arrays_quickly
inline函數(shù)能夠提高效率，因?yàn)樗軌驕p少堆棧開(kāi)銷、減少傳參耗時(shí)。
#define宏函數(shù)與inline函數(shù)具有相同速度和效果，但會(huì)在函數(shù)體中反復(fù)計(jì)算參數(shù)，這當(dāng)參數(shù)是一個(gè)式子時(shí)是很不利的。請(qǐng)讀者根據(jù)具體情況自行選擇。
例：#define sq(x) ((x)*(x))//平方函數(shù)
同樣的道理，遞推比遞歸更優(yōu)秀。它減少了堆棧開(kāi)銷，會(huì)更快速，同時(shí)避免了爆棧的危險(xiǎn)。
同樣地，手動(dòng)bfs比dfs更為高效，且內(nèi)存開(kāi)銷也更小，尤其是多次dfs一棵樹(shù)時(shí)。
一些STL的速度瓶頸即std::allocator對(duì)內(nèi)存的動(dòng)態(tài)分配，這對(duì)于push_back等操作不利。
我們可以手寫這個(gè)struct，用足夠大小的內(nèi)存池來(lái)代替動(dòng)態(tài)分配內(nèi)存。這里我們用派生于std::allocator的myalloc結(jié)構(gòu)體來(lái)代替它：
#include<bits/stdc++.h>
using namespace std;
#define reg register
static char space[10000000],*sp=space;
template<typename T>
struct myalloc:allocator<T>{
myalloc(){}
template<typename T2>
myalloc(const myalloc<T2> &a){}
template<typename T2>
myalloc<T>& operator=(const myalloc<T2> &a){return *this;}
template<typename T2>
struct rebind{typedef myalloc<T2> other;};
inline T* allocate(size_t n){
T *result=(T*)sp;sp+=n*sizeof(T);
return result;
}
inline void deallocate(T* p,size_t n){}
};
完成后，即可這樣定義STL容器：
list<int,myalloc<int> > L;vector<double,myalloc<double> > vec;
實(shí)測(cè)表明，這確實(shí)能夠優(yōu)化STL相當(dāng)一大部分的常數(shù)。
由于為了競(jìng)賽中方便打，該模板沒(méi)有編寫內(nèi)存釋放函數(shù)（網(wǎng)上的模板十分冗長(zhǎng)），因此，當(dāng)內(nèi)存過(guò)大時(shí)不要用此模板，太大會(huì)RE，不太大也可能變慢。
如果平時(shí)想要使用這一類的優(yōu)化，請(qǐng)參考這個(gè)十分詳細(xì)的內(nèi)存池教程：https://blog.csdn.net/u010183728/article/details/81531392
聯(lián)系客服
