第一章冒頭(2)

4801 ワード
timer アルゴリズム テスト null 保存
練習問題そのプログラマーは1 MBの利用可能なストレージスペースがあると言っていますが、概要で説明したコードには1.25 MBのスペースが必要です.彼は苦労せずに余分な空間を請求することができる.もし1 MB空間が厳しい境界であれば、どのように処理することをお勧めしますか?あなたのアルゴリズムの実行時間はいくらですか?
ビットベクトルで10,000個の整数を表すには10,000,000個のビットが必要であり、10,000,000 bits=1.192 MBである.したがって,プログラマが利用できる1 MBの空間は明らかに不十分であり,2回のアルゴリズムを採用し,1回目は5000,000ビットを用いて0~49999999の間の整数を並べ替え,2回目では5000,000~99999999の間の整数を並べ替えることができる.コードは次のとおりです.
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <boost/timer.hpp>
#include <boost/progress.hpp>

using namespace std;
using namespace boost;

#define  BITSPERDWORD 32          //          32  
#define  SHIFT         5          //     ，         2，         2
#define  MASK         0x1f        //  ，      31
#define  N            10000000    //  10000000 7     

//     0    i    0,    i             false
void resetBits(int * arry, int i)  
{
	arry[i >> SHIFT] &= ~(1 << (i & MASK));  //m%n,n = 2^x ，m%n = m & (n-1)
}

//     0    i    1，    i             true
void setBits(int * arry, int i)
{
	arry[i >> SHIFT] |= (1 << (i & MASK));
}

//  i      
int testBits(int * arry, int i)
{
	return arry[i >> SHIFT] & (1 << (i & MASK));
}

//  [l, u]          
int randint(int l, int u)
{
	return (l + rand() % (u - l + 1));
}


int * geneRand2(int m ,int n)
{
	int i, j;
	int *pArry = new int[n];
	for (i = 0; i < n; i++)  //    
	{
		pArry[i] = i;
	}

	//     
	srand((unsigned)time(NULL));
	for (i = 0; i < m; i++)
	{
		j = randint(i, n - 1);
		int t = pArry[i];
		pArry[i] = pArry[j];
		pArry[j] = t ;
	}
	return pArry;
}


void mySort(int m ,int n)
{
	int i, j = 0, k;
	int *pBitsArry = new int[1 +n / (2 * BITSPERDWORD)]; //      
	int * p = geneRand2(m ,n);
	int *pOutArry = new int[m];  //      

	progress_timer t;

	for (k = 0; k < 2; k++)
	{
		for (i = 0; i < (n / 2); i++)
		{
			resetBits(pBitsArry, i);
		}
		if (0 == k)
		{
			for (i = 0; i < m; i++)
			{
				if (p[i] < (n / 2))
				{
					setBits(pBitsArry, p[i]);
				}
			}
			for (i = 0; i < (n / 2); i++)
			{
				if (testBits(pBitsArry, i))
				{
					pOutArry[j++] = i;
				}
			}
		} 
		else
		{
			for (i = 0; i < m; i++)
			{
				if (p[i] >= (n / 2))
				{
					setBits(pBitsArry, p[i]-(n / 2));
				}
			}
			for (i = n / 2; i < n; i++)
			{
				if (testBits(pBitsArry, (i - n / 2)))
				{
					pOutArry[j++] = i;
	
				}
			}
		}
	}
	cout << t.elapsed()<<endl;     //     0 n-1  m                 
/*	cout<<"..........................."<<endl;
	for (i = 0; i < m; i++)
	{
		cout << pOutArry[i]<<endl;
	}
	cout<<"..........................."<<endl;*/
	delete [] p;
	delete [] pBitsArry;
	delete [] pOutArry;

}

int _tmain(int argc, _TCHAR* argv[])
{
	mySort(10000000,10000000);
	return 0;
}

ソート計算時間は(m=n=1000,000,000):0.859 s
kパスアルゴリズムは、knの時間オーバーヘッドおよびn/kの空間オーバーヘッド内で、n未満の最大n個の反復しない正の整数の並べ替えを完了することができる.
練習問題もしそのプログラマーが整数ごとに1回多く現れるのではなく、整数ごとに最大10回現れると言ったら、あなたはどのように彼を提案しますか?あなたのソリューションは、使用可能なストレージ容量の総量に応じてどのように変化しますか?
10はバイナリの1010、2^3<10<2^4に等しいため、4ビットの半バイトでその出現回数を統計することができ、すなわち4*1000 0000ビットで1000 0000個の正の整数を表す必要がある.練習問題5では,4000,000/kビットを用いてkパス内でファイル全体のソートを完了することができる.
練習問題本書1.4節で説明したプログラムにはいくつかの欠陥がある.まず,入力に2回も現れない整数を仮定する.入力に2回も現れないと仮定した整数です.もしある数が1回を超えたら、何が起こるのでしょうか.この場合、エラー処理関数を呼び出すには、プログラムをどのように変更しますか?入力整数がゼロ以下またはn以上の場合、何が起こりますか?入力が数値でなければどうですか?これらの場合、プログラムはどのように処理しますか?プログラムにはどのような賢明な検査が含まれていますか?プログラムをテストするための小さなデータセットについて説明し、上記およびその他の不良状況を正しく処理する方法を説明します.
1)ある数が1回を超える場合、その数は並べ替えられたファイルに1回しか現れない.setBits()関数を呼び出すと、まず、その数のビットベクトルに対応するビットが0であるかどうかをチェックし、0がその数が初めて現れることを示す場合は、それを1に設定します.そうでなければ、その数が重複していることを示し、異常を投げ出してエラー処理を行うことができる.
2)負数対は符号数があり、その2進数の最上位は1であるが、コンピュータ記憶負数はその2進数形式で直接記憶されるのではなく、逆に1を取って記憶されるため、ゼロ未満を入力するとシフト演算子やビット演算子に誤った値が発生し、アクセス配列が境界を越えるなどの問題が生じる.次のようになります.
#include <iostream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	int a = 10, b = -10;
	cout << (a >> 5) << endl;     
	cout << (a & 31)<<endl;

	cout << (b >> 5) << endl;
	cout << (b & 31)<<endl;
	return 0;
}

出力結果:0
                  10
                   -1
                   22
いずれの整数Aについても、A>0であれば、その補符号はそれ自体に等しい.A<0の場合、その符号化はその符号ビットが不変であり、他のビットはビット毎に逆に1を加算する.
b=10000000000000000000000000001010//bの符号b'=11111111111111111111111110110//bの符号化補正
したがって、b>>5=1111111111111111111 11111111111(算術右シフト、すなわち符号数に対して右シフトの場合、その数の符号ビットに左シフトし、元々1であれば1、元々0であれば0)、つまり-1に等しい.b & 31 = 00000000 0000000000000000 00010110 = 22
入力整数がnより大きいか小さい場合、ビットベクトルデータアクセス限界が発生します.入力が数値でない場合は、まず入力データが整数であるかどうかを確認します.
    
プログラマーのステップアップのアルゴリズム練習(二十四)
最大公約数--ユークリッドアルゴリズムと最小公倍数を求めます