『アルゴリズムノート』(一)——日付差問題、ハッシュ(ハッシュ検索)

学習内容はすべて胡凡、曽磊が編集した「アルゴリズムノート」から来て、その中の内容を総括して整理して自分の復習と省察に便利である.
日付処理の問題
日付処理の問題は一般的に2つに分けられます.1つは、指定した日数の後の日付が何であるかを計算することです.もう1つは、ヘッダーと末尾の2つの日付を指定し、それらの間の日数を計算します.このような問題は主に考慮しなければならないのは、平閏年問題と大小月問題であるため、細部の問題が複雑になることがある.他の万年暦表の作成に似ているのは、上記の2つの問題に基づいている.
構想
シミュレーション法で解くことができる.私たちの日常生活のカウントパターンのように、日数を毎日加算し、進位が必要な場所に遭遇したら月に1、日数を1、年に1、月に1を加算します.毎月の日数の読み取りを容易にするために、毎月の日数(2 Dは閏年を表す)を格納するために直接2 D配列を指定し、2 D目が0の場合は平年、1の場合は閏年とします.速度を上げるには、2番目の日付の年と1が異なるまで年を加算します(18年1月と16年4月など、同年に年をまたぐ状況を誤って計算しやすい場合).配列の1次元数の下付きを実際の月に対応させるため、13カ月を設け、0カ月目を空にした.

//    ：
//     ，          ，          ，
//             
//  ：20130101
//  ：20130105
//  ：5
#include
using namespace std;
int month[13][2]={
     {
     0,0},{
     31,31},{
     28,29},{
     31,31},{
     30,30},{
     31,31},{
     30,30},
				{
     31,31},{
     31,31},{
     30,30},{
     31,31},{
     30,30},{
     31,31}	};
bool isleap(int year){
     
	return((year%4==0&&year%100!=0) || (year%400==0));
}
int main(){
     
	
	int time1,y1,m1,d1;
	int time2,y2,m2,d2;
	while(cin>>time1>>time2){
     
		if(time1>time2){
     
			int temp = time1;
			time1 = time2;
			time2 = temp;
		}
		y1=time1/10000,m1=time1%10000/100,d1=time1%100;
		y2=time2/10000,m2=time2%10000/100,d2=time2%100;
		int ans=1;
		while(y1<y2||m1<m2||d1<d2){
     
			d1++;
			if(d1==month[m1][isleap(y1)]+1){
     
				m1++;
				d1=1;
			}
			if(m1==13){
     
				y1++;
				m1=1;
			}
			ans++;
		}
		cout<<ans<<endl; 
	}	
	return 0;
}

ハッシュ＃ハッシュ＃
ハッシュ(Hash)はよく使われる空間で時間を変える方法です.個人的な理解は,2つのリストの間に何らかの対応するマッピング関係が生じることである.たとえば配列はその1つで、格納された整数や文字を配列の下付き記号にマッピングし、迅速にアクセスし、判断することができます.
例えば、以下は例題の解法です.
N個の正の整数を与え、M個の正の整数を与える.このM個の正の整数がそれぞれN個の正の整数に現れたことがあるかどうかを聞く.N個の正の整数{2,3,4,5}とM個の正の整数{1,2}のように、そのうち2だけが中に現れたことがある.ループループ法で解くことは明らかであるが,時間的複雑さはO(NM)に達するので,ハッシュはよい方法である.すなわち,別の配列を開いてN集合の中の数字が出現したか否かを記録し,出現した数字(2,3,4,5)を新しい配列の下付き文字としてマークし,M集合の中の数字が出現した後,M中の数字を新しい配列の下付き文字に対応させて出現したか否かを見て本題を完成する.コードは以下の通りです.

#include
using namespace std;
const int maxn = 10010;
bool hashTable[maxn] = {
     false};
int main(){
     
	
	int n,m,x;
	cin>>n>>m;
	for(int i=0;i<n;i++){
     
		cin>>x;
		hashTable[x] = true;
	} 
	
	for(int i=0;i<m;i++){
     
		cin>>x;
		if(hashTable[x]){
     
			cout<<"YES"<<endl;
		}else{
     
			cout<<"NO"<<endl;
		}
	}
	
	return 0;
} 

簡単なhashTableを新規作成することでこの問題を完成させ,空間を巧みに利用して速度を向上させた.しかし,この問題では大きな数字を入力しているので,配列の座標を利用してマーキングや判断を行うことができる.入力された数字が大きすぎたり、入力された文字が1段になったりすると、その方法は「万能」ではありません.したがって、入力されたものを配列の下付きまたは他のマークしたい要素に変換する方法を通じて、ハッシュ関数Hとして定義されることが多い.要素を1つの関数で整数に変換することで、この要素をできるだけ一意に表す方法があります.

直接座標法(前述の例題のように)

線形変換法H(key)=a*key+b

二乗取中法

除算剰余法H(key)=key%mod

乱数法H(key)=random(key)

折りたたみ法は、キーワードをビット数が等しいいくつかの部分に分割し、これらの部分の重ね合わせと(切り捨てビットのキャリー)をハッシュアドレスとしてとる.シフトオーバーラップ(各部分の最後の位置合わせを再オーバーラップ)と境界オーバーラップ(一方の端から他方の端に向かって境界に沿って逐次折り畳み、次いで位置合わせを加算)

を含む.

デジタル分析法

よく使われるこれらの方法には、空間的な浪費のような不足点が多いことが考えられる.しかし,最も重要なのはマッピングの一意性を確保することが困難である.最も一般的な除算残高法では、発生数は[0,mod)の数が最も多く、より多くの対応関係が必要であればけんかを招きにくい場合を「衝突」と呼ぶ.そのため、これらの衝突を他の方法で解決する.

オープンアドレス法

再ハッシュ法

チェーンアドレス法

パブリックオーバーフロー領域

オープンアドレス法は、衝突を生じるアドレスのために1つのアドレスシーケンスを求める(一定の順序で検出判断する)例えば、線形検出再ハッシュ:既存のH(key)が占有された後、占有されていないH(key)二乗検出再ハッシュを絶えず+1または-1または他の定数+c/-cで探す:既存のH(key)が占有された後、占有されていないH(key)ランダムプローブ再ハッシュを絶えず+/-c^2で探す:同様に、新しいアドレスを探すときに1つの乱数再ハッシュ法を用いてその名の通り、もう一度ハッシュ法を用いると、計算されたタイムチェーンアドレス法が増加して新しいhash値を計算せず、すべてのH(key)の同じKey値をチェーンテーブルで1本の単一チェーンテーブルに接続し、最後に指示通りに直列に接続します.共通オーバーフロー領域法はオーバーフローテーブルを開き,衝突したすべての記録をオーバーフローテーブルに記入し,最後に計算を行う.
上記の方法もハッシュ検索の方法であり,検索対象の要素をハッシュ関数により正の整数にマッピングし,検索時に自分の望む結果を容易に見つけることができる.しかし、一般的には、STLのmapを使ってhashを直接使用する機能が便利で、自分でハッシュテーブルを書く必要はありません.
本の中の問題で終わります:N個の文字列を与えて、更にM個のクエリーの文字列を与えて、各クエリーの文字列がN個の文字列の中で現れる回数を聞きます.

#include
const int maxn = 100;
char S[maxn][5],temp[5];
int hashTable[26*26*26+10];
int hashFunc(char s[],int len){
     
	int id=0;
	for(int i=0;i<len;i++){
     
		id=id*26+(s[i]-'A');
	}
	return id;
}
int main(){
     
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
     
		cin>>s[i];
		int id=hashFunc(s[i],3);   //          
		cout<<"id="<<id<<endl;
		hashTblechar[id]++;  //         +1 
	}
	for(int i=0;i<m;i++){
     
		cin>>temp;
		int id=hashFunc(temp,3);  //    temp      
		cout<<hashTblechar[id]<<endl;  //            
	}
	
	return 0;
}