CodeIQ/サルベジオン問題 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• CodeIQ/サルベジオン問題 へ行く。

*サルベジオン問題 [#va16a2c3]
-CodeIQで結城浩先生が出題されていた、サルベジオン問題に挑戦しましたので、自分なりの解説を書いてみた
-なお、問題の詳細は[[こちら>https://codeiq.jp/ace/yuki_hiroshi/q1215]]&note{codeiq-spacetalky:[[挑戦者求む！【アルゴリズム】サルベジオン社で宇宙船のデータを救え by The Essence of Programming 結城 浩│CodeIQ>https://codeiq.jp/ace/yuki_hiroshi/q1215]], 2014-11-27公開, 2014-11-27閲覧};
-結城先生の[[CodeIQのページはこちら>http://www.hyuki.com/codeiq/]]&note{codeiq-hyuki:[[CodeIQの問題に挑戦しよう！>http://www.hyuki.com/codeiq/]], 2014-11-30閲覧};

*多倍長整数演算の実装 [#jf6c05b5]
-今回の問題は恐ろしく大きな数字を扱う
-intやshortは、それぞれ4byte、2byteのサイズを持つ
-long long などを使うと8byteサポートできるが、それでも8byte = 64bit = &mimetex(2^{64}-1); が最大数となる。
-しかし、今回、WebAPIを覗いてみると、恐ろしい数字が書かれている。
 1 0 K19584500653053662232211568267 V830542486163201924733591581247 1267650600228229401496703205376
-前述の文字列は、1番目のdbのインデクス 0番をqueryした時の返り値。
-説明に書かれているが、順番にdbの番号、インデクス、キー、バリュー、''最大のインデクス+1''が書かれている。
-最大インデクスがとても大きい数字である。
 1267650600228229401496703205376
-この数字は桁数で数えると、31桁。
#mimetex(30 \lt \log_{10}(1267650600228229401496703205376)\approx 30.1029995.. \lt 31)
-そして、2進数で表すと、101桁に達する。
#mimetex(\log_{2}(1267650600228229401496703205376)= 100)
-今気づいたんだが、この数字はちょうど&mimetex(2^{100});なんだな。
-この数字は通常のCやC++で使えるバイト数を超えている
-なので、自前で巨大な数字を扱うクラスを定義する。

*largeNumberクラスの定義 [#g647356d]
-というわけで、自前の巨大な数字を扱うクラス、largeNumberを定義します。
-いっつも思うんですが、クラス名をつけるセンスは鍛えたいです。
#geshi(c++,number=on,start=4){{
class largeNumber{
public:
	// constructor
	largeNumber(void);
	// constructor
	largeNumber(const std::string& a);
	// deconstructor
	~largeNumber(void);

	// wrapper of std::string
	char operator[](unsigned int i) const {
		return rawString[i];
	}
	unsigned int length() const {
		return (unsigned int)rawString.length();
	}

	// align the string
	void alignDigits(std::string& leftString, std::string& rightString) const;
	// subtraction operation
	const largeNumber operator -(const class largeNumber& right) const;
	// add operation
	const largeNumber operator +(const class largeNumber& right) const;
	// divide operation
	largeNumber& divide2();
	// add operation
	largeNumber& operator +=(const largeNumber& right){
		*this = *this + right;
		return *this;
	}
	// substitution
	largeNumber& operator =(const largeNumber& a){
		rawString = a.rawString;
		return *this;
	}
	// comparison operator
	bool operator != (const largeNumber& right) const {
		return !(*this == right);
	}
	// comparison operator
	bool operator == (const largeNumber& right) const {
		return rawString == right.rawString;
	}
	// comparison operator
	bool operator < (const largeNumber& a) const;

	std::string getString() const {
		return rawString;
	}

private:
	// container of the actual index/key/value
	std::string rawString;
};
}}
-largeNumberを実装するために、内部的にはstd::stringを使います。
--要は文字列として保持しておくわけです
--rawString変数がそれにあたります
-そして、一桁ずつ、数字に戻した上で四則演算や比較を行い、一桁ずつ結果を書き戻します。
-今回はおそらく必要にならないだろうとたかを括って、四則演算のうち、足し算(operator +)と、「÷２」(divide2)だけ実装しました。
-んで、db2では、引き算を実装しました。(ただし結果が負になる引き算は未実装)
-あと、絶対必要になるであろう比較演算子
**工夫点 [#ifc09329]
-文字列は配列になっています
--文字列は左から格納されているので 12345 は順番に 1→2→3→4→5 と格納されています
--一方で、足し算なんかは、小さい桁から始めます。つまり、
--5→4→3→2→1 の順に必要になります
#ref(storeAndCompute.png)
-なので、12345 + 6789 なんかを計算する場合は、文字列のindexと、実際の桁がマッチしないため、処理が煩雑になります。
-なので、足し算でも比較でも、alignDigits という内部関数を実装(22行目あたり)して、それを使います
--こいつは内部で2つのlargeNumberを比較します。
--桁数が等しくなければ、短い文字列の左側に0を追加して同じ桁数に揃えます。
--また、桁あふれに備えて、最低でも1桁、0が一番左にあるようにします
#ref(alignDigits.png)
-これで、足し算する場合に、桁数の違いを心配する場合をすべてここで解決しました。
*db1番からKEYを見つけ出す [#q953ce7f]
-db1番は割りと簡単でした。
**まずは中を覗いてみる [#q6f22307]
-db 内部を適当に先頭100個ぐらい覗いてみると、どうもKeyが昇順に並んでいるように見えます。
-ただし、インデクスが&mimetex(12 \times 10^{30});ぐらいあって、順番に探してると大変なことになります。
--参考までに、結城先生は「WebAPIを1秒以上間隔を空けて」アクセスしてほしいとお願いされています
--なので、最悪な場合、&mimetex(12 \times 10^{30});秒だけかかる事になります。
--軽く数億年ぐらい必要になる計算です。
-なので、もっと短い回数のアクセスで目的のキーを見つける必要があります。
**考えてみる [#u3d29b81]
-最大のインデクス数がわかってるし、各インデクスには、ランダムアクセスが可能なので、二分探索を実装することにしました。
-まずは0番をクエリして最大数を求め、そこから探索範囲を半分に減らしながら、探索領域を絞り込んでいきます
**実装 [#t5e65b74]
-以下のように実装しました
#geshi(c++,number=on,start=109){{
// query for db1
std::cout << "target:" << targetKey << std::endl;
std::cout << "key   :" << key << std::endl;
std::cout << "upper :" << upperBoardIndex << std::endl;
std::cout << "index :" << nextIndex << std::endl;
std::cout << "lower :" << lowerBoardIndex << std::endl;
nextIndex = lowerBoardIndex + upperBoardIndex;
nextIndex.divide2();
queryIndex(numberOfDatabase, nextIndex, key, value);
std::cout << "target:" << targetKey << std::endl;
std::cout << "key   :" << key << std::endl;
std::cout << "upper :" << upperBoardIndex << std::endl;
std::cout << "index :" << nextIndex << std::endl;
std::cout << "lower :" << lowerBoardIndex << std::endl;
while(key != targetKey){
	trialCount++;
	if(key < targetKey){
		lowerBoardIndex = lowerBoardIndex + upperBoardIndex;
		lowerBoardIndex.divide2();
	}else{
		upperBoardIndex = lowerBoardIndex + upperBoardIndex;
		upperBoardIndex.divide2();
	}
	nextIndex = lowerBoardIndex + upperBoardIndex;
	nextIndex.divide2();
	queryIndex(numberOfDatabase, nextIndex, key, value);
	std::cout << "target:" << targetKey << std::endl;
	std::cout << "key   :" << key << std::endl;
	std::cout << "upper :" << upperBoardIndex << std::endl;
	std::cout << "index :" << nextIndex << std::endl;
	std::cout << "lower :" << lowerBoardIndex << std::endl;

}
}}
-全体のコードは git に公開予定
-大量のstd::coutはdebug用なので、突き詰めれば下記がメインのコード
#geshi(c++){{
// query for db1
nextIndex = lowerBoardIndex + upperBoardIndex;
nextIndex.divide2();
queryIndex(numberOfDatabase, nextIndex, key, value);
while(key != targetKey){
	trialCount++;
	if(key < targetKey){
		lowerBoardIndex = lowerBoardIndex + upperBoardIndex;
		lowerBoardIndex.divide2();
	}else{
		upperBoardIndex = lowerBoardIndex + upperBoardIndex;
		upperBoardIndex.divide2();
	}
	nextIndex = lowerBoardIndex + upperBoardIndex;
	nextIndex.divide2();
	queryIndex(numberOfDatabase, nextIndex, key, value);
}
}}
-基本的な挙動は以下の通り
--lowerBoardIndexとupperBoardIndexにより、探索範囲を設定する
--基本的に探索範囲の真ん中のインデクスを計算し、そのキーを抽出します(queryIndex)
---抽出したキーが目的のキーより大きい場合は、抽出したキーを下限(lowerBoardIndex)として探索範囲を再設定します
---抽出したキーが目的のキーより小さい場合は、抽出したキーを上限(upperBoardIndex)として探索範囲を再設定します
---教科書どおりの二分探索です
-largeNumberで「÷２」だけ実装したのはこのためです。
-なお、今回の問題は探索範囲が&mimetex(2^{100});であり、キーを見つけるまで、必ず探索領域をちょうど二分割できる状態でしたので、実装が雑でもちゃんと見つけることが出来ました
-探索領域はupperBoardIndexとlowerBoardIndexで定義していたのですが、おそらくlowerBoardIndexとupperBoardIndexが隣合う状況になると、どちらの値も更新されず、無限ループに陥る危険な実装です。
-まぁ正答に急いだからなので、良しとする。
-実際、&mimetex(2^{100});のインデックスだけあって、101回のクエリで目的のキーとその値を見つけることが出来ました。やった！
-以下、gnuplotで探索範囲と、試行回数を対数軸でplotした図。
-本当は、100回探索するのだが、途中から探索範囲が小さくなりすぎて、gnuplotの分解能が足りなくなってしまっている。ショボーン。
#ref(db1-result.png)
*db2番からKEYを見つけ出す [#h1b8119d]
-さて、実はdb2番があるのをすっかり忘れていました。
**まずは中を覗いてみる [#zee56ece]
-中身を覗いてみて顔面蒼白。なんとキーは単調増加でない！
-とりあえず中身を50個ぐらいdumpしてみて、100回ぐらい見返してみました。
-参考までに先頭50個のキー↓
 0
 633825300114114700748351602688
 316912650057057350374175801344
 950737950171172051122527404032
 158456325028528675187087900672
 475368975085586025561263702016
 792281625142643375935439503360
 1109194275199700726309615304704
 79228162514264337593543950336
 237684487542793012780631851008
 396140812571321687967719751680
 554597137599850363154807652352
 713053462628379038341895553024
 871509787656907713528983453696
 1029966112685436388716071354368
 1188422437713965063903159255040
 39614081257132168796771975168
 118842243771396506390315925504
 198070406285660843983859875840
 277298568799925181577403826176
 356526731314189519170947776512
 435754893828453856764491726848
 514983056342718194358035677184
 594211218856982531951579627520
 673439381371246869545123577856
 752667543885511207138667528192
 831895706399775544732211478528
 911123868914039882325755428864
 990352031428304219919299379200
 1069580193942568557512843329536
 1148808356456832895106387279872
 1228036518971097232699931230208
 19807040628566084398385987584
 59421121885698253195157962752
 99035203142830421991929937920
 138649284399962590788701913088
 178263365657094759585473888256
 217877446914226928382245863424
 257491528171359097179017838592
 297105609428491265975789813760
 336719690685623434772561788928
 376333771942755603569333764096
 415947853199887772366105739264
 455561934457019941162877714432
 495176015714152109959649689600
 534790096971284278756421664768
 574404178228416447553193639936
 614018259485548616349965615104
 653632340742680785146737590272
**考えてみる [#v18468f9]
-よーく眺めてみると、増えたり減ったりしているので、何か法則性があるのかも知れない
-よーく眺めていたら、3番目のキーが1番目のキーと2番目のキーの和であることに気が付きました。
 0
 633825300114114700748351602688 // 1番目のキー
 316912650057057350374175801344 // 2番目のキー
 950737950171172051122527404032 // 3番目のキー
-しかし、そうやって単純に足し算で表せるのはどうもここだけの様で、よくわからないので、ミルカさんに倣って、差分を表示してみることにしました
-ここでlargeNumberに引き算機能を実装することに
-そして、試しに各キーの数値の差分を表示してみた。
 0
 633825300114114700748351602688   633825300114114700748351602688
 316912650057057350374175801344   0
 950737950171172051122527404032   633825300114114700748351602688
 158456325028528675187087900672   0
 475368975085586025561263702016   316912650057057350374175801344
 792281625142643375935439503360   316912650057057350374175801344
 1109194275199700726309615304704  316912650057057350374175801344
 79228162514264337593543950336    0
 237684487542793012780631851008   158456325028528675187087900672
 396140812571321687967719751680   158456325028528675187087900672
 554597137599850363154807652352   158456325028528675187087900672
 713053462628379038341895553024   158456325028528675187087900672
 871509787656907713528983453696   158456325028528675187087900672
 1029966112685436388716071354368  158456325028528675187087900672
 1188422437713965063903159255040  158456325028528675187087900672
 39614081257132168796771975168    0
 118842243771396506390315925504   79228162514264337593543950336
 198070406285660843983859875840   79228162514264337593543950336
 277298568799925181577403826176   79228162514264337593543950336
 356526731314189519170947776512   79228162514264337593543950336
 435754893828453856764491726848   79228162514264337593543950336
 514983056342718194358035677184   79228162514264337593543950336
 594211218856982531951579627520   79228162514264337593543950336
 673439381371246869545123577856   79228162514264337593543950336
 752667543885511207138667528192   79228162514264337593543950336
 831895706399775544732211478528   79228162514264337593543950336
 911123868914039882325755428864   79228162514264337593543950336
 990352031428304219919299379200   79228162514264337593543950336
 1069580193942568557512843329536  79228162514264337593543950336
 1148808356456832895106387279872  79228162514264337593543950336
 1228036518971097232699931230208  79228162514264337593543950336
 19807040628566084398385987584    0
 59421121885698253195157962752    39614081257132168796771975168
 99035203142830421991929937920    39614081257132168796771975168
 138649284399962590788701913088   39614081257132168796771975168
 178263365657094759585473888256   39614081257132168796771975168
 217877446914226928382245863424   39614081257132168796771975168
 257491528171359097179017838592   39614081257132168796771975168
 297105609428491265975789813760   39614081257132168796771975168
 336719690685623434772561788928   39614081257132168796771975168
 376333771942755603569333764096   39614081257132168796771975168
 415947853199887772366105739264   39614081257132168796771975168
 455561934457019941162877714432   39614081257132168796771975168
 495176015714152109959649689600   39614081257132168796771975168
 534790096971284278756421664768   39614081257132168796771975168
 574404178228416447553193639936   39614081257132168796771975168
 614018259485548616349965615104   39614081257132168796771975168
 653632340742680785146737590272   39614081257132168796771975168
-左側がキー、右側が前のキーとの差分。
-キーが減少するときは差分が負の数になってしまい、未実装なので、計算結果は0と表示されている
-この瞬間キター！！！となってアドレナリンが脳内にドバーッとでる感じでした。
**ちょっとだけ解説 [#z03f66ec]
-この数値を同様にgnuplotでプロットすると以下の感じになります
#ref(db2-key-simple.png)
-何らか、強い法則性が見えますね。
-これは、完全二分木として整列されているデータと言えます
-ヒープソートに近いですが、ヒープとは違います。
--ヒープソートでは、先頭のデータは最大値ですが、
--このデータでは、先頭は最大のキーの半分の数が格納されています
-ここから目的のキーを探し出すためには、目的のキーと比較を行い、等しくない場合は、更に奥のデータと比較を行います
-もう少し分かり易く図示しましょう
#ref(tree.png)
-これは、1-31までの数字を二分木にしてあります
--根(root)には、16があります
--例えば、ここから5を見つけたい場合は、
---まず16と比較します。5<16なので、16の左の子ノード、8に移ります
---今度は8と比較します。5<8なので、8の左の子ノード、4に移ります
---今度は4と比較します。4<5なので、4の右の子ノード、6に移ります
---今度は6と比較します。5<6なので、6の左の子ノード、5に移ります
---今度は5と比較します。5==5なので、目的のキーを見つけることが出来ました。
--この様に二分木の、適切な子ノードを選ぶことで、db1と同様、二分探索が可能です。
#ref(treeSearch.png)
-問題は、「左の子ノード、右の子ノード」をどうやってインデクスから決定するか、です。
-これはヒープソートが良い例になります
-ヒープソートでは、配列で木構造(ヒープ)を表現します
--現在のインデクスを &mimetex(i); とすると
--左の子ノードは &mimetex(i_{left} = 2i);で表現されます
--右の子ノードは &mimetex(i_{right} = 2i+1);で表現されます
--ただし、そのためには、0番目のインデクスは使わずに、1番からデータを詰めないといけない、という制約があります。
-今回、db2番は0番のインデクスがちょうど0のキーを格納しているので、まさにヒープソートと同じ方法でインデクスが決定できるわけです。
-前述の、gnuplotも、同様にツリー構造を描画すると下図の様になります
#ref(db2-key-tree.png)
-ツリー構造っぽいのが理解し易いかと思います
**実装 [#v3fb74b9]
-既に二分木は完成しているので、適切なキーを取得するまでインデクスを調整しながらクエリを繰り返します。
#geshi(c++,number=on,start=144){{
// query for db2
std::cout << "index :" << index << "\tkey :" << key << '\t' << targetKey << std::endl;
while(key != targetKey){
	trialCount++;
	if(key < targetKey){
		index = GET_RIGHT_INDEX(index);
	}else{
		index = GET_LEFT_INDEX(index);
	}
	queryIndex(numberOfDatabase, index, key, value);
	std::cout << "index :" << index << "\tkey :" << key << '\t' << targetKey << std::endl;
}
break;
}}
-153行目の queryIndex が実際にWebAPIにアクセスしているところです
-ここで得られたkeyがtargetKeyと等しいか、チェックします
--ここには書いてませんが、このループに入る前に、1度WebAPIにアクセスして最初のクエリはしています
-keyとtargetKeyの大小関係に応じて、GET_LEFT_INDEXかGET_RIGHT_INDEXを実行します
-これらは関数ではなく、defineで定義していて
#geshi(c++,number=on,start=14){{
#define GET_LEFT_INDEX(x)  (x + x)
#define GET_RIGHT_INDEX(x) (x + x + largeNumber("1"))
}}
-という具合にインデクスを決定しています
--掛け算が実装されてないので、足し算をするのがミソ。
--また、インデクス自体がクラスなので、''+1'' でなく、''+largeNumber("1")''なのがミソ。
*感想 [#o3769a4c]
-面白かった！
-内部の挙動を推測して、それに応じてコードを書くのは楽しい
-その挙動の推測に曲がった引っ掛けを使わないあたりに、結城先生の人柄を感じる。