123日目です. キリがいいですね(いいのか?).
今日は一日中部屋で本読んでました.
アウトプットの為に最後にまとめます.
おきたんご
— 桜ねね (@ykm_kn) 2017年6月29日
いつも通り, 起床失敗.
NEW GAME!!のTLになったので逃げます
— 桜ねね (@ykm_kn) 2017年6月29日
今日先行上映あったみたいですね. 帰国が楽しみです. ほんとに.
6巻もOVAも家に届いてるので早くNEW GAME!したい.
老害なので後輩に「エディター何使ってるんです？」って聞かれて30分は喋ってた
— 桜ねね (@ykm_kn) 2017年6月29日
もう3年ほどですかね. Vimを使い続けてますよ(vimrcには拘ってません).
emacsが嫌いというわけではありませんが, "Ctrl + z" は死んで欲しいですね.
死ね死ね死ね
空港でSIM買うべ
— 桜ねね (@ykm_kn) 2017年6月29日
空港でSIM買ったら高すぎでしょ💢
— 桜ねね (@ykm_kn) 2017年6月29日
そろそろ帰国日が迫って来た(n回目)ので色々と準備し始めました.
空港からのバスのチケットも取れました. 問題は飛行機の遅延がどうなるか.
実はもう公開してあるんですけど, 誰にも気づかれてないですね. HAHA
-以下まとめ-
何読んでるかは, 既読者ならわかるかもしれませんね.
今日読み進めたのは, 大きく分けると
- 探索
- データ構造
- 再帰/分割統治法
です(順不同).
データ構造はstackとかqueueとかですね. 多少の知識はありますが, 本当の基礎からやってるのでじっくり読んでます.
C++のSTL使うとFIFOとか知ってれば使える(?)はずですが, 自分で実装するときどうするかみたいなのも知見として得られたのでよかったです.
スタックの場合は index-0 を 常に空けておくことで[head, tail]を[0, 1]にもどすだけで初期化できるとか,
キューではリング構造にすることでオーダーをO(1)にする とかですかね.
配列の長さ以上になりそうな時に, 次の参照先を (tail + 1) % LEN にすることで if文を書かずに済むというのもおお〜という感じで.
今までの僕なら普通にif文で tail と LEN 比較でやってたと思うので.
探索は2分探索と線形探索です.
線形探索は順番に見ていくだけですが, 最後に番兵を置くことで比較を減らせるテクニックがあるということくらいでしょうか. while(1)でも必ず見つかることが保証されてるので, 見つかった値を返してそれを呼び出し元で比較すれば発見できたかどうかわかるわけで. 一回一回比較してたらアですからね.
2分探索はソートされていることが前提条件ですが, LinearSearchと比べて計算量が少ないのでいいですね.
2分探索そのものはそこまで難しくはないんですが, 実際にこれを適用してる問題にびっくりしました. この問題で2分探索使えるのか!? と.
最後に再帰ですが, ある関数が内部でその関数を呼び出すアレです.
例として階乗を計算する関数が挙げられてましたが(わかりやすいのかな), スタックに積まれる引数考えるとfor文で計算した方が現実的なんでしょうか.
スタックを考慮しないといけない数字になる前にオーバーフローしそうですけど.
ExhaustiveSearch(いわゆる全探索, 力任せ法?)は,
ある数列を2つ与えて, 数列1の数字の組み合わせで数列2の数字はつくれるかどうか, という問題でした.
数字1つに対して含める含めないしかないので, 通り数は2^nになりますがこの問題ではnはそこまで大きな数字ではないので再帰で全探索するというわけですね.
この問題では作れるかどうかしか出力しないので, どの組み合わせになるかはわからないんですね. スタック使っての応用が期待できそうです.
もう1問の再帰は KochCurveと呼ばれるものを作成して, 各頂点の座標を出力するというもので, これ自体は再帰するだけですが, 座標の計算にベクトル計算が出てくるので久しぶりにやってました. それだけ.
余談ですが,
"I'm exhausted"というとクソ疲れたみたいな意味になるんですが,
exhaustiedは消耗したとかそういう意味なんですね.
Exhaustiveは網羅的という意味でした(Google翻訳). 網羅的探索, つまり全探索ですね.
はい終わり.
明日はPanzer vorするぞ〜(頑張る)
