![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
このページではCodeIQ¬e{codeiq-official:CodeIQ｜ITエンジニアのための実務スキル評価サービス};で結城浩先生から出題されたクロッシング問題について解説しています。
#mimetex(f\left(i, j\right) = \begin{array}\left{1:P_i > P_j\\0: else\right}\end{array})
#mimetex(S(i) = \sum_{j=i+1}^N f(i, j))
#mimetex(\sum_{i=1}^N S(i) = \sum_{i=1}^N \sum_{j=i+1}^N f(i, j))
#geshi(c++,number){{
#include <iostream>
#include <vector>
#include <fstream>
#include <time.h>
#include <Windows.h>
#include <algorithm>
#include <cstdlib>
#define OUTPUT_TIME_IN_ROUNDED_SECOND
const int DEFAULT_NUMBER_OF_DATA = 1000;
int main(int argc, char **argv); int readData(std::vector<int>& arrivedLightNumbers);
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;
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 );
}
};
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
} }}
crossingComputationCost.png