*サルベジオン問題 [#va16a2c3]
-CodeIQで結城浩先生が出題されていた、サルベジオン問題に挑戦しましたので、自分なりの解説を書いてみた
-なお、問題の詳細は[[こちら>https://codeiq.jp/ace/yuki_hiroshi/q1215]]¬e{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/]]¬e{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]
-面白かった！
-内部の挙動を推測して、それに応じてコードを書くのは楽しい
-その挙動の推測に曲がった引っ掛けを使わないあたりに、結城先生の人柄を感じる。
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
