CodeIQ/クロッシング問題 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• CodeIQ/クロッシング問題 へ行く。

このページでは[[CodeIQ>https://codeiq.jp/]]&note{codeiq-official:[[CodeIQ｜ITエンジニアのための実務スキル評価サービス>https://codeiq.jp/]]};で結城浩先生から出題されたクロッシング問題について解説しています。

-クロッシング問題の詳細は[[こちら>https://codeiq.jp/ace/yuki_hiroshi/q432]]
-結城浩先生のCodeIQのページは[[こちら>http://www.hyuki.com/codeiq/]]&note{codeiq-hyuki-official:[[CodeIQの問題に挑戦しよう！>http://www.hyuki.com/codeiq/]]};

*はじめに [#jfa69311]
-今回、締め切りの時間をすっかり忘れていて、結城先生には最低限の回答だけを提出して終わってしまったことをお詫びします。
-提出しようと思った解説文、感想を、ココに記して公開します。

*問題を読んで [#k1d08f04]
-今回の実行時間を測定する問題は、必ずオーダ計算の問題に突き当たるだろうと予想していました。
-クロッシング問題は、今までの様に問題を解くだけでなく、実際に実行時間を測定することも、かなり実世界よりな問題になったと思います。

*解法 [#p1e0615f]
-交点の数は、光線の本数が少ない状態から順番に推定していきました。
--光線が2本しか無い時は、交わるか交わらないかの2種類だけです。
--光線が3本ある時は、交点は最大3点になります。これは&mimetex(_3C_2);で求まります。
--光線が3本あって、交点の数が最大になる場合は、既に2本の光線が交わった上で、その両方と3本目の光線が交わる状態です。
--今回の問題では光線は発射される時点で左から順番に数字が大きなっていきますから、一番大きい数の光線は一番右側から発されます。
--この光線が一番左側に到着するときに、全ての光線と交わり、交点の数が最大になります。
-さて、今回の問題は最大ではなく、交点がいくつか数える問題です。
-そのために、最大からいくつ足りないか、を数え上げることにしました。

*数え上げの理論 [#t6455e5e]
-光線が、ある数nを持ってるとして、こいつが交わる可能性がある光線は、
--自分より左側に到達する、nより大きい数を持つ光線
--自分より右側に到達する、nより小さい数を持つ光線
-の２種類に分けることができます。
-ここで気をつけないと行けないのはダブりでカウントしてしまう事態です。
--直線AとBが交わって交点ができるとして、　交点は1つなのに、直線Aで1点、直線Bでもう1点と、計2点としてカウントしてしまうと、重複してカウントしてしまいます。
-今回はそれを避けるために、到達した光線の内、左側から順番にカウントしていくことにしました。
-感覚としては、1本1本、光線をほどいていくイメージです（もしくは皮を剥いでいくイメージなのですが、光線が1次元なので、ほどいていくと表現しました）
-到達した光線のうち左側から1本ずつ光線をほどいていくと、どんどん交点の数は減っていきます。
-つまり、重複をカウントしてしまうことがありません。

**実際の手続き [#sf595f35]
-さて、交点の数を数えるためには、左側から順番に
--自身より右側に到達する、自身より小さい数を持つ光線
-の本数を数えれば良いことになります。
-これは数式で書けば以下のようになります。
--交わるかどうかを判定する関数を以下のように定義します
#mimetex(f\left(i, j\right) = \begin{array}\left{1:P_i > P_j\\0: else\right}\end{array})
-なお、&mimetex(P);は数列を表し、ここでは到着した光線の番号の集合です。
-''自身より右側に到達する、自身より小さい数を持つ光線の本数''は、&mimetex(f(i,j));を使って、
#mimetex(S(i) = \sum_{j=i+1}^N f(i, j))
-と表せます。
-i番目の光線より右側に到達する光線の本数がS(i)で表されるわけです。
-今回の問題では、この総和を求めますので、S(i)の総和を求めれば良いことになります。
#mimetex(\sum_{i=1}^N S(i) = \sum_{i=1}^N \sum_{j=i+1}^N f(i, j))
-これだけで求めることができます。

*数学的な議論から実行時間の話へ。 [#iee56623]
-薄々、オーダ量の問題だろうと思いながら、ここまでコーディングしました。
-いざcrossing.txtの処理にかかると、これが応答がなかなか返ってこない
-デバッグをしてみると、計算量が膨大なのが原因で、iの添字が1秒間に数百〜千程度しか増えていません。
-問題文は約30万の光線がありますので、数千秒のオーダがかかります。（1時間程度）
-オーダ量の観点から行けば当然の帰結で、二重に総和を求めているので、計算量のオーダはn^2だけかかります。
-これを削減する必要があります。

*数え上げから2分木の構築へ [#d201aeb5]
-計算量が&mimetex(n^2);になってしまっているのは、二重ループがあるせいです。
-この二重ループはかなり無駄です。
-ある数nがあったとして、これより右側に存在する、nより小さい数を探すわけで、毎回30万件を探し当てるのはかなりバカバカしいです。
-今回の問題はもうひとつ特徴がありました。
--それは光線の番号が必ず1つずつ増え、光線の数と、光線が持つ最大の数が必ず一致する、ということです。
--つまりある数nより、小さい数を持つ光線は必ずn-1本存在することが問題で保証されています。
-自身より小さい数を持つ光線は、自身の左側か右側のどちらかにしか到達しません。
-左側に到達した光線の数は、走査する過程でアクセスしますので、アクセスした数をもとに、2分木を作成しました
-2分木を使うことで、自身より小さい数が、2分木内に幾つ含まれているかをカウントしました。

*子の要素数を持つ2分木 [#oaab1478]
-ある要素が、いくつ子を持っているか2分木では通常数え上げる必要があります。
-しかし、今回は計算時間をさらに短縮するため、2分木にデータを挿入する際に、親ノードへ通知する仕組みを作りました。
-ある要素が追加された時、追加された要素は自身の親、先祖の要素全てで、カウンタを1つずつ足していきます。
-今回のソースコードで言えば88行目−93行目のwhileループ内がそれです。
-一つずつ自身の親を手繰りながら、カウンタを1つずつ足していきます。
-これをすることで、全ての要素は、自身を含めて自身以下にいくつ子要素が存在するか、常に把握してることになります。
-一方で、今まで現れた数より小さい数の個数を調べるためには、二分木から、一番近い数を探し、その際のノードの要素を数え上げることで実現されます。
-2分木での探索は&mimetex(O(\log n));で表わされるので、全体の計算量は&mimetex(O(n \log n));となり、&mimetex(O(n^2));より小さくなります。

*実行時間に付いて [#t6bbc741]
-今回はWindows.hにあるclock()という関数を使いました。
-この関数の分解能は1E-3秒(1ms)であり、それによればcrossing.txt は 400ms 程度で計算が完了しました。
-うち、読み込みに260ms、処理に140ms 程度でした。

*計算時間の検討 [#b02362eb]
-本当に&mimetex(O(n^2));で計算時間が増えるのか、nの値を変えて乱数を発生させながら、実際プロットしてみたのが、以下の図
#ref(crossingComputationCost.png)
-両対数軸になってるのがミソ
-参考までに緑色で&mimetex(n\log n);を重ねて描いてみたが、増え方が線型探索と段違いなのが一目瞭然である。

*ソースコード [#o8bf9948]
-偉そうに解説を書いておきながら、unsigned int だとオーバーフローすることに気づいておらず、必要だったのは、unsigned long long int。
-結果残念賞。
-悔やんでも悔やみきれぬ。
-次回でリベンジ！
#geshi(c++,number){{
#include <iostream>
#include <vector>
#include <fstream>
#include <time.h>
#include <Windows.h>
#include <algorithm>
#include <cstdlib>

//下記defineを有効にすると、結果をミリ秒から秒単位に丸め（切り捨て）て表示する
#define OUTPUT_TIME_IN_ROUNDED_SECOND
//下記defineを有効にすると、線型探索でも同じ配列をカウントし、数が合っているか、出力する
//#define VERIFY_ALGORITHM

const int DEFAULT_NUMBER_OF_DATA	= 1000;

int main(int argc, char **argv);
int readData(std::vector<int>& arrivedLightNumbers);

// 2分木の要素
// キーの他に、
// ・自身より小さい数を持つ子のインデックス
// ・自身より大きい数を持つ子のインデックス
// ・自身の親のインデックス
// ・自身以下の子の要素の総数 (自身含む)
// を変数として持つ
struct _binaryTreeElement{
public:
	_binaryTreeElement(int key):
		m_key(key),
		m_left(-1), 
		m_right(-1), 
		m_parent(-1), 
		m_count(1){
		}
	_binaryTreeElement(int key, int parent):
		m_key(key),
		m_left(-1), 
		m_right(-1), 
		m_parent(parent), 
		m_count(1){
		}
	// キー
	int m_key;
	// 左の子のポインタ(自身より小さい数を持つ)
	int m_left;
	// 右の子のポインタ(自身より大きい数を持つ)
	int m_right;
	// 親のポインタ
	int m_parent;
	// 自身以下の子の要素の総数 (自身を含む)
	int m_count;
};

typedef struct _binaryTreeElement binaryTreeElement;

// 2分木のクラス
class CBinaryTree
{
public:
	CBinaryTree() {};

	// 要素を追加する
	void insert( int key ){
		if(m_binaryTree.size() == 0){
			// 最初の要素
			m_binaryTree.push_back(binaryTreeElement(key));
		}else{
			// 同じ要素を探す
			int index = searchIndex( key );
			if(m_binaryTree[index].m_key == key){
				// 同じ要素が見つかった場合
				// 今回の出題では見つからないはずなので、
				// exitして通知する
				std::cerr << "Duplicate key found in CBinaryTree class" << std::endl;
				std::cerr << "key :" << key << std::endl;
				exit( -1);
			}else if(key < m_binaryTree[index].m_key){
				// 追加しようとしているキーが現在のキーより小さい場合
				m_binaryTree.push_back(binaryTreeElement(key, index));
				m_binaryTree[index].m_left	= m_binaryTree.size() - 1;
				index	= m_binaryTree[index].m_left;
			}else{
				// 追加しようとしているキーが現在のキーより大きい場合
				m_binaryTree.push_back(binaryTreeElement(key, index));
				m_binaryTree[index].m_right	= m_binaryTree.size() - 1;
				index	= m_binaryTree[index].m_right;
			}
			while(index != 0){
				// カウンタを増やしながら親を順に手繰る
				index	= m_binaryTree[index].m_parent;
				m_binaryTree[index].m_count++;
			}
		}
	};

	// 指定されたキーが2分木内に存在するか否かを返す
	bool doesInclude( int key ) const {
		int index	= searchIndex(key);
		if(index == -1){
			return false;
		}
		if(0 <= index && index < (int)m_binaryTree.size() && 
			(m_binaryTree[index].m_key == key)){
			return true;
		}else{
			return false;
		}
	}

	// 指定されたキーより、小さいキーを持つノードの数を数える
	int countSmallerThan( int key ) const {
		int index	= 0;
		int count	= 0;
		if(m_binaryTree.empty() == true){
			// 空っぽなら必ず0
			return 0;
		}
		while(1){
			if(key == m_binaryTree[index].m_key){
				if(m_binaryTree[index].m_left != -1){
					count	+= m_binaryTree[m_binaryTree[index].m_left].m_count;
				}
				return count;
			}else if(key < m_binaryTree[index].m_key){
				if(m_binaryTree[index].m_left == -1){
					return count;
				}else{
					index	= m_binaryTree[index].m_left;
				}
			}else{
				if(m_binaryTree[index].m_left != -1){
					count	+= m_binaryTree[m_binaryTree[index].m_left].m_count;
				}
				count++;
				if(m_binaryTree[index].m_right == -1){
					return count;
				}else{
					index	= m_binaryTree[index].m_right;
				}
			}
		}
	};

	// 2分木に存在するノードの数を数える
	unsigned int getNodeCount() const {
		return (unsigned int)m_binaryTree[0].m_count;
	}


private:
	// 指定したキーを持つノードを探す
	// 返された値は、実体を持つ vector 内での位置を表す
	int searchIndex( int key ) const {
		int index = 0;
		if(m_binaryTree.size() == 0){
			// 要素が1つも無い場合
			return -1;
		}
		while(1){
			if(key == m_binaryTree[index].m_key){
				return index;
			}else if(key < m_binaryTree[index].m_key){
				if(m_binaryTree[index].m_left == -1){
					return index;
				}else{
					index	= m_binaryTree[index].m_left;
				}
			}else{
				if(m_binaryTree[index].m_right == -1){
					return index;
				}else{
					index	= m_binaryTree[index].m_right;
				}
			}
		}
	};

	// 2分木の実体、vector
	std::vector<binaryTreeElement> m_binaryTree;
};

#ifdef VERIFY_ALGORITHM
class Random
{
public:
	// コンストラクタ
	Random()
	{
		srand( static_cast<unsigned int>( time(NULL) ) );
	}

	// 関数オブジェクト
	unsigned int operator()(unsigned int max)
	{
		double tmp = static_cast<double>( rand() ) / static_cast<double>( RAND_MAX );
		return static_cast<unsigned int>( tmp * max );
	}
};

// N件の乱数データを生成する
void generateData(int argc, char** argv, std::vector<int>& arrivedLightNumbers){

	int numberOfData;

	if(argc <= 1){
		numberOfData	= DEFAULT_NUMBER_OF_DATA;
	}else{
		numberOfData	= max(atoi(argv[1]), 2);
	}

	for(int i = 0;i < numberOfData;i++){
		arrivedLightNumbers.push_back(i+1);
	}

	Random r;
	random_shuffle( arrivedLightNumbers.begin(), arrivedLightNumbers.end(), r );  // ランダムシャッフル
}
#endif //VERIFY_ALGORITHM

// ファイルからデータを読み込む
int readData(int argc, char** argv, std::vector<int>& arrivedLightNumbers){
	char *dataFileName;
	if(argc <= 1){
		// ファイル名が指定されなかった場合
		std::cerr << "ファイル名が指定されていません" << std::endl;
		std::cerr << argv[0] << " [データファイル名] として使用して下さい" << std::endl;
		return -1;
	}else{
		dataFileName	= argv[1];
	}

	std::fstream input(dataFileName);
	if(input.is_open() == false){
		// オープンに失敗した場合
		std::cerr << "ファイルオープンに失敗" << std::endl;
		std::cerr << dataFileName << std::endl;
		std::cerr << argv[0] << " [データファイル名] として使用して下さい" << std::endl;
		return -2;
	}

	// 読み込んだデータ内で最大の数字
	int maxNumber	= 0;
	int readBuffer;
	while(input >> readBuffer, !input.eof()){
		// vector 内に追加
		arrivedLightNumbers.push_back(readBuffer);
		if(readBuffer > maxNumber){
			maxNumber	= readBuffer;
		}
	}
	if(maxNumber != arrivedLightNumbers.size()){
		// 読み込んだ値の内、最大の数と、読み込んだデータの数が一致しない場合
		// (=データ内容と件数が不整合の場合)
		std::cerr << "最大の番号が" << maxNumber << "で、データの件数が" << arrivedLightNumbers.size() << "件です。" << std::endl;
		std::cerr << "データが壊れています" << std::endl;
		return -3;
	}

	return arrivedLightNumbers.size();
}


int main(int argc, char **argv){

	using namespace std;

	// 到着した光線の番号を保持する
	vector<int> arrivedLightNumbers;
	// 時刻測定用
	clock_t begin, end;
	// 交差点の総数
	// unsigned int totalNumberOfCrossPoint	= 0; // ← unsigned int だと桁不足
	unsigned int totalNumberOfCrossPoint	= 0;
	// 光線の本数
	int maximumNumberOfLight	= 0;
	// ある数より小さい数が現れた回数
	int countOfSmallerNumber	= 0;
	// 処理に必要な2分木クラス
	CBinaryTree binaryTree;

	// 計測開始
	begin	= clock();
#ifdef VERIFY_ALGORITHM
	// 線型探索の場合の結果
	unsigned int totalNumberOfCrossPointInLinear	= 0;
	// 線型探索の場合の所要時間
	clock_t endLinear;
	// 乱数のデータを生成する 
	generateData(argc, argv, arrivedLightNumbers);
#else
	// データをファイルから読み込む
	readData(argc, argv, arrivedLightNumbers);
#endif // VERIFY_ALGORITHM

	for(unsigned int i = 0;i < arrivedLightNumbers.size();i++){
		// 自身より小さい数が既に何回現れたか調べる
		countOfSmallerNumber	= binaryTree.countSmallerThan(arrivedLightNumbers[i]);
		// 1本の光線は「自身の右側に自身より小さい数がいくつ存在するか」で表される
		// 光線の番号は順番に振られているので「自身の数-1-自身より左側に存在する自身より小さい数」が等価である
		totalNumberOfCrossPoint	+= arrivedLightNumbers[i] - 1 - countOfSmallerNumber;
		// 自身の数を、現れた数として2分木に追加
		binaryTree.insert(arrivedLightNumbers[i]);
	}
	// 計測終了
	end	= clock();
#ifdef VERIFY_ALGORITHM
	for(unsigned int i = 0;i < arrivedLightNumbers.size();i++){
		for(unsigned int j = i;j < arrivedLightNumbers.size();j++){
			if(arrivedLightNumbers[j] < arrivedLightNumbers[i]){
				totalNumberOfCrossPointInLinear++;
			}
		}
	}
	endLinear	= clock();
	cout << arrivedLightNumbers.size() << ',' << endLinear - end + 1 << ',' << totalNumberOfCrossPointInLinear << ',' << end - begin + 1 << ',' << totalNumberOfCrossPoint << endl;
#else
#ifdef OUTPUT_TIME_IN_ROUNDED_SECOND
	cout << totalNumberOfCrossPoint << ',' << (int)((double)(end - begin) / 1000) << endl;
#else
	cout << totalNumberOfCrossPoint << ',' << end - begin << endl;
#endif //OUTPUT_TIME_IN_ROUNDED_SECOND
	cout << "ENV: C++" << endl << endl;
#endif //VERIFY_ALGORITHM

}
}}