雁过无痕

《编程之美》读书笔记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