6/22 一生分のバックをした気がする
昨日の夜はOS自作入門とプロジェクト研究でやってる機械学習.
『OS自作入門』の方は8日目が終わった. マウスが動くようになった. 動きが奇妙なのはなんなんだろう. 妙にたくさん動いたり, 途中から水平方向にしか動かなくなったりする. 自分がどこかでコード書き間違えたのか, そもそもこういうものなのか.
機械学習の方はMALSSという支援ツールを使っているので, アルゴリズムの中身とかは一切理解していない状態. そもそものモデルの評価が難しい. 入れ子の交差検証なるものをしているらしい. 外側のループでテスト用のデータセットと訓練用のデータセットに分割, 内側のループで訓練用のデータセットをさらに分割しているらしい. 内側の交差検証はハイパーパラメーターの調整のためのものって認識であってるんだろうか？
Nested versus non-nested cross-validation — scikit-learn 0.18.2 documentation
MALSSの分析レポートを見ると最初にアルゴリズムごとの精度(入れ子式交差検証)が示されていて, その後に各アルゴリズムの詳細が書かれている. この詳細の方にはグリッドサーチの結果としてそれぞれのパラメータでの精度(非入れ子式交差検証)が書かれている. 疑問なのはこのグリッドサーチの結果の精度が非入れ子式交差検証になっていること. これってどういう値なんだろうか？
AOJ-ICPC
-
カーテン | Aizu Online Judge [解答]
座標圧縮っぽいことをする(実際やってることとしては, vectorに全要素を放り込んでソートしてユニークな要素だけを抽出してる). 圧縮してできた格子の各セルについて, (1) カーテンの領域に含まれていない (2) 窓の領域に含まれていることを調べる. (1)は問題なく判定できる. (2)はセルの中心からX軸/Y軸に平行に半直線(向きは正負どちらの方向でもOK)を伸ばして, 多角形の辺と交わる回数を数える. X/Y方向とも奇数回交わっていればそのセルは多角形の中に含まれる. (1)(2)を満たすセルの面積を足しあげれば求める答えになる. セルの数がN^2で各セルについて(1)(2)を満たすかの判定がO(N)でできるので, 計算量はO(N^3).
とまぁ、こんな感じで解けるのだけれど, 最初は窓の辺とカーテンの辺の交点を求めて...みたいなことをするのかなぁぐらいしか考えつかなかった. 解説を見てなるほど〜といった感じ. 国内予選の本番だったら手元実行にものを言わせて力づくで解くのかなぁ. -
Matsuzaki Number | Aizu Online Judge [解答]
素数を列挙してNより大きいP個の素数のペアの和を求めてソートしてP番目を出力する. ペアを列挙するときに重複したペアを数えているのに気づかなくて困ってしまった.
朝一にヤマトのお兄さんが来て, 寝ぼけながら荷物を受け取ったもののよくよく考えると配達日時って日曜に変更してなかったっけ？と. 後からもう一度ヤマトのお兄さんが来て「間違えちゃったけど大丈夫でした？」と聞かれたけれど, まぁ受け取れたんで問題ないっす.
日中は自動車学校でバックを使う技能教習を3限分受けたので疲れた. 左右の方向転換と縦列駐車. スケジュール立てた人は僕に恨みでもあるのかと. 縦列駐車とか前と後ろの車が高級車だったら間違いなく諦めますね......
6/21 OSわからん
『OS自作入門』をやっているのだけれど, 各回でのコードの差分を追うのが結構しんどい. こういうのは思考停止で写経したいタイプなので, 前回までの自分で書いたコードと配布されているコードを見比べながら書き足している. 毎度忘れてしまうので, その時のシェルコマンドをメモ.
- 配布されているファイルをリネーム
find ./ -type f | grep '\(\.c\|\.h\|\.nas\)' | xargs -n1 -Ifname mv fname fname.old - 前回のディレクトリからファイルをコピー
find 前回のディレクトリ -type f | grep '\(\.c\|\.h\|\.nas\)' | xargs -n1 -Ifname cp fname ./ -
今いるディレクトリからリネームしていたファイルを削除
find ./ -type f | grep '\.old' | xargs -n1 rm
find, grep, xargsだけでファイルに対して一括で操作ができるのでとても便利. 特にxargsの-Iは覚えておくと表現できるもの増えるのでオススメ.
ちなみに本編の進捗自体はまだ7日目なのでアレ. 慣れない単語が多すぎるので少しづつメモをとっている. 自分で整理しながら勉強するなんてかなり久しぶり.
AOJ-ICPC
- みさわさんの根付き木 | Aizu Online Judge
構文解析してツリーを取り出して、取り出したツリーを合成して、それをまた文字列表現に直すのが少し面倒. -
You Are the Judge | Aizu Online Judge
正答数の降順, ペナルティの昇順, チームIDの昇順でソート. std::pairは便利だなぁ. -
夏合宿の朝は早い | Aizu Online Judge
強連結成分分解して, 各人が他の人からモーニグコールされるかどうかを調べる. 連結成分毎に,
(1) 参照されていない人がある場合はその人たちが全員起きればOKなので, それらすべてが起きられる確率をかけ合わせる.
(2) 全要素が参照されている時は閉路になっている(？)ので誰か一人が起きていればOK, つまり(1 - 全員が寝坊する確率)をかけ合わせる.
ちなみに, 強連結成分分解にUnion Findを使うのって一般的なんでしょうか？
あと、DBスペ受かりました.
ガッキー結婚してくれ〜(DBスペシャリスト受かりました) pic.twitter.com/vkBOyLIBMk
— 加藤真也 (@0x19f) 2017年6月21日
OSAの中間、解答と書いたこと全然違ったわ. ウケる(真顔).
6/20 初投稿
インターネットアーカイブで某先生の昔のブログを読んでなんとなく僕も日記的なものを付けようかなと思ったので、これからなるべく毎日(？)書いていこうと思う
今日は朝9:00前に起床、1限を受けに大学へ
気がついたらCデベの内容が結構進んでいた
2限休講なのでAOJ-ICPCを解く
・Usaneko Matrix | Aizu Online Judge
N = 1のときだけイレギュラーなのが面倒
・JAG-channel | Aizu Online Judge
模擬国内250点の最後の問題AC
お昼はこころで優勝
zuraのおじさんが溜まったスタンプカードを消費してた
3限はプロBの中間
思っていたよりOCamlできた(？)のでセーフ
(まさか実行結果の型を書かせる問題が出るとは思ってなかったので面食らったけど)
# (+) 1;;
の実行結果がどうなるかとか理解できてないと普通につらそうな内容だった
今日はもう1問
筋肉みたいな実装でゴリ押し
AOJのオンラインジャッジでTLEするときはbits/stdc++.hをインクルードすると速くなるという知見を得た(？)
