w.rdc.sae.sina.com.cn:3307|nj41yyozkz|nj41yyozkz stl « SAE云计算
Twitter FaceBook
Home
Sina App Engine

Displaying Tag 'stl'

Posted by kobe, and filed under 计算机应用

前一阵糙读了一下STL ALOGRITHM里的算法,觉得有三个给我印象很深,拿到上面来分享一下。
  1,rotate。顾名思义,该算法是绕一点做旋转,当然了,这么说有点忽悠。其实很简单,比如abcdefg以f点rotate就是fgabcde,再以b点做rotate就是bcdefga。实现该算法不难,难的是把情况考虑仔细。首先,选用swap来做,这点一般人都能想到,原因很简单,swap在空间时间上都很高效。如果abcdefg以c做rotate,实际就是把ab看成一个泡,一直往后冒,一直冒到最后为止,这时ab被交换到了最后的位置,其他的也就自然被顺序“拱”到了前面,于是算法完成。但这里有个问题,如果轴在中点往后,那么这样的做法不对,如果以f为轴rotate,a在与g交换后算法就终止了,变成了gbcdefa,很明显算法不完全。所以这个算法最简单明了的实现应该按两种情况来,判断轴在中点的左还是右,然后分别处理。时间复杂度为O(n)。
  STL的做法不完全相同,但基本也是按照这个思路,只不过在第二种情况时,它的轴是变化的,一直向后移动,直到全部交换完成。比较起来我觉得我提到的做法最简单明了,当然了STL也不傻子,STL采用它的做法原因是有的迭代器是不能反向移动的。对STL的做法想了解的更深,可以读它的rotate实现。
  rotate的实现,并不复杂,其实提到它完全是为了给下面的两个算法打铺垫。
 
  2,stable_patrition。patrition很常用,做法也很常见,采用的是快排的前半身,以一个轴从头和从尾分别交换,碰到了即为完成。但是这里提到的是稳定的patrition,做法也不难想,如果对长度为n的数组做stable_patrition,那么开辟出一个和n同样大小的缓冲。从头扫描该数组,如果满足条件则把它放在前面(依次增长),否则则把它放在缓冲里(依次增长),很显然这样的结果是满足条件的序列和不满足条件的序列都为稳定,最后把两个序列合并即可,时间复杂度为O(n)。
  不过,问题没这么简单,如果要求空间复杂度为0呢?这里STL的实现用到了分治的思想,很显然2个数的stable_patrition不需要任何空间消耗,依次类推如果4个数呢?假设有一个数组A,被稳定分为了段A1段A2,同样B被稳定分为了段B1和段B2,如果A在B的前面,很显然:
  A1、B1满足条件,且A1在B1的前面;
  A2、B2不满足条件,且A2在B2的前面;
  如果对A2和B1做rotate操作,则可以保证A1和B1满足条件,且仍然为稳定分类,在前;A2和B2不满足条件,且仍然为稳定分类,在后。如此完成了stable_patrition。
  可以推出递推式为T(n)=2*T(n/2)+n,利用通用公式,求得T(n)=n*log(n),时间复杂度为N*Log(N)。当然STL并不是从最底层的2做起的,换句话说并不是自底向上,而是自顶向下逐步试探已分配的空间是不是大于等于目前分段的长度,如果大于等于则停止分段,采用缓冲区做法,如果不满足则继续分段,最后在归并。时间的复杂度在N*Log(N)和O(N)之间,当然空间消耗也就不能是1了。

 
  3,merge_without_buffer。对于两个有序数组的归并,早有定论,开辟空间,利用两个游标进行归并。这里要提到的是不使用任何缓冲区的两个有序数组的归并。有了上面两个思想的启发,应该不难想到:对于数组A和数组B,A、B皆有序,选B的中间数mb,查找mb在A中的位置(或者插入位置),由此得到了A和B的两个分段:
  A1、B1小于mb;
  A2、B2大于等于mb;
  于是对A2和B1做rotate操作,则再对A1B1和A2B2数组分别归并,这样问题T(n)化简为了两个T(n/2)的问题,最终可以到2个数的归并。问题的时间复杂度也为N*Log(N)。考虑rotate的两种情况,可以在选mb的时候,把长度大的一个数组作为数组B,这样在rotate时,前段小于后段的概率要大一些,这样能提高些许性能。
13th 四 2010
Tags: ,
illuminati
illuminati
 
Designed by