STL源码剖析之rotare的数学原理

发表于 | 更新于 | 分类于

这文章主要想讲一讲 rotate 算法的数学原理以及代码的一点解析.

网上有人讲过这个函数 , 但是直接让我去看某书第几节 , 这….. 当然我去看了一下 , 感觉那本书讲的不是很容易理解 , 这里我尽量以大白话去讲 , 逻辑当然还是严格的.

BidirectionalIterator版

索引从 0 开始 , 设前半段某个元素索引为 x (后半段同理) . 设整个长度为 l . middle 索引为 m .

当我们完成操作时 , x 应该变为 l - m + x

第一个操作 reverse( first , middle ) 后 x 变为 m - x - 1

第二个操作不影响前半段

第三个操作 reverse( first , last ) 后 m - x - 1 变为 l - m + x

RandomAccessIterator版

引理

若有两个正整数 m , n , 且 gcd( m , n ) = d , 那么序列 { m % n , 2m % n , 3m % n , …. , nm % n } 一定是 { 0 , d , 2d , …. , n-d } 的某个排列并重复出现 d 次.

引理证明

设 m = m’ d , n = n’ d , m’ 与 n’ 的最大公因数一定是 1.否则的话 d 可以取更大.

很明显 , 一个数 mod n’ 结果只有 n’ 种可能 ( 0 , 1 , 2 , …. , n’-1 )

而 n’ * m’ 是一定整除 n’ 的

考虑 ( m’ % n’ , 2m’ % n’ , 3m’ % n’ , …. , n’ * m’ % n’ ) 一共 n 个余数 , 而这些余数一定位于那些可能当中 . 接下来我们如果能证明任意两个余数不相等 , 那么我们就可以知道这必定是余数可能的某种排列.

假设 k m’ 与 j m’ 的余数相等( 0 ≤ j ≤ k ≤ n ) . 即 ( k - j ) * m’ % n’ = 0 ,加上 m’ 与 n’ 最大公因数为 1 ,所以必须 ( k - j ) % n’ = 0 ( 可以理解为需要找到数把 n’ 给消掉 , 而 m 不可能贡献任何因数 ) , 而 k - j < n’ , 所以这是不可能的 . 在把 n’ , m’ , 余数所有可能 , 全部乘以 d 以后即可得到引理.

__rotate

1
2
3
4
5
6
7
8
9
10
11
//代码来自书上
template <class RandomAccessIterator, class Distance>
void  __rotate(RandomAccessIterator first, RandomAccessIterator middle,
      RandomAccessIterator last, Distance*,
      random_access_iterator_tag)
{
     Distance n  =  __gcd(last - first, middle - first);  //gcd代码我不放了
     while (n--)
         __rotate_cycle(first, last, frist  +  n, middle - first,
						value_type(first));
}

__rotate_cycle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//代码来自书上
template <class RandomAccessIterator, class Distance, class T>
void  __rotate_cycle(RandomAccessIterator first, RandomAccessIterator last,
                     RandomAccessIterator initial, Distance shift, T*)
{
     T value = *initial;
     RandomAccessIterator ptr1 = initial;
     RandomAccessIterator ptr2 = ptr1 + shift;
     while (ptr2 != initial)
     {
         *ptr1 = *ptr2;
         ptr1 = ptr2;
         if (last - ptr2 > shift)
             ptr2 += shift;
         else
             ptr2 = first + (shift - (last - ptr2));
     }
     *ptr1 = value;
}

代码原理

这里不想讲了 , 一轮 len/gcd 个元素 , 一共 gcd 轮.

你可以自己用纸笔画一下就知道了