C语言高效实现向量循环移位

2020-01-06 20:15:53于海丽

第三种方法(求逆法):令V=ab(其中a为要移位的个数),①对向量V中的前a个元素做求逆操作得到V'=a'b;②对向量V中的接下来的b个元素做求逆操作得到V''=a'b';③对整个向量V做求逆操作得到V'''=(a'b')'=ba。(同阶方阵A,B有(AB)'=B'A')为了验证该操作是否可行,以文章开始处所举的例子(12345循环移动2个位置)进行求逆操作:12345→(①)21345→(②)21543→(③)34512,结果成立,说明该操作可行。而求逆操作中所包含的思想其实很简单:我们在观察一个字符串的时候往往是从左往右看的,而要循环移动其中i位,实际是将这i个字符放在整个串的末尾。而如果我们从右往左看呢?我们发现其实原本在字符串中的长度为i的子串到了整个串的末尾(即54321),我们发现两个子串的长度换好了,但是每个子串是逆序排列的,这个时候对两个子串各做一次求逆操作不就得出了最终的结果了吗?这种方法所带来的思考是:实际解决一个问题的时候,如果发现考虑的思路遇到较大阻碍,换个视角看问题往往能有意想不到的效果。

以上方法的伪码实现为:


/*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:对于第三种方法,著名计算机科学家,unix以及C语言前身B语言的设计者Ken•Thompson在编辑器中使用这种求逆代码时就主张将该代码作为一种常识。

至此三种方法都介绍完了,细心的读者也许发现前两种方法只进行了n次交换操作,而第三种方法进行了2n次操作,因此第三种方法的性能从运行时间的角度来看应该是三种方法中最差的,理论上是如此,多进行操作的算法往往耗时也越长,但实际呢?我们不妨做个试验来验证一下,为了更加真实的模拟现实,n和i的取值分别如下:

n=10000000,i={21,22,…,100},分别对移位个数在[21,100]之间进行总运行时间的测量,测试代码如下(具备可移植性,在win/linux上均可运行,其中win_xp和linux/ubuntu在本机上测试成功得出相应数据,win_7下的版本在同学的系统上运行得出相应数据):