四重選擇題2021-11-18 15:30:30

當陣列長度與位移長度不互質時，該演算法不可行。考慮12345678左移2位，先將8取出，此時8的位置空缺，填入6，6位置空缺，填入4，4位置空缺，填入2，2位置空缺，填入8，演算法完成，結果為14365872，錯誤。

注：“不可行”指的是題主的“直覺上，陣列所有元素根據對映關係會形成一個完整的環，這樣演算法一定能完成”。評論區和其他答主已經給出了修正方法。在此一併表示感謝。

陳越姥姥2021-11-19 21:51:01

這個想法很好的。

有個定理說：每個置換都可以寫成若干個不相連的輪換之積。這句話放到你這裡的解釋就是：陣列左移是對原來元素的一個重排列，就是一個“置換”。“輪換”就是你說的“完整的環”。一個排列可以由多個互不相交的環組成，不一定是“一個”完整的環。

例如當陣列中有n*k個元素，要左移k位，那就是把

a［1］。。。a［k］ a［k+1］。。。a［2k］ a［2k+1］。。。a［3k］ ……。 a［（n-1）k+1］。。。a［nk］

置換成為

a［k+1］。。。a［2k］ a［2k+1］。。。a［3k］ ……。 a［（n-1）k+1］。。。a［nk］ a［1］。。。a［k］

隨便拿走一個元素，不妨就取走a［1］，讓第1個位置先空出來，然後填空的順序就是：

a［k+1］、a［2k+1］、a［3k+1］、。。。、a［（n-1）k+1］、a［1］ —— 這就是一個環。

其實你是可以在完成了一個環以後，繼續找下一個還沒被調整過的數字，那一定是屬於下一個環的……如此直到所有環都被處理掉。

最壞情況下（什麼是最壞情況？自己想一下），元素移動的次數會達到多少？

知乎使用者2021-11-20 00:10:34

巧了，以前出過一個右移的題目，原理是一樣的。

可以證明：對於長度為m，右移n位的情況下，最少需要的賦值次數為m+gcd（n%m，m）。

知乎使用者2021-11-21 01:50:30

C++ 的標準庫中有現成封裝好的

rotate

函式，作用和你需要的完全一致。

當然我說這話的意思不是讓你偷懶直接調庫——這樣根本學不到什麼東西，而是說，其中就有值得我們參考學習的東西，讀一下原始碼就能學到很多東西。

我在本文會介紹實現

rotate

的三個方法並分析它們各自的優劣。這些知識都是我之前研究 STL 原始碼並結合自己的最佳化經驗習得的。

三個方法分別是：

你提到的 ”三次逆轉法“；

@Betty 及其他幾位答主都提到的 ”迴圈移動法“；

以及 ”分塊交換法“。

”迴圈移動法“ 其他答主都提到了，但是隻有 @Betty 給出了普遍適用的方法。不過很可惜他沒有給出詳細的講解，本文會結合畫圖給出一個生動易理解的解釋。

@陳越姥姥 姥姥給出的方法本質上還是 ”迴圈移動法“。但只是該法在序列長度為整倍數下的特例，不具有普適性。

@四重選擇題 說錯了，長度不互質時可行，而且評論裡也給出瞭解決辦法。不互質的情況其實很簡單，只要你懂了互質的情況，不互質的情況立馬就好解決。

另外不得不提的是，”迴圈移動法“ 是早些年間 C++ 標準庫實現

std：：rotate

（的其中一個版本的過載）的基本思路，但是現在的 STL 實現已經不再使用這個方法了。

這個方法有著三個中最小的操作次數，但只是

表面上很漂亮，

實際工作效能非常拉胯，下文會給出分析。

一、做一些命名約定

為後文描述方便，做如下命名約定：

給定序列區間

，其中又以

mid

劃分為兩個子區間：

，

。稱交換

的相對位置的操作為旋轉操作。

圖解示意

（對於

，

）

：

二、三次逆轉法

首先法一就是你提到的三次

reverse

。分別逆轉子區間

，再整體逆轉區間

，恰好可以實現

rotate

操作所規定的需求。

這個方法的

優勢

是：

1）

此方法毋需開闢輔助陣列，達到了空間效率上的最優。

2）

經過簡單演算法思維訓練的計算機專業初學者，就能輕鬆上手，實現出一個無輔助陣列開銷且時間效率

“並不太低”

的

rotate

演算法。

但是這個方法具有如下的劣勢

：

1）該法只能運用於能雙向訪問的容器

（如陣列、

vector

、

list（雙向迴圈連結串列）

）。對於只能單向訪問的容器（如

forward_list（單鏈表）

），則無法適用該方法。（注意，STL 中的

std：：rotate

是支援單向訪問的容器的！這意味著，我們必須另尋支援單向訪問容器的新演算法，為單向訪問容器提供單獨的過載版本）

2）

在一些情況下，三次逆轉法的效率其實並不夠理想。詳見 2。1 及 2。2：

2.1

設有

使得

，則三次逆轉法共需執行

次

swap

操作。而一一交換

中的元素，則只需

次

swap

操作（例：對於

，

，分別交換

，只需 4 次交換）

類似的情況還會發生在

、

其中一段的長度正好為另一段的整數倍的情況下。我們不妨再設

，

，即

。

交換

得

交換

得

交換

得

至此完成

rotate

操作。

以上方法稱為 ”初代的分塊交換法“，它是我們即將在第四節介紹的完整的分塊交換法的簡化情形（因為初代只能處理其中一段的大小為另一段整數倍的情況）。

不難證得：當

（或

）時，三次逆轉法約需

次

swap

（這裡不考慮分奇偶數的情形，只做簡單估算），而初代的分塊交換法只需執行

次

swap

。

取比值

當 k 較小（

），即兩個序列長度比較接近時，分塊演算法的效率要明顯高於三次逆轉法。儘管當 k 較大時，兩者耗時的相對差值會被拉小

（注意絕對差值仍有 N 次的 swap，只是相對地差距拉小了）。

三、迴圈移動法

我們先考察

與

互素的情況（其實不互素的情況很簡單，後面會講解，只要你理解了互素情況下是如何處理的，不互素的情況如何處理自然就能得出來了）。

不妨設

，

。

↓ 開闢臨時變數

t

，暫存序列

開始位置的 0 號元素，將游標（藍色發光位置）指向序列

開始位置。

↓ 將 3 存到先前存放 0 的位置，然後，將游標向後移動

個位置，指向 6。

↓ 將 6 存到先前存放 3 的位置，然後，將游標

迴圈向後移動

個位置，指向 2。

這裡，

“迴圈向後移動”

的意思就是每當移動到整個序列末尾的時候，再重新回到序列開始的地方，繼續向後移動。

↓ 將 2 存到先前存放 6 的位置，然後，將游標迴圈向後移動

個位置，指向 5。

↓ 將 5 存到先前存放 2 的位置，然後，將游標迴圈向後移動

個位置，指向 1。

↓ 將 1 存到先前存放 5 的位置，然後，將游標迴圈向後移動

個位置，指向 4。

↓ 將 4 存到先前存放 1 的位置。

↓ 顯然，最後，只需將暫存在臨時變數

t

中的 0 存到先前存放 4 的位置上，就得到我們想要的結果了。

至此，我們成功將

變換為了我們想要的

（

，

）

那，如果

與

不互素怎麼辦？

不妨還是舉個例子，對於

，

，即

，

的請況，不難得出

，

與

不互素。

如果直接使用上文中對長度互素情況下的辦法（大家不妨動用紙筆算算看），會得到

對比我們想要的結果：

發現了麼？偶數（4， 6， 8， 0， 2）都調整到位了，只剩奇數沒有動。只需對奇數這一組（也就是整體位置偏移一個 1）再進行一次迴圈移位就可以了。

對於最大公因數為 3 的情況也是類似的，總共需分三組分別進行一次，總計三次迴圈移位就可以了。大家不妨動手驗證一下。

歸納一下，對於完整的一次

rotate

操作，不論

與

是否互素，總會將整個序列分為

個組，每組中有

個元素。每處理一個組需要

次賦值操作。

因此完整的一次

rotate

操作，總的賦值操作次數為

次。粗略地來說，還是一個具有線性複雜度的演算法。

程式碼不難：

void

rotate_cycle

（

int

*

first

，

int

*

mid

，

int

*

last

）

{

size_t

len1

=

mid

-

first

；

size_t

len2

=

last

-

mid

；

size_t

len

=

len1

+

len2

；

if

（

len1

==

0

||

len2

==

0

）

{

return

；

}

size_t

group

=

std

：：

gcd

（

len1

，

len2

）；

size_t

group_size

=

len

/

group

；

while

（

group

——

）

{

int

*

it

=

first

+

group

；

int

t

=

*

it

；

for

（

size_t

i

=

0

；

i

<

group_size

-

1

；

++

i

）

{

#if 0

int * next = first + （it - first + len1） % len； // 迴圈向後移動 （取模實現）

#else

// 迴圈向後移動 （分支實現， 更高效）

int

*

next

=

it

；

if

（

size_t

（

last

-

it

）

>

len1

）

{

next

+=

len1

；

}

else

{

next

=

first

+

（

len1

-

（

last

-

it

））；

}

#endif

*

it

=

*

next

；

it

=

next

；

}

*

it

=

t

；

}

}

“迴圈移動法” 的優勢：

1）

具有最少的操作次數，它只需

次賦值操作。

而 ”三次逆轉法“ 約需

次 swap，每次 swap 又需要三次賦值操作，所以就是

次賦值。（這裡不考慮分奇偶數的情形，只做簡單估算）

那麼，”三次逆轉法“ 的時間開銷會是 “迴圈移動法” 的約 3 倍嗎？（如果 gcd 的值不大的話）這裡留一個疑問，下面解答。

2）

”理論上“ 十分高的效能。（為什麼是 “理論上” 呢，請接著往下看）

“迴圈移動法” 的劣勢：

1）該法只適用於隨機訪問容器。

因為該法

1’ 需要計算序列長度；

2‘ 需要每次需要將指標迴圈向後移動

次。

所以必然要求容器具有隨機訪問能力。

所以在早先的 STL 實現中，該方法只能實現

std：：rotate

的隨機訪問迭代器的過載版本。

2）

有些同學可能為了實現方便，會使用取模運算來實現 “迴圈向後移動” 的操作——注意！取模是開銷極大的運算。

或者你也可以使用

if

語句去最佳化取模，實現 “迭代器是否移動到了序列末尾” 這一判斷，但是引入分支結構帶來的效能影響也還是存在的（除非機器支援

cmov

等條件操作指令，不必生成分支跳轉外，否則一旦有分支跳轉，對效能的影響還是挺大的）

3）

每次移動的元素之間並不相鄰，導致該法非常非常難進行 SIMD 指令級並行最佳化，並獲得性能提升。

要想理解這一條的同學可以去了解一下 SIMD 指令。這是現代 CPU 的一個非常重要的加速技術，可以實現一條 CPU 指令並行操作多條資料。比如 “三次逆轉法” 中的逆轉操作很容易使用 SIMD 加速，可以實現一次操作逆轉多條資料，從而大大地加快了速度。

4）

訪存失效問題可能會十分嚴重，因為：

1‘ 每次移動的元素之間並不相鄰，十分容易超出快取的範圍；

2’ 可能會發生若干次指標轉回到序列前端重新掃描的情況。

訪存失效問題是一個會大大降低演算法執行效率的問題，因為每一次訪存失效都會伴隨著大量的時鐘週期被白白浪費。惶論在 ”迴圈移動法“ 中，幾乎每一次的資料訪問都有使訪存失效的風險。

比如對於下面的這幾種情況（旋轉 （len1， len2） 長度的 int 型序列），bench 結果是這樣的：

g++ rotate。bench。cpp -o rotate。bench -O2

// 說明：kerbal：：rotate 是我自己的庫中

運用多種手段調優後的 rotate 實現，

主要基於後文要介紹的

”分塊交換法“

len1：

32

len2：

99999968

kerbal：：rotate

61

ms

std：：rotate

62

ms

迴圈移位法

（

取模實現

）

1206

ms

迴圈移位法

（

分支實現

）

686

ms

三次逆轉法

75

ms

樸素的臨時陣列法

31

ms

len1：

33333333

len2：

66666667

kerbal：：rotate

64

ms

std：：rotate

60

ms

迴圈移位法

（

取模實現

）

869

ms

迴圈移位法

（

分支實現

）

97

ms

三次逆轉法

76

ms

樸素的臨時陣列法

94

ms

len1：

50000000

len2：

50000000

kerbal：：rotate

36

ms

std：：rotate

38

ms

迴圈移位法

（

取模實現

）

334

ms

迴圈移位法

（

分支實現

）

80

ms

三次逆轉法

77

ms

樸素的臨時陣列法

113

ms

cat /proc/cpuinfo

processor ：

0

vendor_id ： GenuineIntel

cpu family ：

6

model ：

158

model name ： Intel

（

R

）

Core

（

TM

）

i7-9750H CPU @ 2。60GHz

stepping ：

10

microcode ： 0xea

cpu MHz ： 2600。000

cache size ：

12288

KB

連最原始的開闢臨時陣列的方法都打不過了 /攤手

所以你應該知道為什麼 STL 後來拋棄了這個演算法。

這裡有幾句有感而發的話：

學校裡講的《演算法和資料結構》課程，在衡量一個演算法的執行時間時，往往只會關注那個在數學上推匯出的時間複雜度——雖然這確實是這門課程本應討論的範圍。

但是，你作為一個學習計算機的

人

，如果只是做到學《資料結構》時

只

學《資料結構》，學《組成原理》時

只

學《組成原理》，學《作業系統》時

只

學《作業系統》，在你上機實踐時

沒有

把這些課程中所學到的內容

綜合、聯絡

起來的話，

那麼這種學習方式就是形而上學的

。

我不相信，你的《組成原理》課本沒有告訴你，計算機的儲存體系是多級的，每一級之間都有至少一個數量級的速度差距——這在我們今天的分析中就用到了，也被事實所檢驗了。

我不相信，你的《作業系統》課本沒有告訴你，程式的區域性性原理，一個良好的計算機程式常常具有良好的區域性性——這在我們今天的分析中也用到了，也被事實所檢驗了。

所以希望讀者以後能意識到，

評價一個演算法好不好，不能僅僅只在《演算法和資料結構》的維度下衡量，更需要結合整個專業的課程體系綜合評判。

共勉。

四、分塊交換法

我們回顧一下在分析 “三次逆轉法” 優勢劣勢時提前介紹的 ”初代的分塊交換法“（適用於

、

其中一段的長度正好為另一段的整數倍的情況）。

比如對於

，

，即

時。

交換

得

交換

得

交換

得

演算法結束，得到最終結果。

那如果出現長度無法整除的情況怎麼辦？

不妨再設

，

先用上面的初代方法試試看：

交換

得

交換

得

接下來該怎麼辦？

其實要我說，其實問題已經解決了。

有讀者可能會問，辦法呢？辦法在哪裡？

剩下的不夠處理的

，把它當作

，

再旋轉一下不就行了嘛。

遞迴處理即可

。

演算法的大致框架如下：

void

rotate_chunk_swap

（

int

*

first

，

int

*

mid

，

int

*

last

）

{

size_t

len1

=

mid

-

first

；

size_t

len2

=

last

-

mid

；

if

（

len1

<=

len2

）

{

for

（

size_t

i

=

0

；

i

<

len2

/

len1

；

++

i

）

{

int

*

chunk_first

=

first

+

len1

*

i

；

for

（

size_t

j

=

0

；

j

<

len1

；

++

j

）

{

swap

（

chunk_first

［

j

］，

chunk_first

［

len1

+

j

］）；

}

}

}

else

{

。。。

// 處理 len1 < len2 的情形

}

rotate_chunk_swap

（。。。）；

// 遞迴處理剩下的部分

}

當然，實際編寫程式碼時，為了處理方便，實際上是操作

first

，

mid

雙迭代器，每次交換

first

，

mid

所指元素，再一起向後步進。在處理序列末尾元素時的細節會有所不同，但是解決問題的基本思路是一致的。

void

rotate_chunk_swap

（

int

*

first

，

int

*

mid

，

int

*

last

）

{

size_t

len1

=

mid

-

first

；

size_t

len2

=

last

-

mid

；

if

（

len1

==

0

||

len2

==

0

）

{

return

；

}

while

（

mid

！=

last

）

{

swap

（

*

first

，

*

mid

）；

++

first

；

++

mid

；

}

rotate_chunk_swap

（

first

，

mid

-

len2

%

len1

，

mid

）；

}

這裡尤有一個需要注意的地方，因為該版本的演算法是基於遞迴實現，在輸入資料較為刁鑽的時候，是有爆棧的危險的！

比如最極端的，在輸入序列長度為

，

時，那個 while 迴圈進行不了幾次就會陷入遞迴。

如果你瞭解

尾遞迴最佳化

的話，其實上一個遞迴版本很容易就能改為非遞迴的版本：

void

rotate_chunk_swap_non_recursive

（

int

*

first

，

int

*

mid

，

int

*

last

）

{

while

（

true

）

{

size_t

len1

=

mid

-

first

；

size_t

len2

=

last

-

mid

；

if

（

len1

==

0

||

len2

==

0

）

{

return

；

}

while

（

mid

！=

last

）

{

swap

（

*

first

，

*

mid

）；

++

first

；

++

mid

；

}

// ***

mid

=

mid

-

len2

%

len1

；

last

=

mid

；

// ***

}

}

其實，唯一的區別兼技術要點就在打星處。

這裡怎麼理解呢？

原來是

rotate_chunk_swap（first， mid - len2 % len1， mid）；

進行遞迴呼叫，

其實就相當於構造了一組新的引數給下一輪的分塊交換操作：

first‘ = first

，

mid’ = mid - len2 % len1

，

last‘ = mid

那麼，在尾遞迴改迴圈時，我們只要將引數修改為新的值就行了。

這樣就避免了遞迴爆棧的問題。

當然，這裡繼續最佳化的點還有很多。

比如，我們當然是希望內迴圈

while

（

mid

！=

last

）

{

swap

（

*

first

，

*

mid

）；

+

first

；

++

mid

；

}

的執行次數越多越好，而外迴圈（或者是遞迴）越少越好。（區域性性原理）

所以這裡就可以做個長度的判斷，如果

，那麼就從左往右做分塊交換，否則就從右往左做分塊交換。

做了完整的工程化應用 & 最佳化的程式碼可以參考這裡，你需要一點閱讀 C++ 模板的能力。

github。com/WentsingNee/Kerbal

妹妹催覺覺了，晚安～

AKAX2021-11-22 22:46:03

首先，左移和右移其實是一樣的。三次翻轉並不慢，cache很友好，建議採用。總交換次數應該是n次而不是2n次。比如12345678

（偏移量4：則前段是1234，但只交換了14和23兩次而已。後段5678也是兩次。總的交換次數為n/2，完成兩次翻轉，第三次翻轉恆為n/2，所以總次數是n而不是2n。

偏移量3：則前段是123，直交換了13一次。後段是45678，只交換2次而已。第三次翻轉恆為n/2。總的交換次數可以視為n。）

下標計算法理論次數更少，但實際上寫出來仍然要n次，而且可能cache不友好，多了兩次if，可能會影響cpu流水。速度我就懶得測了。

上程式碼：189。 輪轉陣列

三次交換：

class Solution {

private：

void re（vector &s，int i，int j）{

for（int x；++i<——j；x=s［i］，s［i］=s［j］，s［j］=x）；

}

public：

void rotate（vector& nums， int k） {

int n=nums。size（）；k%=n；if （！k） return；

k=n-k； //這裡可以看出左旋跟右旋是一樣的。題目要求右旋，這裡改成左旋跟你的意思一致。

re（nums，-1，k）；

re（nums，k-1，n）；

re（nums，-1，n）；

}

}；

下標計算法：

class Solution {

public：

void rotate（vector& nums， int k） {

int n=nums。size（）；k%=n；if （！k） return；

for（int z=n-k，x=0，y=0，a1=nums［0］，a2；n——；a1=a2）

{

x=x

a2=nums［x］；nums［x］=a1；

if （x==y）{y=++x；a2=nums［x］；}

}

}

}；//這是純粹左旋，跟你的意思一致；