雁過無痕

《編程之美》讀書筆記09： 2.17 數組循環移位

對長度為n的數組(ab)左移k位，最直接的方法，就是用stl的rotate函數（stl針對三種不同的迭代器，提供了三個版本的rotate）。但在某些情況下，用stl的rotate效率極差。

對數組循環，可以采用的方法有：

①     動態分配一個同樣長度的數組，將數據復制到該數組并改變次序，再復制回原數組。

②     利用ba=(b^r)^r(a^r)^r=(a^rb^r)^r，通過三次反轉字符串。

③ 分組交換（盡可能使數組的前面連續幾個數為所要結果）：

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

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

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

④ 所有序號為 (i+t*k) % n (i為指定整數，t為任意整數)，會構成一個循環鏈（共有gcd(n,k)個，gcd為n、k的最大公約數），每個循環鏈上的元素只要移動一個位置即可，總共交換了n次。

stl的rotate的三種迭代器，分別使用了后三種方法。

多數情況下，前三種方法效率都比較高，第一種方法過分要求內存，第四種方法，元素間平均交換次數最少，理論上效率應該是最高的，但在n和k都很大時，其效率相當差（由于每次交換訪問的內存不連續，在n和k比較大時，內存訪問開銷很大，因為cache line命中率很低，又不斷跨頁訪問內存。）。方法三的平均交換次數要少于方法二，但判斷次數相對要多，效率相差不是太大，在大數組時方法三效率比較高，但同一個小數組左移幾十萬次，方法二效率略高，畢竟整個數組都可以被cache，內存訪問開銷小，判斷次數對效率影響較大。

測試代碼
  1// 2.17_rotate.cpp   by  flyinghearts#qq.com 
  2
  3#include <iostream>
  4#include <vector>
  5#include <algorithm>
  6#include <ctime>
  7#include <cstdlib>
  8using namespace std;
  9
 10/**//*
 11left_shift_0 通過復制到臨時數組
 12left_shift_1 三次反轉
 13left_shift_2 分組交換
 14left_shift_3 循環交換
 15left_shift_4 循環交換（先求最大公約數，確定次數）
 16left_shift_5 stl的rotate
 17
 18test函數：
 19數組ff存放要測試的函數
 20count 測試次數
 21arr_len 動態生成的測試數組的長度
 22show是否顯示每次測試用時
 23*/
 24
 25typedef void MT(int* , unsigned, int);
 26MT left_shift_0, left_shift_1, left_shift_2, left_shift_3;
 27MT left_shift_4, left_shift_5;
 28void test(MT *ff[], unsigned sz, unsigned count=1, unsigned arr_len=1e6, bool show=0);
 29
 30int main()
 31{
 32   MT *ff[]={left_shift_0,left_shift_1,left_shift_2,left_shift_3,left_shift_4,left_shift_5};
 33   unsigned sz=sizeof(ff)/sizeof(ff[0]);
 34   test(ff, sz, 4e4,1e3);
 35   test(ff, sz, 4,2e7,1);
 36   test(ff, sz, 4e6,100);
 37}
 38
 39void left_shift_0(int* arr, unsigned n,int k)
 40{
 41  if (n==0) return;
 42  k %= n;
 43  if (k==0) return;
 44  if (k<0) k += n;
 45  vector<int> a(n);
 46  int * const p=&a[0];
 47  copy(arr+k,arr+n,p);
 48  copy(arr,arr+k,p+n-k);
 49  copy(p,p+n,arr);
 50}
 51
 52
 53void my_reserve(int* arr, int n)
 54{
 55  int *p=arr, *q=arr+n-1;
 56  int tmp;
 57  while (p<q){
 58    tmp = *p;
 59    *p++ = *q;
 60    *q-- = tmp;
 61  }
 62}
 63
 64
 65void left_shift_1(int* arr, unsigned n,int k)
 66{
 67  if (n==0) return;
 68  k %= n;
 69  if (k==0) return;
 70  if (k<0) k += n;
 71  my_reserve(arr,k);
 72  my_reserve(arr+k,n-k);
 73  my_reserve(arr,n);
 74}
 75
 76
 77void left_shift_2(int* arr, unsigned n,int k)
 78{
 79  if (n==0) return;
 80  k %= n;
 81  if (k==0) return;
 82  if (k<0) k += n;
 83  int tmp;
 84  int *low=arr, *last=arr+n, *mid=arr+k, *high=mid;
 85  while (mid != last){
 86    tmp = *low;
 87    *low++ = *high;
 88    *high++ = tmp;
 89    if (low==mid) mid=high;
 90    else if (high==last) high=mid;
 91  }
 92}
 93
 94
 95void left_shift_3(int* arr, unsigned n,int k)
 96{
 97  if (n==0) return;
 98  k %= n;
 99  if (k==0) return;
100  if (k<0) k += n;
101  int tmp,count=n;
102  int *first=arr, *last=arr+n, *cur=first, *next=first;
103  tmp = *first;
104  while (count--){
105    cur=next;
106    next += k;
107    if (next >= last)  next -= n;
108    if (next != first) *cur=*next;
109    else{
110      *cur = tmp;
111      tmp = * ++first;
112      next = first;
113    }
114  }
115}
116
117
118unsigned my_gcd(unsigned a, unsigned b)
119{
120  unsigned min=a, max=b,tmp;
121  if (a>b) { min=b; max=a;}
122  while (min){
123    tmp=min;
124    min=(max-min)%min;
125    max=tmp;
126  }
127  return max;
128}
129
130
131void left_shift_4(int* arr, unsigned n,int k)
132{
133  if (n==0) return;
134  k %= n;
135  if (k==0) return;
136  if (k<0) k += n;
137  int tmp;
138  unsigned i,j;
139  int *first=arr, *last=arr+n, *cur=first, *next=first;
140  unsigned count1=my_gcd(k,n);
141  unsigned count2=n/count1;
142  for (i=0; i<count1; ++i, ++first){
143    tmp=*first;
144    next=first;
145    for (j=0; j<count2; ++j){
146      cur = next;
147      next += k;
148      if (next >= last) next -= n;
149      *cur=*next;
150    }
151    *cur=tmp;
152  }
153}
154
155void left_shift_5(int* arr, unsigned n,int k)
156{
157  if (n==0) return;
158  k %= n;
159  if (k==0) return;
160  if (k<0) k += n;
161  rotate(arr,arr+k,arr+n);
162}
163
164
165void test(MT *ff[], unsigned sz, unsigned count, unsigned arr_len, bool show)
166{
167  clock_t tb,te;
168  unsigned i,j;
169  int k;
170  vector<int> arr(arr_len);
171  vector<clock_t> total(sz);
172  srand(time(0));
173  for (i=0; i <count; ++i ){
174    k = rand();
175    k -= rand();
176    if (show)  cout<< "K: "<< k << "\n";
177    for (j=0; j<sz; ++j){
178      tb = clock();
179      ff[j](&arr[0],arr_len,k);
180      te = clock();
181      total[j] += te-tb;
182      if (show) cout<< j << " :  "<< te-tb<< "  ms\n";
183    }
184    if (show) cout<<endl;
185  }
186    cout<<"\nTotal: \n";
187    for (j=0; j<sz; ++j){
188      cout<<j<<"  "<< total[j]<<"  ms\n";
189    }
190    cout<<endl;
191}
192
193
194
195
196