C語言高效實(shí)現(xiàn)向量循環(huán)移位
問題：n個(gè)元素的向量V循環(huán)移位（以左移為例）i個(gè)位置，例如12345循環(huán)移動(dòng)2個(gè)位置得到34512.
問題本身非常簡單，以至于我們一看到問題就能想到對應(yīng)的解決策略：申請i個(gè)字節(jié)的動(dòng)態(tài)存儲(chǔ)，將向量區(qū)間[0,i-1]的i個(gè)元素存儲(chǔ)至臨時(shí)存儲(chǔ)器，之后將[i,n]的n-i+1個(gè)元素向左移動(dòng)i個(gè)位置，并將臨時(shí)存儲(chǔ)器中的i個(gè)元素寫回原向量區(qū)間中[n-i+1,n]。但如果我們強(qiáng)加一些限制：在現(xiàn)有可申請內(nèi)存的總量k << i以及所要求的時(shí)間復(fù)雜度為O(n)的情況下如何實(shí)現(xiàn)循環(huán)移位？問題的復(fù)雜度似乎就上了一個(gè)量級。而之所以寫這篇文章，很大程度上是因?yàn)榻酉聛硪榻B的三種方法帶來了對問題本質(zhì)更深入的思考。
方法一(姑且稱之為求模法)：借助一個(gè)臨時(shí)變量temp，temp ← V[0]，V[0] ← V[i%n]，V[i%n] ← V[(2i)%n]…直到(ki)%n =0時(shí)，此時(shí)所要完成的操作即為V[((k-1)i)%n] ← V[0]，而由于變量V[0]的值在被V[i%n]覆蓋之前已存入temp，取而代之的操作即為：V[((k-1)i)%n] ← temp。圖解表示為(圖示的移位個(gè)數(shù)為i=3)：
整個(gè)操作過程借助一個(gè)臨時(shí)變量，經(jīng)過n次左右的操作即完成整個(gè)移位過程，時(shí)間復(fù)雜度滿足O(n)。事實(shí)上，向量中所有的元素都進(jìn)行了移位操作，因此如果當(dāng)完成V[((k-1)i)%n] ← temp操作時(shí)，仍有元素未完成移動(dòng)，此時(shí)從V[1]開始再次進(jìn)行移動(dòng)。因?yàn)槿绻麤]有移動(dòng)全部的元素，則說明最初的i個(gè)元素將分為m(m>1)個(gè)等價(jià)類，所以從V[1]開始再次移動(dòng)是可行的，這歸功于等價(jià)類的性質(zhì)：任何求模等價(jià)類聚集中每個(gè)集合中的每個(gè)元素間隔的長度相等。所以若0和1同屬一個(gè)等價(jià)類，則該等價(jià)類必然包含所有i個(gè)元素。
上述過程的偽碼表示為：
/*LOOPSHIFT(V,i)*/
cnt←0
j←-1
while cnt≠length[V]
do j←j+1
temp←V[j]
k←i+j
while k%n≠j
do V[(k-i)%n]←V[k%n]
k←k+i
cnt←cnt+1
V[(k-i)%n]←temp
cnt←cnt+1
在繼續(xù)深入考慮之前先思考以下兩種情況：①在13個(gè)元素中循環(huán)移動(dòng)5個(gè)元素(12/5) ②在14個(gè)元素中移動(dòng)4個(gè)元素(14/4)，其中⌈⌉表示上取整，⌊⌋表示下取整。
1)在13/5這種情況中，由于(⌈12/5⌉)×5-12=3，每次在5個(gè)元素中以2進(jìn)行循環(huán)迭代，在[0,4]這5個(gè)元素中的迭代次序?yàn)?不考慮向量中的其他元素)：0→3→1(6%5)→4(9%5)→2(12%5)→0(15%5)，因此最終通過上述代碼的一次內(nèi)層循環(huán)即可完成整個(gè)移位操作。
2)在14/4這種情況中，由于(⌈14/4⌉)×4-14=2，每次在4個(gè)元素中也以2進(jìn)行循環(huán)迭代，在[0,3]這5個(gè)元素中的迭代次序?yàn)椋?→2→0(4%2)→1(退出內(nèi)層循環(huán)，簡單從下標(biāo)為1的元素重新開始移動(dòng))→3→1(5%2)，因此最后在外層執(zhí)行兩次迭代才最終完成整個(gè)移位操作。
通過這兩個(gè)例子可以發(fā)現(xiàn)外層的迭代次數(shù)(即等價(jià)類的個(gè)數(shù))最終和整個(gè)向量的長度以及所要移位的個(gè)數(shù)有關(guān)，具體的關(guān)系為：cnt = gcd(n,i) 其中n=length[A]，cnt為外層迭代的次數(shù)。
由于任何求模等價(jià)類聚集中每個(gè)集合中的元素間隔的長度相等(由上可知，即實(shí)際過程中未進(jìn)行模運(yùn)算之前的值)，據(jù)此證明過程如下：
因?yàn)閘ength[V]=n且移位個(gè)數(shù)為i，因此必然存在大于等于n且被i整除的數(shù)k=⌈n/i⌉×i
由n= α×gcd(n,i)且i=β×gcd(n,i)，k=⌈n/i⌉×β×gcd(n,i)
因此在i個(gè)元素上每次移位的個(gè)數(shù)為iter=k-n=(⌈n/i⌉×β-α)×gcd(n,i)，即iter能被gcd(n,i)整除
由于對元素求模各等價(jià)類的個(gè)數(shù)即為等價(jià)類中每個(gè)元素的間隔長度，因此實(shí)際在i個(gè)元素中進(jìn)行iter個(gè)移位所得的等價(jià)類即為：
i×iter/lcm(n,i)=gcd(i,iter)=gcd(i,(⌈n/i⌉×β-α)×gcd(n,i))，由于i=β×gcd(n,i)可得gcd(β,⌈n/i⌉×β-α)=1
由此可知gcd(i,iter)=gcd(n,i)，因此結(jié)論得證，共有cnt=gcd(n,i)個(gè)等價(jià)類，每個(gè)等價(jià)類的代表所構(gòu)成的集合為{0,1,…,cnt-1}（用近世代數(shù)的術(shù)語來說，也就是旋轉(zhuǎn)產(chǎn)生的置換群的陪集個(gè)數(shù)）。
因此上述偽碼可重寫為：
/*LOOPSHIFT(V,i) --gcd version*/
for cnt←0 to gcd(n,i)-1 /*n=length[V], "cnt←0 to n"means assign cnt in [0,n] */
do temp←V[cnt]
k←i
for j←1 to (length[V]/gcd(n,i))-1
do V[(k-i)%n]←V[k%n]
k←k+i
V[(k-i)%n]←temp
第二種方法(遞歸法)：令V=ab(a為要移位的個(gè)數(shù)，length[a]與length[b]不一定相等)，則旋轉(zhuǎn)向量V實(shí)際就是交換向量ab得到ba，假定length[a]<length[b]，分解向量b=αβ，使得length[a]=length[β]，同樣借助一個(gè)臨時(shí)變量temp可實(shí)現(xiàn)向量a和β的交換，可得到第一次迭代之后的向量為βαa，接下來在對βα向量執(zhí)行同樣地交換，執(zhí)行一系列交換之后最終得到向量ba，而遞歸最終到達(dá)不動(dòng)點(diǎn)(fix-point)的條件即為所要交換的兩個(gè)向量長度相等，即移位值為0。實(shí)際就是將原問題分解為一系列性質(zhì)類似的子問題，利用分治的思想逐個(gè)擊破，最終達(dá)到整體交換的目標(biāo)。
以上方法的偽碼實(shí)現(xiàn)為：
/*LOOPSHIFT(V,i) --recurrence version*/
//RECSHIFT(V, i, low, high) /*low:lower_bound high:higher_bound*/
if low=high || high<i /*i is a fix value*/
then return
if i-low>high-i+1 /*select a min value as the count of reversion*/
then revcnt←high-i+1
flag←1 /*set the flag value low bound increase*/
else revcnt←i-low
for j←0 to revcnt-1 /*swap the elem in the vector i times*/
do temp←V[low+j]
V[low+j]←V[high+1+j-revcnt]
V[high+1+j-revcnt]←temp
if flag=1
then low←low+revcnt
else high←high-revcnt
RECSHIFT(V,i,low,high) /*call itself*/
第三種方法(求逆法)：令V=ab(其中a為要移位的個(gè)數(shù))，①對向量V中的前a個(gè)元素做求逆操作得到V'=a'b；②對向量V中的接下來的b個(gè)元素做求逆操作得到V''=a'b'；③對整個(gè)向量V做求逆操作得到V'''=(a'b')'=ba。(同階方陣A，B有(AB)'=B'A')為了驗(yàn)證該操作是否可行，以文章開始處所舉的例子(12345循環(huán)移動(dòng)2個(gè)位置)進(jìn)行求逆操作：12345→(①)21345→(②)21543→(③)34512，結(jié)果成立，說明該操作可行。而求逆操作中所包含的思想其實(shí)很簡單：我們在觀察一個(gè)字符串的時(shí)候往往是從左往右看的，而要循環(huán)移動(dòng)其中i位，實(shí)際是將這i個(gè)字符放在整個(gè)串的末尾。而如果我們從右往左看呢？我們發(fā)現(xiàn)其實(shí)原本在字符串中的長度為i的子串到了整個(gè)串的末尾(即54321)，我們發(fā)現(xiàn)兩個(gè)子串的長度換好了，但是每個(gè)子串是逆序排列的，這個(gè)時(shí)候?qū)蓚€(gè)子串各做一次求逆操作不就得出了最終的結(jié)果了嗎？這種方法所帶來的思考是：實(shí)際解決一個(gè)問題的時(shí)候，如果發(fā)現(xiàn)考慮的思路遇到較大阻礙，換個(gè)視角看問題往往能有意想不到的效果。
以上方法的偽碼實(shí)現(xiàn)為：
/*LOOPSHIFT(V,i) --reverse version*/ //REVERSE(V,i,high) /*high=high_bound*/ REVERSE(V,0,i-1) REVERSE(V,i,high) REVERSE(V,0,high) //-------------------------------------------------- REVERSE(V,low,high) /*function body*/ for j←0 to ((high-low+1)/2)-1 do temp←V[low+j] V[low+j]←V[high-j] V[high-j]←temp
ps:對于第三種方法，著名計(jì)算機(jī)科學(xué)家，unix以及C語言前身B語言的設(shè)計(jì)者Ken•Thompson在編輯器中使用這種求逆代碼時(shí)就主張將該代碼作為一種常識(shí)。
至此三種方法都介紹完了，細(xì)心的讀者也許發(fā)現(xiàn)前兩種方法只進(jìn)行了n次交換操作，而第三種方法進(jìn)行了2n次操作，因此第三種方法的性能從運(yùn)行時(shí)間的角度來看應(yīng)該是三種方法中最差的，理論上是如此，多進(jìn)行操作的算法往往耗時(shí)也越長，但實(shí)際呢？我們不妨做個(gè)試驗(yàn)來驗(yàn)證一下，為了更加真實(shí)的模擬現(xiàn)實(shí)，n和i的取值分別如下：
n=10000000,i={21,22,…,100}，分別對移位個(gè)數(shù)在[21,100]之間進(jìn)行總運(yùn)行時(shí)間的測量，測試代碼如下(具備可移植性，在win/linux上均可運(yùn)行，其中win_xp和linux/ubuntu在本機(jī)上測試成功得出相應(yīng)數(shù)據(jù)，win_7下的版本在同學(xué)的系統(tǒng)上運(yùn)行得出相應(yīng)數(shù)據(jù))：
//#define __LINUX__
#define __WINDOWS__
#include <stdio.h>
#ifdef __WINDOWS__
#include <memory.h>
#include <Windows.h>
#endif
#ifdef __LINUX__
#include <string.h>
#include <sys/time.h>
#include <unistd.h>
#endif
#define cntoffun 3
#define cntofi 80
#define start 20
#ifdef __WINDOWS__
#define mintomillsec (60*1000)
#define sectomillsec 1000
#endif
#ifdef __LINUX__
#define sectomicrosec (1e6)
#define microsectomillisec (1e-3)
#define startp 0
#define endp 1
#endif
/*i from 21 to 100*/
#define v_length 10000000
char vec[v_length];
int gcd(int n, int i);
void swap(char *a,char *b);
void loopshift_gcd(char v[],int i,int high);
void recshift(char v[],int i,int low,int high);
void reverse(char v[],int low,int high);
void reverseshift(char v[],int i,int high);
typedef int DWORD;
int main()
{
#ifdef __WINDOWS__
SYSTEMTIME tm;
#endif
#ifdef __LINUX__
struct timeval tv[2];
#endif
char colofline[]="yrb";
DWORD s_millsec,e_millsec;
FILE *fp;
int i,j;
size_t timearray[cntoffun][cntofi];
memset(vec,0,sizeof(vec));
memset(timearray,0,sizeof(timearray));
#ifdef __WINDOWS__
fp=fopen("F:\\gettimeofrp.m","w");
#endif
#ifdef __LINUX__
fp=fopen("/home/raine/Desktop/gettimeofrp.m","w");
#endif
for(j=0;j<cntoffun;j++)
{
for(i=start+1;i<=(start+cntofi);i++)
{
printf("func[%d]\tcount_of_shift[%d]\t",j,i);
#ifdef __WINDOWS__
GetLocalTime(&tm);
s_millsec=tm.wMinute*mintomillsec+tm.wSecond*sectomillsec+ \
tm.wMilliseconds;
#endif
#ifdef __LINUX__
gettimeofday(&tv[startp],NULL);
#endif
if (j==0)
loopshift_gcd(vec,i,v_length-1);
else if (j==1)
recshift(vec,i,0,v_length-1);
else
reverseshift(vec,i,v_length-1);
#ifdef __WINDOWS__
GetLocalTime(&tm);
e_millsec=tm.wMinute*mintomillsec+tm.wSecond*sectomillsec+ \
tm.wMilliseconds;
timearray[j][i-start-1] = e_millsec - s_millsec;
#endif
#ifdef __LINUX__
gettimeofday(&tv[endp],NULL);
timearray[j][i-start-1] = ((tv[endp].tv_sec-tv[startp].tv_sec)*sectomicrosec+\
(tv[endp].tv_usec-tv[startp].tv_usec))*microsectomillisec;
#endif
printf("use time %d\n",timearray[j][i-start-1]);
}
}
/*matlab code*/
fprintf(fp,"clear;\nclc;\nord_x=[...\n");
for(i=start+1;i<=(start+cntofi);i++)
{
fprintf(fp,"%d ",i);
if(i%10==0) fprintf(fp,"...\n");
}
fprintf(fp,"];\n\n");
for(i=0;i<cntoffun;i++)
{
fprintf(fp,"ord_yfunc%d=[...\n",i+1);
for(j=0;j<cntofi;j++)
{
fprintf(fp,"%d ",timearray[i][j]);
if ((j+1)%10 == 0) fprintf(fp,"...\n");
}
fprintf(fp,"];\n\n");
}
fprintf(fp,"title('performance of three function');\n");
fprintf(fp,"xlabel('x=[21:100]');\n");
fprintf(fp,"ylabel('the time three function use(millisecond)');\n");
fprintf(fp,"hold on;\n");
for(i=0;i<cntoffun;i++)
fprintf(fp,"plot(ord_x,ord_yfunc%d,'%c*-');\n",i+1,colofline[i]);
fprintf(fp,"legend('func1'");
for(i=1;i<cntoffun;i++)
fprintf(fp,",'func%d'",i+1);
fprintf(fp,");");
fclose(fp);
printf("\nhave been finished,press any key to quit ^ ^\n");
#ifdef __WINDOWS__
system("pause");
#endif
}
void swap(char *a,char *b)
{
char temp=*a;*a=*b;*b=temp;
}
int gcd(int n,int i) /*n:length[v], i:shift times, n>=i*/
{
int temp=i;
while(n%i != 0)
{
temp = n%i;
n=i; i=temp;
}
return temp;
}
void loopshift_gcd(char v[],int i,int high)
{
size_t length = gcd(high+1,i);
size_t cntofelem = ((high+1)/length)-1;
int cnt, j, k;
char temp;
for(cnt=0;cnt<length;cnt++)
{
temp=v[cnt];
k=i;
for(j=1;j<=cntofelem;j++)
{
v[(k-i)%(high+1)] = v[k%(high+1)];
k+=i;
}
v[(k-i)%(high+1)]=temp;
}
}
void recshift(char v[],int i,int low,int high)
{
int revcnt,j,temp=0;
if(low == high || high<i) return;
if (i-low>high-i+1)
revcnt=high-i+1,temp=1;
else
revcnt=i-low;
for(j=0;j<=revcnt-1;j++)
swap(&v[low+j],&v[high+1+j-revcnt]);
if(temp == 1)
low+=revcnt;
else
high-=revcnt;
recshift(v,i,low,high);
}
void reverse(char v[],int low,int high)
{
int j;
for(j=0;j<(high-low+1)/2;j++)
swap(&v[low+j],&v[high-j]);
}
void reverseshift(char v[],int i,int high)
{
reverse(v,0,i-1);
reverse(v,i,high);
reverse(v,0,high);
}
結(jié)果運(yùn)行之后所得到的M文件(matlab)如下(只展示了xp下所得出的版本)：
%win_xp version
clear;
clc;
ord_x=[...
21 22 23 24 25 26 27 28 29 30 ...
31 32 33 34 35 36 37 38 39 40 ...
41 42 43 44 45 46 47 48 49 50 ...
51 52 53 54 55 56 57 58 59 60 ...
61 62 63 64 65 66 67 68 69 70 ...
71 72 73 74 75 76 77 78 79 80 ...
81 82 83 84 85 86 87 88 89 90 ...
91 92 93 94 95 96 97 98 99 100 ...
];
ord_yfunc1=[...
187 157 156 141 156 156 172 187 172 187 ...
204 187 203 219 203 219 219 250 234 234 ...
250 250 266 266 265 281 266 297 281 297 ...
313 312 313 328 312 344 359 360 359 359 ...
375 360 375 375 375 390 391 391 390 391 ...
391 406 390 407 422 406 406 391 406 406 ...
391 422 407 421 422 469 469 422 484 484 ...
422 407 437 422 422 437 453 485 500 453 ...
];
ord_yfunc2=[...
16 15 16 15 16 16 15 16 16 15 ...
16 31 16 15 0 0 0 0 31 0 ...
16 16 15 16 16 15 16 15 16 16 ...
15 16 16 15 16 15 16 16 15 16 ...
16 15 16 31 16 15 16 15 16 15 ...
32 15 16 16 15 15 16 16 15 16 ...
15 16 15 16 16 15 16 16 15 15 ...
16 16 15 16 16 15 16 15 16 16 ...
];
ord_yfunc3=[...
16 16 15 16 15 16 16 15 16 16 ...
15 15 16 16 15 16 16 15 16 15 ...
32 15 16 16 15 16 15 16 15 16 ...
16 15 16 15 16 16 15 16 16 31 ...
15 16 16 15 16 16 15 16 15 16 ...
31 16 16 15 16 15 16 15 16 16 ...
15 16 16 16 15 16 16 15 16 31 ...
16 15 16 16 15 16 15 16 16 31 ...
];
title('performance of three function(Win xp)');
xlabel('x=[21:100]');
ylabel('the time three function use(millisecond)');
hold on;
plot(ord_x,ord_yfunc1,'y*-');
plot(ord_x,ord_yfunc2,'r*-');
plot(ord_x,ord_yfunc3,'b*-');
legend('func1','func2','func3');
執(zhí)行所得圖形化表示如下（順序分別為win_xp，win_7，GUN/Linux_Ubuntu）：
由于winxp版本的運(yùn)行時(shí)間是在真實(shí)硬件環(huán)境中得出的，而win7版本則在同學(xué)的機(jī)器上得出，linux版本的則是用軟件模擬出來的硬件環(huán)境，因此進(jìn)行橫向比較往往沒有多大意義。而進(jìn)行縱向比較可得出的結(jié)論如下：
①由圖示可知，算法一（即求模算法）是性能最差的，算法二和算法三性能相當(dāng)。這與我們當(dāng)初預(yù)測的算法的操作次數(shù)越少則運(yùn)行時(shí)間越短存在悖逆，想想這是為什么？
②各算法實(shí)際運(yùn)行過程中往往還需要考慮操作系統(tǒng)的調(diào)度以及進(jìn)程切換的影響。由windows兩個(gè)版本的圖示可知，該算法的運(yùn)行相對算法中需要移位的個(gè)數(shù)的增量相對比較穩(wěn)定。因此，從某種意義上可以看出windows的調(diào)度子系統(tǒng)相對比較穩(wěn)定。
對于結(jié)論①中提出的問題，聰明的你是否已經(jīng)有了自己的答案？沒錯(cuò)，那就是傳說中的存儲(chǔ)器層次結(jié)構(gòu)的老朋友：局部性。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
在?Visual?Studio?2019?的基礎(chǔ)上，新版集成開發(fā)壞境提供了非常多的改進(jìn)，包括對?64?位、.NET?6?的支持，為核心調(diào)試器提供更好的性能。本文給大家分享Visual?Studio?2022?激活碼，需要的朋友參考下吧2021-12-12
c++讀取數(shù)據(jù)文件到數(shù)組的實(shí)例
今天小編就為大家分享一篇c++讀取數(shù)據(jù)文件到數(shù)組的實(shí)例，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-07-07
這篇文章非常詳細(xì)的講解了C語言中指針的概念,包含多種方法,多種定義,全面的說明了C語言的特性，希望能給你帶來幫助2021-08-08
如何實(shí)現(xiàn)socket網(wǎng)絡(luò)編程的多線程
首先，學(xué)好計(jì)算機(jī)網(wǎng)絡(luò)知識(shí)真的很重要。雖然，學(xué)不好不會(huì)影響理解下面這個(gè)關(guān)于宏觀講解，但是，學(xué)好了可以自己打漁吃，學(xué)不好就只能知道眼前有魚吃卻打不到漁。在Java中網(wǎng)絡(luò)程序有2種協(xié)議：TCP和UDP,下面可以和小編一起學(xué)習(xí)下2019-05-05
這篇文章主要個(gè)給大家介紹了關(guān)于Qt自定義表頭實(shí)現(xiàn)過濾功能的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用Qt具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-07-07
C/C++?for?語句的要點(diǎn)與注意事項(xiàng)小結(jié)
C/C++ 中的?for?語句是一種常用的循環(huán)結(jié)構(gòu),用于重復(fù)執(zhí)行一段代碼,直到滿足某個(gè)條件為止,這篇文章主要介紹了C/C++?for?語句的要點(diǎn)與注意事項(xiàng),需要的朋友可以參考下2024-06-06
VisualStudio?制作Dynamic?Link?Library動(dòng)態(tài)鏈接庫文件的詳細(xì)過程
這篇文章主要介紹了VisualStudio?制作Dynamic?Link?Library動(dòng)態(tài)鏈接庫文件的詳細(xì)過程，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-08-08
這篇文章主要為大家詳細(xì)介紹了用C語言實(shí)現(xiàn)一個(gè)掃雷小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-09-09
Qt5.9繼承QObject創(chuàng)建多線程實(shí)例
本文主要介紹了Qt5.9繼承QObject創(chuàng)建多線程實(shí)例，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-09-09
Qt學(xué)習(xí)筆記之QPalette調(diào)色板類
這篇文章主要為大家詳細(xì)介紹了Qt學(xué)習(xí)筆記之QPalette調(diào)色板類，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-07-07