《编程之美》读书笔记09: 2.17 数组循环移位
对长度为n的数组(ab)左移k位,最直接的方法,就是用stl的rotate函数(stl针对三种不同的迭代器,提供了三个版本的rotate)。但在某些情况下,用stl的rotate效率极差。
对数组循环,可以采用的方法有:
① 动态分配一个同样长度的数组,将数据复制到该数组并改变次序,再复制回原数组。
② 利用ba=(br)r(ar)r=(arbr)r,通过三次反转字符串。
③ 分组交换(尽可能使数组的前面连续几个数为所要结果):
若a长度大于b,将ab分成a0a1b,交换a0和b,得ba1a0,只需再交换a1 和a0。
若a长度小于b,将ab分成ab0b1,交换a和b0,得b0ab1,只需再交换a 和b0。
通过不断将数组划分,和交换,直到不能再划分为止。分组过程与求最大公约数很相似。
④ 所有序号为 (i+t*k) % n (i为指定整数,t为任意整数),会构成一个循环链(共有gcd(n,k)个,gcd为n、k的最大公约数),每个循环链上的元素只要移动一个位置即可,总共交换了n次。
stl的rotate的三种迭代器,分别使用了后三种方法。
多数情况下,前三种方法效率都比较高,第一种方法过分要求内存,第四种方法,元素间平均交换次数最少,理论上效率应该是最高的,但在n和k都很大时,其效率相当差(由于每次交换访问的内存不连续,在n和k比较大时,内存访问开销很大,因为cache line命中率很低,又不断跨页访问内存。)。方法三的平均交换次数要少于方法二,但判断次数相对要多,效率相差不是太大,在大数组时方法三效率比较高,但同一个小数组左移几十万次,方法二效率略高,毕竟整个数组都可以被cache,内存访问开销小,判断次数对效率影响较大。
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
测试代码
1
// 2.17_rotate.cpp by flyinghearts#qq.com
2![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
3
#include <iostream>
4
#include <vector>
5
#include <algorithm>
6
#include <ctime>
7
#include <cstdlib>
8
using namespace std;
9![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
10![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
11
left_shift_0 通过复制到临时数组
12
left_shift_1 三次反转
13
left_shift_2 分组交换
14
left_shift_3 循环交换
15
left_shift_4 循环交换(先求最大公约数,确定次数)
16
left_shift_5 stl的rotate
17![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
18
test函数:
19
数组ff存放要测试的函数
20
count 测试次数
21
arr_len 动态生成的测试数组的长度
22
show是否显示每次测试用时
23
*/
24![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
25
typedef void MT(int* , unsigned, int);
26
MT left_shift_0, left_shift_1, left_shift_2, left_shift_3;
27
MT left_shift_4, left_shift_5;
28
void test(MT *ff[], unsigned sz, unsigned count=1, unsigned arr_len=1e6, bool show=0);
29![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
30
int main()
31![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
32![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
39
void left_shift_0(int* arr, unsigned n,int k)
40![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
52![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
53
void my_reserve(int* arr, int n)
54![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
55
int *p=arr, *q=arr+n-1;
56
int tmp;
57![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (p<q)
{
58
tmp = *p;
59
*p++ = *q;
60
*q-- = tmp;
61
}
62
}
63![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
64![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
65
void left_shift_1(int* arr, unsigned n,int k)
66![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
76![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
77
void left_shift_2(int* arr, unsigned n,int k)
78![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
94![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
95
void left_shift_3(int* arr, unsigned n,int k)
96![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (count--)
{
105
cur=next;
106
next += k;
107
if (next >= last) next -= n;
108
if (next != first) *cur=*next;
109![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
110
*cur = tmp;
111
tmp = * ++first;
112
next = first;
113
}
114
}
115
}
116![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
117![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
118
unsigned my_gcd(unsigned a, unsigned b)
119![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
120
unsigned min=a, max=b,tmp;
121![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (a>b)
{ min=b; max=a;}
122![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (min)
{
123
tmp=min;
124
min=(max-min)%min;
125
max=tmp;
126
}
127
return max;
128
}
129![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
130![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
131
void left_shift_4(int* arr, unsigned n,int k)
132![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i=0; i<count1; ++i, ++first)
{
143
tmp=*first;
144
next=first;
145![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
155
void left_shift_5(int* arr, unsigned n,int k)
156![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
164![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
165
void test(MT *ff[], unsigned sz, unsigned count, unsigned arr_len, bool show)
166![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i=0; i <count; ++i )
{
174
k = rand();
175
k -= rand();
176
if (show) cout<< "K: "<< k << "\n";
177![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (j=0; j<sz; ++j)
{
188
cout<<j<<" "<< total[j]<<" ms\n";
189
}
190
cout<<endl;
191
}
192![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
193![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
194![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
195![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
196![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)