CodeIQ/クロッシング問題
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
このページでは[[CodeIQ>https://codeiq.jp/]]¬e{codeiq-o...
-クロッシング問題の詳細は[[こちら>https://codeiq.jp/ace/y...
-結城浩先生のCodeIQのページは[[こちら>http://www.hyuki.co...
*はじめに [#jfa69311]
-今回、締め切りの時間をすっかり忘れていて、結城先生には最...
-提出しようと思った解説文、感想を、ココに記して公開します。
*問題を読んで [#k1d08f04]
-今回の実行時間を測定する問題は、必ずオーダ計算の問題に突...
-クロッシング問題は、今までの様に問題を解くだけでなく、実...
*解法 [#p1e0615f]
-交点の数は、光線の本数が少ない状態から順番に推定していき...
--光線が2本しか無い時は、交わるか交わらないかの2種類だけ...
--光線が3本ある時は、交点は最大3点になります。これは&mime...
--光線が3本あって、交点の数が最大になる場合は、既に2本の...
--今回の問題では光線は発射される時点で左から順番に数字が...
--この光線が一番左側に到着するときに、全ての光線と交わり...
-さて、今回の問題は最大ではなく、交点がいくつか数える問題...
-そのために、最大からいくつ足りないか、を数え上げることに...
*数え上げの理論 [#t6455e5e]
-光線が、ある数nを持ってるとして、こいつが交わる可能性が...
--自分より左側に到達する、nより大きい数を持つ光線
--自分より右側に到達する、nより小さい数を持つ光線
-の2種類に分けることができます。
-ここで気をつけないと行けないのはダブりでカウントしてしま...
--直線AとBが交わって交点ができるとして、 交点は1つなのに...
-今回はそれを避けるために、到達した光線の内、左側から順番...
-感覚としては、1本1本、光線をほどいていくイメージです(も...
-到達した光線のうち左側から1本ずつ光線をほどいていくと、...
-つまり、重複をカウントしてしまうことがありません。
**実際の手続き [#sf595f35]
-さて、交点の数を数えるためには、左側から順番に
--自身より右側に到達する、自身より小さい数を持つ光線
-の本数を数えれば良いことになります。
-これは数式で書けば以下のようになります。
--交わるかどうかを判定する関数を以下のように定義します
#mimetex(f\left(i, j\right) = \begin{array}\left{1:P_i > ...
-なお、&mimetex(P);は数列を表し、ここでは到着した光線の番...
-''自身より右側に到達する、自身より小さい数を持つ光線の本...
#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 ...
-これだけで求めることができます。
*数学的な議論から実行時間の話へ。 [#iee56623]
-薄々、オーダ量の問題だろうと思いながら、ここまでコーディ...
-いざcrossing.txtの処理にかかると、これが応答がなかなか返...
-デバッグをしてみると、計算量が膨大なのが原因で、iの添字...
-問題文は約30万の光線がありますので、数千秒のオーダがかか...
-オーダ量の観点から行けば当然の帰結で、二重に総和を求めて...
-これを削減する必要があります。
*数え上げから2分木の構築へ [#d201aeb5]
-計算量が&mimetex(n^2);になってしまっているのは、二重ルー...
-この二重ループはかなり無駄です。
-ある数nがあったとして、これより右側に存在する、nより小さ...
-今回の問題はもうひとつ特徴がありました。
--それは光線の番号が必ず1つずつ増え、光線の数と、光線が持...
--つまりある数nより、小さい数を持つ光線は必ずn-1本存在す...
-自身より小さい数を持つ光線は、自身の左側か右側のどちらか...
-左側に到達した光線の数は、走査する過程でアクセスしますの...
-2分木を使うことで、自身より小さい数が、2分木内に幾つ含ま...
*子の要素数を持つ2分木 [#oaab1478]
-ある要素が、いくつ子を持っているか2分木では通常数え上げ...
-しかし、今回は計算時間をさらに短縮するため、2分木にデー...
-ある要素が追加された時、追加された要素は自身の親、先祖の...
-今回のソースコードで言えば88行目−93行目のwhileループ内が...
-一つずつ自身の親を手繰りながら、カウンタを1つずつ足して...
-これをすることで、全ての要素は、自身を含めて自身以下にい...
-一方で、今まで現れた数より小さい数の個数を調べるためには...
-2分木での探索は&mimetex(O(\log n));で表わされるので、全...
*実行時間に付いて [#t6bbc741]
-今回はWindows.hにあるclock()という関数を使いました。
-この関数の分解能は1E-3秒(1ms)であり、それによればcrossin...
-うち、読み込みに260ms、処理に140ms 程度でした。
*計算時間の検討 [#b02362eb]
-本当に&mimetex(O(n^2));で計算時間が増えるのか、nの値を変...
#ref(crossingComputationCost.png)
-両対数軸になってるのがミソ
-参考までに緑色で&mimetex(n\log n);を重ねて描いてみたが、...
*ソースコード [#o8bf9948]
-偉そうに解説を書いておきながら、unsigned 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 clas...
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_...
}
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++;
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_cas...
return static_cast<unsigned int>( tmp * max );
}
};
// N件の乱数データを生成する
void generateData(int argc, char** argv, std::vector<int>...
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(), arrivedLigh...
}
#endif //VERIFY_ALGORITHM
// ファイルからデータを読み込む
int readData(int argc, char** argv, std::vector<int>& arr...
char *dataFileName;
if(argc <= 1){
// ファイル名が指定されなかった場合
std::cerr << "ファイル名が指定されていません" << std::e...
std::cerr << argv[0] << " [データファイル名] として使用...
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] << " [データファイル名] として使用...
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 << "で、データ...
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; // ← unsign...
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(arri...
// 1本の光線は「自身の右側に自身より小さい数がいくつ存...
// 光線の番号は順番に振られているので「自身の数-1-自身...
totalNumberOfCrossPoint += arrivedLightNumbers[i] - 1 -...
// 自身の数を、現れた数として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 -...
#else
#ifdef OUTPUT_TIME_IN_ROUNDED_SECOND
cout << totalNumberOfCrossPoint << ',' << (int)((double)...
#else
cout << totalNumberOfCrossPoint << ',' << end - begin <<...
#endif //OUTPUT_TIME_IN_ROUNDED_SECOND
cout << "ENV: C++" << endl << endl;
#endif //VERIFY_ALGORITHM
}
}}
終了行:
このページでは[[CodeIQ>https://codeiq.jp/]]¬e{codeiq-o...
-クロッシング問題の詳細は[[こちら>https://codeiq.jp/ace/y...
-結城浩先生のCodeIQのページは[[こちら>http://www.hyuki.co...
*はじめに [#jfa69311]
-今回、締め切りの時間をすっかり忘れていて、結城先生には最...
-提出しようと思った解説文、感想を、ココに記して公開します。
*問題を読んで [#k1d08f04]
-今回の実行時間を測定する問題は、必ずオーダ計算の問題に突...
-クロッシング問題は、今までの様に問題を解くだけでなく、実...
*解法 [#p1e0615f]
-交点の数は、光線の本数が少ない状態から順番に推定していき...
--光線が2本しか無い時は、交わるか交わらないかの2種類だけ...
--光線が3本ある時は、交点は最大3点になります。これは&mime...
--光線が3本あって、交点の数が最大になる場合は、既に2本の...
--今回の問題では光線は発射される時点で左から順番に数字が...
--この光線が一番左側に到着するときに、全ての光線と交わり...
-さて、今回の問題は最大ではなく、交点がいくつか数える問題...
-そのために、最大からいくつ足りないか、を数え上げることに...
*数え上げの理論 [#t6455e5e]
-光線が、ある数nを持ってるとして、こいつが交わる可能性が...
--自分より左側に到達する、nより大きい数を持つ光線
--自分より右側に到達する、nより小さい数を持つ光線
-の2種類に分けることができます。
-ここで気をつけないと行けないのはダブりでカウントしてしま...
--直線AとBが交わって交点ができるとして、 交点は1つなのに...
-今回はそれを避けるために、到達した光線の内、左側から順番...
-感覚としては、1本1本、光線をほどいていくイメージです(も...
-到達した光線のうち左側から1本ずつ光線をほどいていくと、...
-つまり、重複をカウントしてしまうことがありません。
**実際の手続き [#sf595f35]
-さて、交点の数を数えるためには、左側から順番に
--自身より右側に到達する、自身より小さい数を持つ光線
-の本数を数えれば良いことになります。
-これは数式で書けば以下のようになります。
--交わるかどうかを判定する関数を以下のように定義します
#mimetex(f\left(i, j\right) = \begin{array}\left{1:P_i > ...
-なお、&mimetex(P);は数列を表し、ここでは到着した光線の番...
-''自身より右側に到達する、自身より小さい数を持つ光線の本...
#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 ...
-これだけで求めることができます。
*数学的な議論から実行時間の話へ。 [#iee56623]
-薄々、オーダ量の問題だろうと思いながら、ここまでコーディ...
-いざcrossing.txtの処理にかかると、これが応答がなかなか返...
-デバッグをしてみると、計算量が膨大なのが原因で、iの添字...
-問題文は約30万の光線がありますので、数千秒のオーダがかか...
-オーダ量の観点から行けば当然の帰結で、二重に総和を求めて...
-これを削減する必要があります。
*数え上げから2分木の構築へ [#d201aeb5]
-計算量が&mimetex(n^2);になってしまっているのは、二重ルー...
-この二重ループはかなり無駄です。
-ある数nがあったとして、これより右側に存在する、nより小さ...
-今回の問題はもうひとつ特徴がありました。
--それは光線の番号が必ず1つずつ増え、光線の数と、光線が持...
--つまりある数nより、小さい数を持つ光線は必ずn-1本存在す...
-自身より小さい数を持つ光線は、自身の左側か右側のどちらか...
-左側に到達した光線の数は、走査する過程でアクセスしますの...
-2分木を使うことで、自身より小さい数が、2分木内に幾つ含ま...
*子の要素数を持つ2分木 [#oaab1478]
-ある要素が、いくつ子を持っているか2分木では通常数え上げ...
-しかし、今回は計算時間をさらに短縮するため、2分木にデー...
-ある要素が追加された時、追加された要素は自身の親、先祖の...
-今回のソースコードで言えば88行目−93行目のwhileループ内が...
-一つずつ自身の親を手繰りながら、カウンタを1つずつ足して...
-これをすることで、全ての要素は、自身を含めて自身以下にい...
-一方で、今まで現れた数より小さい数の個数を調べるためには...
-2分木での探索は&mimetex(O(\log n));で表わされるので、全...
*実行時間に付いて [#t6bbc741]
-今回はWindows.hにあるclock()という関数を使いました。
-この関数の分解能は1E-3秒(1ms)であり、それによればcrossin...
-うち、読み込みに260ms、処理に140ms 程度でした。
*計算時間の検討 [#b02362eb]
-本当に&mimetex(O(n^2));で計算時間が増えるのか、nの値を変...
#ref(crossingComputationCost.png)
-両対数軸になってるのがミソ
-参考までに緑色で&mimetex(n\log n);を重ねて描いてみたが、...
*ソースコード [#o8bf9948]
-偉そうに解説を書いておきながら、unsigned 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 clas...
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_...
}
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++;
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_cas...
return static_cast<unsigned int>( tmp * max );
}
};
// N件の乱数データを生成する
void generateData(int argc, char** argv, std::vector<int>...
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(), arrivedLigh...
}
#endif //VERIFY_ALGORITHM
// ファイルからデータを読み込む
int readData(int argc, char** argv, std::vector<int>& arr...
char *dataFileName;
if(argc <= 1){
// ファイル名が指定されなかった場合
std::cerr << "ファイル名が指定されていません" << std::e...
std::cerr << argv[0] << " [データファイル名] として使用...
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] << " [データファイル名] として使用...
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 << "で、データ...
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; // ← unsign...
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(arri...
// 1本の光線は「自身の右側に自身より小さい数がいくつ存...
// 光線の番号は順番に振られているので「自身の数-1-自身...
totalNumberOfCrossPoint += arrivedLightNumbers[i] - 1 -...
// 自身の数を、現れた数として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 -...
#else
#ifdef OUTPUT_TIME_IN_ROUNDED_SECOND
cout << totalNumberOfCrossPoint << ',' << (int)((double)...
#else
cout << totalNumberOfCrossPoint << ',' << end - begin <<...
#endif //OUTPUT_TIME_IN_ROUNDED_SECOND
cout << "ENV: C++" << endl << endl;
#endif //VERIFY_ALGORITHM
}
}}
ページ名: