程式設計珠玑 -- 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逐漸增大，這樣的優勢自然就不存在了。