アルゴリズムの並列調査セット

声明:algorithm in cから抜粋し、
セットを調べます:いくつかのN個の要素の集合の応用問題の中で、私達は通常初めに各要素に1つの単一の要素の集合を構成させて、それから一定の順序で同じグループに属する要素のありかの集合を合併して、その間に1つの要素がどのセットの中にあるかを繰り返し探します.
このアルゴリズムは、連通性の問題を解決するために使用することができる.
例えば、コンピュータネットワークにおける2台のホストが接続(検索)するか否かを判断し、接続しない場合は、2台のホストを1つの集合のうち、2台のホストが集合するUnionに統合する方法を考える.
下記の中:
整形配列vec_pair代表ノード
入力対p,q:p,qノード間が連通しているか否かを判断し,連通している場合は次の対の処理を継続し,そうでなければ連通している.
バージョン1クイック検索:
この方法は,連通しているかどうかを迅速に判断できるが,連通の過程はやや遅い,すなわち,速く調べ,ゆっくりしている.
この方法は連通するかどうかを判断する:2つのノード値が同じかどうか、vec_pair[p]==vec_pair[q]は,同じ場合,同じ集合,すなわち連通し,そうでなければ逆である.
並列操作:配列全体をスキャンし、ノード値をvec_にします.pair[p]のノードはvec_に変更されましたpair[q]、または逆
この方法はノードを整形配列で表し、
初期化時は各ノードが連通していないと考えられ,連通していないことを示す方式は,各ノード値がノードのある下付き文字であり,当然,すべての下付き文字が異なり,不通である.

vector<int> vec_pair(N);
	for (int i = 0; i < N; i++)
		vec_pair[i] = i;
bool slow_union(vector<int>::size_type p, vector<int>::size_type q, vector<int> &vec_pair)
{
	vector<int>::size_type temp = vec_pair[p];
	vector<int>::size_type tempq = vec_pair[q];
	vector<int>::size_type size = vec_pair.size();

	for (vector<int>::size_type i = 0; i < size; ++i)
	{
		if (vec_pair[i] == temp)
			vec_pair[i]=tempq;
	}
	return true;
}
bool quik_search(vector<int>::size_type p, vector<int>::size_type q, vector<int> &vec_pair)
{
	return vec_pair[p] == vec_pair[q];
}
int main
{
	while (cin>>p>>q)
	{
		if (slow_search(p,q,vec_pair,rootp,rootq))
			continue;
		quik_union(rootp, rootq, vec_pair);
		copy(vec_pair.begin(), vec_pair.end(), ostream_iterator<int>(cout," "));
		cout << endl;
	}
}

バージョン1から1回で連通するか否かを判断するが,パラレルセット操作は配列全体をスキャンする必要があり,M対,Nノードがあればパラレルセット操作に要する時間はMNである.Nが大きい(百万)場合は、パラレル・セット・オペレーションを最適化する必要があります.
バージョン2の高速パラレル:
ツリー構造では、2つのノードが直接接続されている場合、2つのノードの間に分岐があり、同じツリーに属します.2つのノードが同じセット(連通)にあるかどうかを判断するには、各ノードの親ノードを自分のノード(ルートノード)に向かうまで追跡するだけです.2つのノードが検索中に同じノードが得られると,共通であり,同じ集合に属すると考えられる.
配列初期化後:各ノードは自身を指します.すなわち、各ノードはルートノードです.
検索操作:親ノードをルートノードまで追跡し、p,qのルートノードが同じであれば連通し、そうでなければ連通しない.もちろん,中間のあるノードを見つけたときに同じノードを見つけたときに連通と判断することもできるが,どのようにして中間の同じノードを見つけてからにしようか.
そして操作:pが存在するツリーのうちqが存在するツリーのサブツリー,すなわちqのルートノードを下付きにし,pノードのルートノードに値を与える.
bool slow_search(int p, int q, vector &vec_pair,int &rootp,int &rootq)
{
//vector::size_type rootp, rootq;
for (rootp = p; rootp != vec_pair[rootp]; rootp = vec_pair[rootp]);
for (rootq = q; rootq != vec_pair[rootq]; rootq = vec_pair[rootq]);
return rootp == rootq;
}
bool quik_union(int rootp, int rootq, vector &vec_pair)
{
vec_pair[rootp] = rootq;
return true;
}
このバージョンでは、最悪の場合、1-2,2-3,3-4と入力します.などの場合、接続されたツリーは1本、検索回数
(1+2+3+…N)/N=(N-1)/2、すなわちM対所要時間はMN/2
修正:ノード数の少ない木をサブツリーとする.
配列レコードサブツリーのノード数を追加すればいいです.
バージョン3加重高速並列:
vector vec_pair(N),sz(N);
for (int i = 0; i < N; i++)
{
vec_pair[i] = i;
sz[i] = 1;
}
bool slow_search(int p, int q, vector &vec_pair,int &rootp,int &rootq)
{
//vector::size_type rootp, rootq;
for (rootp = p; rootp != vec_pair[rootp]; rootp = vec_pair[rootp]);
for (rootq = q; rootq != vec_pair[rootq]; rootq = vec_pair[rootq]);
return rootp == rootq;
}
bool quik_union(int rootp, int rootq, vector &vec_pair)
{
vec_pair[rootp] = rootq;
return true;
}
このバージョンの最悪の検索ごとにバージョン4:圧縮パス
各ノードがルートノードを直接指すことができる場合は、検索時にパス圧縮を使用して、サブノードが親ノードの親ノードを指すようにする方法がより便利です.検索回数が増えるにつれて、木は徐々に平らになります.
変更
bool slow_search(int p, int q, vector &vec_pair,int &rootp,int &rootq)
{
//vector::size_type rootp, rootq;
for (rootp = p; rootp != vec_pair[rootp]; rootp = vec_pair[rootp])
    vec_pair[rootp]=vec_pair[vec_pair[rootp]];
for (rootq = q; rootq != vec_pair[rootq]; rootq = vec_pair[rootq])
    vec_pair[rootq]=vec_pair[vec_pair[rootq]];
return rootp == rootq;
}
まとめ:
高速検索、高速パラレルセットはlarge Nに適していません.重み付け方法が良いです.
圧縮経路法はsearch時に多くの操作があったため,重み付け法が具体的に分析する価値があるかどうかを修正する.