雁過無痕

要將一個(gè)數(shù)組的所有元素向左旋轉(zhuǎn)k位，通常有三種算法：

算法1（分組交換）：

若a長度大于b，將ab分成a₀a₁b，交換a₀和b，得ba₁a₀，只需再交換a₁ 和a₀。

若a長度小于b，將ab分成ab₀b₁，交換a和b₀，得b₀ab₁，只需再交換a 和b₁。

不斷將數(shù)組劃分和交換，直到不能再劃分為止。分組過程與求最大公約數(shù)很相似。

 讀寫內(nèi)存各 n到2*n次

算法2 (三次反轉(zhuǎn))

利用ba=(b^r)^r(a^r)^r=(a^rb^r)^r，先分別反轉(zhuǎn)a、b，最后再對(duì)所有元素進(jìn)行一次反轉(zhuǎn)。

讀寫內(nèi)存各約2*n次

算法3 （使用循環(huán)鏈）

假設(shè) n、k的最大公約數(shù)為M，則所有序號(hào)為 (i + j*k) % n (0<= i < M, 0 <= j < n/M)的元素，構(gòu)成M個(gè)循環(huán)鏈（i值相同的在同一個(gè)循環(huán)鏈上）， 每個(gè)循環(huán)鏈上的元素移動(dòng)到前一個(gè)元素的元素，就可以交換到最終結(jié)果上的位置，因而總共只要讀寫內(nèi)存各n次。（比如： 1 2 3 4 5 6，左移2位， 1 3 5 和 2 4 6分別構(gòu)成兩個(gè)循環(huán)鏈。）

事實(shí)上C++標(biāo)準(zhǔn)算法庫提供了現(xiàn)成的函數(shù)：rotate函數(shù)。按理說，幾種算法都比較簡單，編譯器的庫函數(shù)又是經(jīng)過時(shí)間檢驗(yàn)的，效率即使比手寫的差，也不會(huì)差太多。但如果對(duì)rotate函數(shù)進(jìn)行測試的話，可能會(huì)發(fā)現(xiàn)標(biāo)準(zhǔn)庫的版本慢得可不是一點(diǎn)點(diǎn)。

對(duì)VC 2010，運(yùn)行后面的測試程序，自定義函數(shù)（采用算法2）要用99ms，而std::rotate卻要1656ms。是庫的實(shí)現(xiàn)者不懂得用這個(gè)簡單的算法嗎？檢查下庫的源代碼，就會(huì)發(fā)現(xiàn)：標(biāo)準(zhǔn)算法庫中，對(duì)C++的三種迭代器（前向迭代器、雙向迭代器，隨機(jī)訪問迭代器），分別采用了上面三種算法。直接調(diào)用其內(nèi)部的實(shí)現(xiàn)（std::_Rotat函數(shù)），重新測試下，可得到下面結(jié)果：

        （使用GCC的，請(qǐng)用版本號(hào)低于4.5的進(jìn)行測試）

    從結(jié)果可以看出，效率是：算法1 > 算法2 >>> 算法3。 

從理論上講，算法3只要讀寫內(nèi)存各n次，應(yīng)該是效率最高的算法。這在每次內(nèi)存讀寫的開銷相差不大時(shí)成立。但實(shí)際上，由于硬件限制，CPU對(duì)內(nèi)存的訪問采用分級(jí)緩存機(jī)制：一級(jí)緩存容量很小但訪問速度最快，存放程序的指令和最常用的數(shù)據(jù)，而二、三級(jí)緩存容量較大但訪問速度要慢很多。CPU是無法繞過緩存直接訪問內(nèi)存數(shù)據(jù)（某些特殊指令可以不用一二三級(jí)緩存，但它也要用到其它專用緩存），對(duì)不在緩存中的數(shù)據(jù)，必須先載入到緩存中，這個(gè)操作是相當(dāng)昂貴的。對(duì)大數(shù)組來說，不可能將所有數(shù)據(jù)都存放在緩存中，而對(duì)內(nèi)存的不連續(xù)訪問，CPU對(duì)內(nèi)存定位的開銷（各級(jí)緩存間數(shù)據(jù)的調(diào)整，反復(fù)移入或移出數(shù)據(jù)到緩存）是巨大的，這就造成了算法3的性能在該情況下非常差。測試發(fā)現(xiàn)，k = 3時(shí)，該算法的效率就已經(jīng)相當(dāng)差了。對(duì)小數(shù)組，盡管該算法讀寫次數(shù)少，但由于各種算法所用時(shí)間都很小，這種優(yōu)勢(shì)很難體現(xiàn)出來。可以說，算法3在數(shù)學(xué)上是非常優(yōu)美的，但是在實(shí)際應(yīng)用中，是一種相當(dāng)差的算法。

對(duì)算法的選擇，不應(yīng)該忽視內(nèi)存因素。在對(duì)隨機(jī)訪問迭代器版本的roate實(shí)現(xiàn)上犯這個(gè)錯(cuò)誤的，可不僅僅是VC，還有著名的STL Port、GCC（GCC從4.5開始libstdc++改用算法1，并做了些優(yōu)化），以及新興的libc++。（其它的編譯器/庫沒用過，也就沒有測試。）

另外，測試時(shí)發(fā)現(xiàn)VC 2010的一個(gè)bug：前向迭代器的實(shí)現(xiàn)版本，當(dāng)k = 0時(shí)，程序直接掛了。

測試代碼：