CodeIQ/サルベジオン問題

サルベジオン問題†

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

多倍長整数演算の実装†

• 今回の問題は恐ろしく大きな数字を扱う
• 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クラスの定義†

• というわけで、自前の巨大な数字を扱うクラス、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では、引き算を実装しました。(ただし結果が負になる引き算は未実装)
• あと、絶対必要になるであろう比較演算子

工夫点†

• 文字列は配列になっています
  • 文字列は左から格納されているので 12345 は順番に 1→2→3→4→5 と格納されています
  • 一方で、足し算なんかは、小さい桁から始めます。つまり、
  • 5→4→3→2→1 の順に必要になります
    
• なので、12345 + 6789 なんかを計算する場合は、文字列のindexと、実際の桁がマッチしないため、処理が煩雑になります。
• なので、足し算でも比較でも、alignDigits という内部関数を実装(22行目あたり)して、それを使います
  • こいつは内部で2つのlargeNumberを比較します。
  • 桁数が等しくなければ、短い文字列の左側に0を追加して同じ桁数に揃えます。
  • また、桁あふれに備えて、最低でも1桁、0が一番左にあるようにします
    
• これで、足し算する場合に、桁数の違いを心配する場合をすべてここで解決しました。

db1番からKEYを見つけ出す†

• db1番は割りと簡単でした。

まずは中を覗いてみる†

• db 内部を適当に先頭100個ぐらい覗いてみると、どうもKeyが昇順に並んでいるように見えます。
• ただし、インデクスが&mimetex(12 \times 10^{30});ぐらいあって、順番に探してると大変なことになります。
  • 参考までに、結城先生は「WebAPIを1秒以上間隔を空けて」アクセスしてほしいとお願いされています
  • なので、最悪な場合、&mimetex(12 \times 10^{30});秒だけかかる事になります。
  • 軽く数億年ぐらい必要になる計算です。
• なので、もっと短い回数のアクセスで目的のキーを見つける必要があります。

考えてみる†

• 最大のインデクス数がわかってるし、各インデクスには、ランダムアクセスが可能なので、二分探索を実装することにしました。
• まずは0番をクエリして最大数を求め、そこから探索範囲を半分に減らしながら、探索領域を絞り込んでいきます

実装†

• 以下のように実装しました

  #geshi(c++,number=on,start=109){{ 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++){{ 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の分解能が足りなくなってしまっている。ショボーン。
  

db2番からKEYを見つけ出す†

• さて、実はdb2番があるのをすっかり忘れていました。

まずは中を覗いてみる†

• 中身を覗いてみて顔面蒼白。なんとキーは単調増加でない！
• とりあえず中身を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

考えてみる†

• よーく眺めてみると、増えたり減ったりしているので、何か法則性があるのかも知れない
• よーく眺めていたら、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と表示されている
• この瞬間キター！！！となってアドレナリンが脳内にドバーッとでる感じでした。

ちょっとだけ解説†

• この数値を同様にgnuplotでプロットすると以下の感じになります
  
• 何らか、強い法則性が見えますね。
• これは、完全二分木として整列されているデータと言えます
• ヒープソートに近いですが、ヒープとは違います。
  • ヒープソートでは、先頭のデータは最大値ですが、
  • このデータでは、先頭は最大のキーの半分の数が格納されています
• ここから目的のキーを探し出すためには、目的のキーと比較を行い、等しくない場合は、更に奥のデータと比較を行います
• もう少し分かり易く図示しましょう
  
• これは、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と同様、二分探索が可能です。
    
• 問題は、「左の子ノード、右の子ノード」をどうやってインデクスから決定するか、です。
• これはヒープソートが良い例になります
• ヒープソートでは、配列で木構造(ヒープ)を表現します
  • 現在のインデクスを &mimetex(i); とすると
  • 左の子ノードは &mimetex(i_{left} = 2i);で表現されます
  • 右の子ノードは &mimetex(i_{right} = 2i+1);で表現されます
  • ただし、そのためには、0番目のインデクスは使わずに、1番からデータを詰めないといけない、という制約があります。
• 今回、db2番は0番のインデクスがちょうど0のキーを格納しているので、まさにヒープソートと同じ方法でインデクスが決定できるわけです。
• 前述の、gnuplotも、同様にツリー構造を描画すると下図の様になります
  
• ツリー構造っぽいのが理解し易いかと思います

実装†

• 既に二分木は完成しているので、適切なキーを取得するまでインデクスを調整しながらクエリを繰り返します。

  #geshi(c++,number=on,start=144){{ 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")なのがミソ。

感想†

• 面白かった！
• 内部の挙動を推測して、それに応じてコードを書くのは楽しい
• その挙動の推測に曲がった引っ掛けを使わないあたりに、結城先生の人柄を感じる。

最新の20件