CodeIQ/サルベジオン問題
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
*サルベジオン問題 [#va16a2c3]
-CodeIQで結城浩先生が出題されていた、サルベジオン問題に挑...
-なお、問題の詳細は[[こちら>https://codeiq.jp/ace/yuki_hi...
-結城先生の[[CodeIQのページはこちら>http://www.hyuki.com/...
*多倍長整数演算の実装 [#jf6c05b5]
-今回の問題は恐ろしく大きな数字を扱う
-intやshortは、それぞれ4byte、2byteのサイズを持つ
-long long などを使うと8byteサポートできるが、それでも8by...
-しかし、今回、WebAPIを覗いてみると、恐ろしい数字が書かれ...
1 0 K19584500653053662232211568267 V83054248616320192473...
-前述の文字列は、1番目のdbのインデクス 0番をqueryした時の...
-説明に書かれているが、順番にdbの番号、インデクス、キー、...
-最大インデクスがとても大きい数字である。
1267650600228229401496703205376
-この数字は桁数で数えると、31桁。
#mimetex(30 \lt \log_{10}(1267650600228229401496703205376...
-そして、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& r...
// subtraction operation
const largeNumber operator -(const class largeNumber& ri...
// add operation
const largeNumber operator +(const class largeNumber& ri...
// 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変数がそれにあたります
-そして、一桁ずつ、数字に戻した上で四則演算や比較を行い、...
-今回はおそらく必要にならないだろうとたかを括って、四則演...
-んで、db2では、引き算を実装しました。(ただし結果が負にな...
-あと、絶対必要になるであろう比較演算子
**工夫点 [#ifc09329]
-文字列は配列になっています
--文字列は左から格納されているので 12345 は順番に 1→2→3→4...
--一方で、足し算なんかは、小さい桁から始めます。つまり、
--5→4→3→2→1 の順に必要になります
#ref(storeAndCompute.png)
-なので、12345 + 6789 なんかを計算する場合は、文字列のind...
-なので、足し算でも比較でも、alignDigits という内部関数を...
--こいつは内部で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により、探索範囲を設定...
--基本的に探索範囲の真ん中のインデクスを計算し、そのキー...
---抽出したキーが目的のキーより大きい場合は、抽出したキー...
---抽出したキーが目的のキーより小さい場合は、抽出したキー...
---教科書どおりの二分探索です
-largeNumberで「÷2」だけ実装したのはこのためです。
-なお、今回の問題は探索範囲が&mimetex(2^{100});であり、キ...
-探索領域はupperBoardIndexとlowerBoardIndexで定義していた...
-まぁ正答に急いだからなので、良しとする。
-実際、&mimetex(2^{100});のインデックスだけあって、101回...
-以下、gnuplotで探索範囲と、試行回数を対数軸でplotした図。
-本当は、100回探索するのだが、途中から探索範囲が小さくな...
#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 63382530011411470074835...
316912650057057350374175801344 0
950737950171172051122527404032 63382530011411470074835...
158456325028528675187087900672 0
475368975085586025561263702016 31691265005705735037417...
792281625142643375935439503360 31691265005705735037417...
1109194275199700726309615304704 31691265005705735037417...
79228162514264337593543950336 0
237684487542793012780631851008 15845632502852867518708...
396140812571321687967719751680 15845632502852867518708...
554597137599850363154807652352 15845632502852867518708...
713053462628379038341895553024 15845632502852867518708...
871509787656907713528983453696 15845632502852867518708...
1029966112685436388716071354368 15845632502852867518708...
1188422437713965063903159255040 15845632502852867518708...
39614081257132168796771975168 0
118842243771396506390315925504 79228162514264337593543...
198070406285660843983859875840 79228162514264337593543...
277298568799925181577403826176 79228162514264337593543...
356526731314189519170947776512 79228162514264337593543...
435754893828453856764491726848 79228162514264337593543...
514983056342718194358035677184 79228162514264337593543...
594211218856982531951579627520 79228162514264337593543...
673439381371246869545123577856 79228162514264337593543...
752667543885511207138667528192 79228162514264337593543...
831895706399775544732211478528 79228162514264337593543...
911123868914039882325755428864 79228162514264337593543...
990352031428304219919299379200 79228162514264337593543...
1069580193942568557512843329536 79228162514264337593543...
1148808356456832895106387279872 79228162514264337593543...
1228036518971097232699931230208 79228162514264337593543...
19807040628566084398385987584 0
59421121885698253195157962752 39614081257132168796771...
99035203142830421991929937920 39614081257132168796771...
138649284399962590788701913088 39614081257132168796771...
178263365657094759585473888256 39614081257132168796771...
217877446914226928382245863424 39614081257132168796771...
257491528171359097179017838592 39614081257132168796771...
297105609428491265975789813760 39614081257132168796771...
336719690685623434772561788928 39614081257132168796771...
376333771942755603569333764096 39614081257132168796771...
415947853199887772366105739264 39614081257132168796771...
455561934457019941162877714432 39614081257132168796771...
495176015714152109959649689600 39614081257132168796771...
534790096971284278756421664768 39614081257132168796771...
574404178228416447553193639936 39614081257132168796771...
614018259485548616349965615104 39614081257132168796771...
653632340742680785146737590272 39614081257132168796771...
-左側がキー、右側が前のキーとの差分。
-キーが減少するときは差分が負の数になってしまい、未実装な...
-この瞬間キター!!!となってアドレナリンが脳内にドバーッ...
**ちょっとだけ解説 [#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 << '\...
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 << '...
}
break;
}}
-153行目の queryIndex が実際にWebAPIにアクセスしていると...
-ここで得られたkeyがtargetKeyと等しいか、チェックします
--ここには書いてませんが、このループに入る前に、1度WebAPI...
-keyとtargetKeyの大小関係に応じて、GET_LEFT_INDEXかGET_RI...
-これらは関数ではなく、defineで定義していて
#geshi(c++,number=on,start=14){{
#define GET_LEFT_INDEX(x) (x + x)
#define GET_RIGHT_INDEX(x) (x + x + largeNumber("1"))
}}
-という具合にインデクスを決定しています
--掛け算が実装されてないので、足し算をするのがミソ。
--また、インデクス自体がクラスなので、''+1'' でなく、''+l...
*感想 [#o3769a4c]
-面白かった!
-内部の挙動を推測して、それに応じてコードを書くのは楽しい
-その挙動の推測に曲がった引っ掛けを使わないあたりに、結城...
終了行:
*サルベジオン問題 [#va16a2c3]
-CodeIQで結城浩先生が出題されていた、サルベジオン問題に挑...
-なお、問題の詳細は[[こちら>https://codeiq.jp/ace/yuki_hi...
-結城先生の[[CodeIQのページはこちら>http://www.hyuki.com/...
*多倍長整数演算の実装 [#jf6c05b5]
-今回の問題は恐ろしく大きな数字を扱う
-intやshortは、それぞれ4byte、2byteのサイズを持つ
-long long などを使うと8byteサポートできるが、それでも8by...
-しかし、今回、WebAPIを覗いてみると、恐ろしい数字が書かれ...
1 0 K19584500653053662232211568267 V83054248616320192473...
-前述の文字列は、1番目のdbのインデクス 0番をqueryした時の...
-説明に書かれているが、順番にdbの番号、インデクス、キー、...
-最大インデクスがとても大きい数字である。
1267650600228229401496703205376
-この数字は桁数で数えると、31桁。
#mimetex(30 \lt \log_{10}(1267650600228229401496703205376...
-そして、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& r...
// subtraction operation
const largeNumber operator -(const class largeNumber& ri...
// add operation
const largeNumber operator +(const class largeNumber& ri...
// 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変数がそれにあたります
-そして、一桁ずつ、数字に戻した上で四則演算や比較を行い、...
-今回はおそらく必要にならないだろうとたかを括って、四則演...
-んで、db2では、引き算を実装しました。(ただし結果が負にな...
-あと、絶対必要になるであろう比較演算子
**工夫点 [#ifc09329]
-文字列は配列になっています
--文字列は左から格納されているので 12345 は順番に 1→2→3→4...
--一方で、足し算なんかは、小さい桁から始めます。つまり、
--5→4→3→2→1 の順に必要になります
#ref(storeAndCompute.png)
-なので、12345 + 6789 なんかを計算する場合は、文字列のind...
-なので、足し算でも比較でも、alignDigits という内部関数を...
--こいつは内部で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により、探索範囲を設定...
--基本的に探索範囲の真ん中のインデクスを計算し、そのキー...
---抽出したキーが目的のキーより大きい場合は、抽出したキー...
---抽出したキーが目的のキーより小さい場合は、抽出したキー...
---教科書どおりの二分探索です
-largeNumberで「÷2」だけ実装したのはこのためです。
-なお、今回の問題は探索範囲が&mimetex(2^{100});であり、キ...
-探索領域はupperBoardIndexとlowerBoardIndexで定義していた...
-まぁ正答に急いだからなので、良しとする。
-実際、&mimetex(2^{100});のインデックスだけあって、101回...
-以下、gnuplotで探索範囲と、試行回数を対数軸でplotした図。
-本当は、100回探索するのだが、途中から探索範囲が小さくな...
#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 63382530011411470074835...
316912650057057350374175801344 0
950737950171172051122527404032 63382530011411470074835...
158456325028528675187087900672 0
475368975085586025561263702016 31691265005705735037417...
792281625142643375935439503360 31691265005705735037417...
1109194275199700726309615304704 31691265005705735037417...
79228162514264337593543950336 0
237684487542793012780631851008 15845632502852867518708...
396140812571321687967719751680 15845632502852867518708...
554597137599850363154807652352 15845632502852867518708...
713053462628379038341895553024 15845632502852867518708...
871509787656907713528983453696 15845632502852867518708...
1029966112685436388716071354368 15845632502852867518708...
1188422437713965063903159255040 15845632502852867518708...
39614081257132168796771975168 0
118842243771396506390315925504 79228162514264337593543...
198070406285660843983859875840 79228162514264337593543...
277298568799925181577403826176 79228162514264337593543...
356526731314189519170947776512 79228162514264337593543...
435754893828453856764491726848 79228162514264337593543...
514983056342718194358035677184 79228162514264337593543...
594211218856982531951579627520 79228162514264337593543...
673439381371246869545123577856 79228162514264337593543...
752667543885511207138667528192 79228162514264337593543...
831895706399775544732211478528 79228162514264337593543...
911123868914039882325755428864 79228162514264337593543...
990352031428304219919299379200 79228162514264337593543...
1069580193942568557512843329536 79228162514264337593543...
1148808356456832895106387279872 79228162514264337593543...
1228036518971097232699931230208 79228162514264337593543...
19807040628566084398385987584 0
59421121885698253195157962752 39614081257132168796771...
99035203142830421991929937920 39614081257132168796771...
138649284399962590788701913088 39614081257132168796771...
178263365657094759585473888256 39614081257132168796771...
217877446914226928382245863424 39614081257132168796771...
257491528171359097179017838592 39614081257132168796771...
297105609428491265975789813760 39614081257132168796771...
336719690685623434772561788928 39614081257132168796771...
376333771942755603569333764096 39614081257132168796771...
415947853199887772366105739264 39614081257132168796771...
455561934457019941162877714432 39614081257132168796771...
495176015714152109959649689600 39614081257132168796771...
534790096971284278756421664768 39614081257132168796771...
574404178228416447553193639936 39614081257132168796771...
614018259485548616349965615104 39614081257132168796771...
653632340742680785146737590272 39614081257132168796771...
-左側がキー、右側が前のキーとの差分。
-キーが減少するときは差分が負の数になってしまい、未実装な...
-この瞬間キター!!!となってアドレナリンが脳内にドバーッ...
**ちょっとだけ解説 [#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 << '\...
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 << '...
}
break;
}}
-153行目の queryIndex が実際にWebAPIにアクセスしていると...
-ここで得られたkeyがtargetKeyと等しいか、チェックします
--ここには書いてませんが、このループに入る前に、1度WebAPI...
-keyとtargetKeyの大小関係に応じて、GET_LEFT_INDEXかGET_RI...
-これらは関数ではなく、defineで定義していて
#geshi(c++,number=on,start=14){{
#define GET_LEFT_INDEX(x) (x + x)
#define GET_RIGHT_INDEX(x) (x + x + largeNumber("1"))
}}
-という具合にインデクスを決定しています
--掛け算が実装されてないので、足し算をするのがミソ。
--また、インデクス自体がクラスなので、''+1'' でなく、''+l...
*感想 [#o3769a4c]
-面白かった!
-内部の挙動を推測して、それに応じてコードを書くのは楽しい
-その挙動の推測に曲がった引っ掛けを使わないあたりに、結城...
ページ名: