编程珠玑 -- swap section

编程珠玑第二篇主要提出了三个思想：

1。 二分查找。（binary search）

2。 交换分区。（swap section）

3。 签名。        （signature）

 

二分查找比较耳熟能详，签名的话我觉得是个很好的思想，差不多相当于hashMap吧。这一节我主要关注的是交换分区的算法。

 

问题描述大概如下：旋转一个长度为n的字符串i个位置。比如，字符串"abcdefgh"， n=8, i=3，旋转过后得到"defghabc"。

最容易想到的当然是把前i个字符保存起来，然后把后面的n-i个字符移到前面去，然后再把保存起来的i个字符串粘到n-i个字符后面。时间复杂度为O(n)，空间复杂度为O(i)，我们需要多余的i个空间来存放那些被剪切的字符。有什么办法可以使空间复杂度降为O(1)呢？

 

书里面提到了Gries and Mills的一篇总结报告，＜swap section>。我去网上找了来。报告中提到了三种算法：

1. Dolphine swap.

    Dolphine swap的基本思路是，把x[0]先保存起来，然后把x[i]放到x[0]，把x[2i]放到x[i]...如果i和n互质的话，一个循环就能将所有的字符串都放好，最后把t填充到最后一个空位中。如果i和n不互质的话，则需要做gcd个循环。

void dolphine( char* s, int pos ){
	int n=strlen(s);
	int r = gcd( n, pos );
	int i=0;
	for( i=0; i<r; i++ ){
		char t=s[i];
		int j=i;
		while(1){
			int k = j+pos;
			if( k >= n )
				k -= n;
			if( k == i )
				break;
			s[j] = s[k];
			j =k ;
		}
		s[j] = t;
	}
}

//顺便给出gcd的算法
int gcd( int a, int b ){
	while( a != b ){
		if( a>b )
			a -= b;
		else
			b -= a;
	}
	return a;
}

 

2. Successive swap

     假设i＜n-i，最容易想到的是，前i个字符串最终一定要放在最后面i个位置。把这前后两个i位的字符串进行交换，则接下来的问题变成对前面长度为n-i的字符串进行同样的操作。如果i>n-i，则交换后变成对后面n-i个字符串进行操作。

void successiveSwap( char*s, int pos ){
	if( pos == 0 || pos == strlen(s) )
		return;
	int i, p;
	i = p = pos;
	j = strlen(s)-i;
	while( i!=j ){
		if( i<j ){
	//swap（ char*s, int a, int b, int m)代表将字符串s[a...a+m-1]与s[b...b+m-1]进行交换
			swap( s, p-i, p+j-i, i );
			j -= i;
		}else{
			swap( s, p-i, p, j );
			i -= j;
		}
	}
	swap( p-i, p, i );
}  

3. Reversal swap

Reversal swap是最简单的。把设a=s[0...i-1], b=s[i...n-1]，设如下：设a="abcd", b="kgthe",

a = reverse(a) = "dcba",

b = reverse(b) = "ehtgk"

reserse(ab) = "kgheabcd", 不正是我们想要的结果了么？

 

void reversalSwap( char* s, int pos ){
	reverse( s, 0, pos-1 );
	reverse( s, pos, strlen(s)-1 );
	reverse( s, 0, strlen(s)-1 );
	}

 

Bentley在后面的习题中提出了对这三种算法进行比较的结果，考虑比较大的数组，这样的话，该数组将占用超过一页的内存，随着旋转距离的增加，dolphine算法导致页面的不断换入换出，因此算法的时间开销变大；而SuccessiveSwap由于有比较良好的locality，时间开销是三种算法中最稳定的。ReversalSwap也比较稳定，但是因为进行了两次交换，所以时间在SuccessiveSwap之上。

附件是Gries and Mills的＜swap section>

 

这段日子重新开始看《编程珠玑》以及这篇总结，发现之前给出的代码有点问题，修改了一下。而且我觉得第二章提出的另外两个问题也很有趣，值得我记录下来。

 

所谓的二分查找并不是我们通常以为的那种给定一个排好序的数组，然后进行查找，虽然思想是一致的。比如说给出99个0到100的数，让你找出在该范围中不在这组数据中的一个数（只有99个数，如果没有重复，至少也有两个数不在该数组中）。使用二分查找的思想，对数据进行顺序处理，比方说大于50的数放到一边，小于的放到另一边；至少会有一边的数据小于50个，那么肯定可以在这边的数中找到不存在的那个数，依次类推下去。

 

找同位词，设计一种计算方法，可以使得同位词拥有相同的计算结果。书中给出的想法是对词的字母进行排序，得到一个对应的结果。然后将所有单词的计算结果进行排序，从而使得同位词将被排在一起。