0001 /****************************************************************************************** 0002 * 测试位图 0003 ******************************************************************************************/ 0004 int testBitmap ( int n ) { 0005 bool* B = new bool[n]; //常规位图 0006 Bitmap M ( n ); //高效位图 0007 for ( int t = 0; t < 50; t++ ) { //重复使用位图多次 0008 memset ( B, 0, n * sizeof ( bool ) ); //逐位清零,O(n) 0009 M.reset(); //逻辑清零,O(1) 0010 for ( int i = 0; i < 3 * n; i++ ) { //反复地 0011 Rank k = dice ( n ); //在随机位置上 0012 if ( dice ( 2 ) ) { //以50%的概率插入 0013 B[k] = true; M.set ( k ); 0014 } else { //或50%的概率清除 0015 B[k] = false; M.clear ( k ); 0016 } 0017 } 0018 //M.set( 29 ); //有时可卖个破绽,以反向测试本测试程序 0019 int k; 0020 for ( k = 0; k < n; k++ ) //逐位地对比 0021 if ( B[k] != M.test ( k ) ) //一旦发现不合 0022 break; //随即退出 0023 if ( k < n ) { //并报告(assert:: k == n+1) 0024 printf ( "\n B[]: " ); 0025 for ( int j = 0; j <= k; j++ ) printf ( "%6c", B[j] ? 'x' : ' ' ); 0026 printf ( "\n M[]: " ); 0027 for ( int j = 0; j <= k; j++ ) printf ( "%6c", M.test ( j ) ? 'x' : ' ' ); 0028 printf ( "\n" ); 0029 } else 0030 printf( "Test %4d OK\n", t ); 0031 } 0032 delete [] B; 0033 return 0; 0034 } 0035 0036 /****************************************************************************************** 0037 * 测试位图 0038 ******************************************************************************************/ 0039 int main ( int argc, char* argv[] ) { 0040 if ( 2 > argc ) { printf ( "Usage: %s <size of test>\a\a\n", argv[0] ); return 1; } 0041 srand ( ( unsigned int ) time ( NULL ) ); //设置随机种子 0042 return testBitmap ( atoi ( argv[1] ) ); //启动测试 0043 }