编程珠玑 -- bitSort

＜C专家编程＞看完了。受益最大的应该就是对声明部分的理解吧，特别是函数指针什么的。通过函数指针，可以实现一个自动机。我是这么想的。另外就是因此而学会了使用vi进行编程。接下来想学写makefile文件，不然文件一多调试修改后又要重新编译好几个文件。

 

回到编程珠玑上。第一篇描述了这样一个问题：在一定的内存限定下（内存大概有1MB）对一个包含有K个小于n (n=10^7)的数据的文件进行排序，可以保证，这K个数据没有一个是重复的（其实就是电话号码）。

 

qsort只能对内存中的数据进行排序，也就是说，要对文件遍历40次，每次读取一定范围的数到内存中，然后进行排序。（如，第一次，读取0～249，999范围内的数据到内存，qsort后输出到新的文件，然后再从文件中读取250,000~499,999的数据。。）这样的话，必须对文件遍历40次。

 

mergeSort只读取一次源文件，但是要开辟很多个临时文件进行辅助排序。

 

有什么办法可以只读一次源文件，写一次output，又不需要临时文件的辅助呢？

 

这个问题有三个特征是一般排序问题不具备的：

1。 数据范围比较小（＜10^7）

2。 没有重复数据

3。 每个数据都很独立，没有其他相联的数据。

 

由于数据没有重复，同时所有数据都小于10^7，我们可以用每个bit来代表一个数据是否存在源文件中（由这些bit组成的表大概需要1.25MB），一边读取文件的时候一边设置相应的位，最后输出的时候检查相应的位是否为1，为1则输出该数字。如果内存严格要求1MB的话，可以分成两次读取。

 

我在实现的时候，写了三个函数，一个用于产生K个不重复的随机数，一个用于设置相应位，一个用于打印由map得到的排序后的结果。总之写了挺长的代码。。大概有100行了，后来看了后面的solution，不禁汗颜，，果然字字珠玑啊，10几行代码就把整个精华都写出来了，贴在这里给大家看看吧：

 

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1+N/BITSPERWORD];

void set( int i ){ a[i>>SHIFT] |= (1<<(i&MASK)); }

void clear( int i ){ a[i>>SHIFT] &= ~(1<<(i&MASK)); }

int test( int i ){ return (a[i>>SHIFT] & (1<<(i&MASK))); }

main(){
	int i=0;
	int j=0;
	for( i=0; i<N; i++ )
		clear(i);
	FILE* fp = fopen( "sortData", "r" );
	if( fp != NULL ){
		while( fscanf( fp, "%d", &i ) != EOF )
			set(i);
		for( i=N-1; i>=0; i-- ){
			if( test(i) ){
				j++;
				printf( "%d: %d\n", j, i );
			}
		}
	}
}

 

再看看我自己写的三个函数：

setMapAtK跟他的set基本是一样的，可是与起来远不如人家紧凑：

//这里考虑到我同时还要利用这个函数来产生不重复的随机数，所以选择了使用返回值
int setMapAtK( int gen, int* map ){
	int num = gen >> 5;
	int bit = gen & 31;
	if( map[num] & (1 << (bit)))
		return 1;
	map[num] = map[num]|(1 << (bit));
	return 0;
}

 printMap就很悲惨了，不过可取的一点是，我是对每个整数进行的操作，当取完最后一个为1的位后该整数就为0，也就是说，没有必要再对这个整数后面的位了。对于稀松集，这样效率是会提高一点的。

void printMap( int* map ){
	int r = 1;
	int i=MAXINT_TEMP-1;
	int size = MAXINT_TEMP>>5;
	int left = MAXINT_TEMP & 31;
	//这里主要考虑到最大整数可能并不是32的整数（虽然在我们的例子中n=10^7是）
	if( left > 0 ){
		int j = left-1;
		unsigned int num = (1<<j);
			int t = map[size];
			while(j>=0 && t ){
				if( map[size]& num ){
					t = (t & (num^(0xFFFF)));
					printf( "%d: %d\n", r++, i );
				}
				j--;
				i--;
				num = (num>>1);
			}
			i -= (j+1);
	}
	int k;
	//这里是主要循环
	for( k=size-1; k>=0; k-- ){
		int j=32;
		unsigned int num = 0x80000000;
			int t = map[k];
			while( j && t ){
				if( map[k] & num ){
					t = (t& (num^(0xFFFFFFFF)));
					printf( "%d: %d\n", r++,i );
				}
				j--;
				i--;
				num = (num>>1);
			}
			i -= j;
	}
}

 试验的结果我的时间是要比它少5、6秒（k=10^6)，不过随着k逐渐增大，这样的优势自然就不存在了。