![見出し画像](https://assets.st-note.com/production/uploads/images/42827474/rectangle_large_type_2_f37b93c2c285b6ea829dd664bb816ee5.jpg?width=1200)
2020 年振り返り プライベート学び編@CS
年の瀬にしたかった振り返りだが、忙しさを言い訳にしていなかった。 Better later than never ということで少しずつ行なおうと考えている。まずはコンピュータサイエンスの領域 [※1] に関して学んだことを記載する。
2019 年はコーディングインタビュー [※2] のスキルをあげていた。そんなわけで年の前半は AtCoder [※3] を後半は LeetCode [※4] を解いていた。 AtCoder でいうと ABC の C まではさくっと解け、 D や E に関しては解けたり解けなかったり、 LeetCode でいうと Medium くらいの問題は、ホワイトボードでも解けるようになった。
2020 年はこれらの技能を鍛えるための時間を割くことは控えた。コーディングインタビュー対策の意味合いが強く、社会情勢的 [※5] にしばらくはグローバルなテック企業への転職も厳しそうと考えたためである。
今一度ソフトウェアエンジニアとしての足腰を鍛えよう [※6] と決め、いわゆる古典的なコンピュータサイエンスの分野を学ぶことにした。まがりなりにも情報系の学部と修士を卒業した [※7] のだが、事実としてこれらの知識は忘却の彼方に消え去っている。いざ学んでみると、実装はともかく理論的な話は抑えていると思っていたが、実態としてはそんなことはなかった。非常に悲しいことだが前を向いて生きるしかない。伸び代がたくさんあるんだ。と。
本記事では以下の 2020 年に学んだ分野に関して、学び始めた背景、学ぶ前のレベル感、期間、参考資料、進め方、振り返りを軽く記載する。
データベース
学び始めた背景
仕事でデータベースのテーブル設計やパフォーマンス改善にも関わっており、データベースの理解を一段深めるのがちょうど良いタイミングであった。
学ぶ前のレベル感
それなりに複雑な SQL は書けるし、インデックスを利用する際のトレードオフは理解しており、システムの特性を考えた上で必要に応じてテーブルの非正規化も検討できる。ただしデータベースが SQL のクエリを受け取りデータを取り出すまでに何をしているかの理解は曖昧。
期間
2 月頭から5 月頭の 3 ヶ月強程度
参考資料
Sansan の技術ブログに記載されたDBMSをGoで実装してみたという記事 [※8]で紹介されていた CMU の DATABASE SYSTEMS という授業 [※9] が良さそうだったので、そちらの授業動画を観た。また、あわせて当該授業にあげられていた参考書のオンライン版と母校の授業で配られたプリントを読み返した。
進め方
授業動画を起点にスケジュールを立てて進めるのが良いかと考え、どの講義と参考資料をいつ見るかをスプレッドシートにまとめ予実管理をしながら進めた。
平日には資料類を読み、休日に講義動画を見るという進め方を行なった。授業の課題までは手が回らなかった。
振り返り
個人的には実行計画の評価方法やデータ結合の各種アルゴリズムの箇所が学びになった。もちろん授業で扱っているのは基本的な内容で最新のデータベースは違うところは多数あるのは事実だが。また、反省としてスケジュール通りに授業動画をこなすのに注力して理解が曖昧なまま進めてしまった。
※このまとめを記載している中で ARIES (Algorithms for Recovery and Isolation Exploiting Semantics) の内容やデータベースにおける Concurrency 周りをすでに忘れていることがわかったので再度の復習をせねば。。。
コンパイラ
学び始めた背景
データベースの授業を一通り終わりそうな時に、タイミングよく rui ueyama さん [※10] がオンラインブック「低レイヤを知りたい人のためのCコンパイラ作成入門」を教材に使ったオンラインコースを始めると呟いているのを気づく。
四則演算とカッコのある数式をパースして、計算結果を出力するプログラムを書けと言われてもできなさそうだったので、次はコンパイラにしようと決意する。学部時代の教科書もあるし、部屋で埃を被っているタイガーブック [※11] もあったのでそれらも読もうと考える。
学ぶ前のレベル感
字句解析して構文解析して中間言語を出し、リンカーがライブラリと繋げてアセンブリを出すことは理解していた。構文解析は確か LL とか LR(1) とかいうアルゴリズムがあった気がする。大学の実験で lex とか yacc を使った記憶もある。
期間
5 月頭から 10 月頭の 5 ヶ月程度
参考資料
- 低レイヤを知りたい人のためのCコンパイラ作成入門
- コンパイラ (情報系教科書シリーズ)(大学で使っていた教科書)
- 最新コンパイラ構成技法(通称 タイガーブック)
進め方
データベースでは内容の理解以上にスケジュール通りにこなすことに注力してしまったという反省があるので、コンパイラは一つ一つの理解をきっちりするように進めた。
本当は rui さんの教科書を見て自分で実装するのがいいのだけれども、写経してた。これには、 3 つのルールを決めて行なった。
- 少しでもいいからなるべく毎日進めること
- 1 コミットごとに何をやっているか説明できるようにすること
- セルフホストできるまでは進めること
毎日手をつけられたわけではないが、淡々と進めた。土日にはあわせて大学時代のコンパイラの教科書とタイガーブックを読み進めることにした。ただし、タイガーブックの演習問題までは解かなかった。
振り返り
構文解析周りのアルゴリズムを理解できた。再帰下降構文解析は課題含め理解しているという認識。(なお、 LL 法や LR 法はすでに忘れているが、説明を見れば理解できる。ハズ)他にも C の知らない文法やらグローバル変数とローカル変数の扱いの違いや、レジスタの割り当て法、継承の実現方法、 GC のアルゴリズムなどを学べた。自分でゼロから実装できるかといえば怪しいが、レベル感も色々あるけれども簡単なものならば参考書片手に内容は理解できるのではないかと考えている。
また、低レイヤを知りたい人のためのCコンパイラ作成入門は丁寧に説明されているのに加えて手を動かしてインクリメンタルに機能が作られていくのでオススメ。セルフコンパイルができた瞬間はテンションが上がった。
タイガーブックも時間をかけて読めば理解のできる内容であった。書籍が重版されておらず [※12] 、誤字脱字もそれなりにあったので翔泳社へ連絡をしてみた。丁寧な対応をしていただき、正誤表にも反映され [※13] ちょっと誇らしい気持ちになった。
オペレーティングシステム
学び始めた背景
データベース、コンパイラときて低レイヤーまわりといえばオペレーティングシステムも外せないよなぁ。と考えオペレーティングシステムの勉強を進めた。あえていうならば埃を被っている書籍が多かったためである。
コンパイラで手を動かすのが良かったので、こちらも手を動かすのが良いかと考え、教材としては作って理解するOSを読むことに。後半でひたすらアセンブラを書くのは正直辛かった。これでプログラムを書ける気がしない。
オペレーティングシステムとは?というところの知識には不十分と感じたので今は部屋で埃を被っていたタネンバウム本と恐竜本を読んでいる。分厚い本なのでまだまだしばらく時間はかかりそう。
学ぶ前のレベル感
オペレーティングシステムといえばコンピュータへの命令を抽象化して扱ってくれるもの。という認識。大枠で言うとファイルシステムとか外部デバイスの扱いに複数タスクを並列に実施してくれたり、メモリ周りの管理をしてくれるもの。キーワードで言うと資源の共有方法やコンテキストスイッチ、ページング、スレッドとプロセスあたり。が思い浮かぶ。
学んでいた期間
10 月~
参考資料
- 作って理解するOS x86系コンピュータを動かす理論と実装
- オペレーティングシステム(通称 タネンバウム本)
- オペレーティングシステムの概概念(通称 恐竜本)
進め方
9 月から調子を崩して休養をしていたので、調子が良い日にできる範囲で読み実装することにした。前半部は理解が厳しいということはあまりなかった。後半部の実装はアセンブリの読み書きが慣れていないこともあり、牛歩の理解で進めた。
振り返り
現状では、オペレーティングシステムを学ぶというよりアセンブラを読み解く力がレベルアップした気がした。作って理解するOSは、 Why というより How によった記載だった。こんな機能があります、命令はこうです。ではでは作っていきましょう!という感じでオペレーティングシステムに関して体型的にまとまっていないと感じられた [※14] 。悪い本だとは思わないが、個人的に理論と実装の紐付けがあまりできなくて残念だった。タネンバウム本や恐竜本に関してはまだ読み始めなのでコメントはなしで。実装周りははじめてのOSコードリーディング ~UNIX V6で学ぶカーネルのしくみを読めたらと考えている。
脚注
※1 自分の振り返りのしやすさで便宜上、タイトル含めコンピュータサイエンスと書いたが、2020 年学んだ領域のうち ACM と IEEE の発表しているコンピュータサイエンスの領域のものを全て記載しているわけではない。他の振り返り記事の内容もここに含まれるのでは?という意見が出てもおかしくはない。
※2 1 時間ほどの制限時間内に小さなプログラミング問題を解かせる面接形式のこと。英語圏の IT エンジニア職へ応募する場合はほぼ必須。日本でも一部の企業では実施されている。ホワイトボードやオンライン上の共有エディタでソースコードを書く。非常に緊張する。パニックになると非常に簡単な問題でも解けず、気がついたら面接が終わる経験をする。これはトラウマもの。
※3 日本で最も有名なプログラミングコンテストのプラットフォーム。ビギナー向けのコンテストは AtCoder Beginner Contest 、通称 ABC という。ビギナー向けと言っても、後半の問題の難易度は高い。
※4 企業ごとに過去に出たコーディングインタビューの問題を解けるサイト。転職の際に利用するのはデファクトスタンダードとなっている。正直 NDA 的に大丈夫なのかと思うところはあるし、試験対策は本質的ではないと思うところはある。一方で英語圏の IT エンジニア職での面接を受ける人は皆利用しているので、綺麗事は言ってられない。
※5 感染症の世界的大流行が発生し、多くの企業の募集がクローズされたため。 1 日でも早く収束することを祈りつつ、人との接触を避けた生活を送っている。根が引きこもりだけれども流石に疲れた。
※6 最新の技術もそれはそれで学ぶ必要はあるが、どうしても流行り廃りがあるのが悩ましいところ。基礎は仕事に直接役には立つ機会は少ないかもしれないが、ふとしたタイミングで必要となることがある。その際に力を発揮できるのは個人の価値にもつながる。また、理論に近ければ近いほど、長く使える知識である。そのため、投資対効果が高いと考えている。
※7 学部時代は気合いで単位は取得していたが、授業内容を真面目に勉強していたかというと不安が残る。修士時代も研究に関わる範囲のみに集中していたし、コンピュータサイエンスの修士号保持者のイメージと自分のスキルが少し離れている気がする。恵まれた環境にいたのは確かだが、それを生かし切れたかというと疑問である。学生時代はしっかり勉強しておくべきだというのは声を大にして言いたい。
※8 素晴らしい記事なので一読するのをおすすめする。
※9 平易な英語でわかりやすく説明してくれるので、英語だとビビる必要はない。 DJ がいるのが謎であった。英語で言われるジョークに対して皆が笑っているが自分は理解できなくて悲しい気持ちになる経験は多数あるが、本講義でのジョークも平易で理解できた(だから何だ)。
※10 非常に能力の高い著名なソフトウェアエンジニアの方。 note の記事はどれも面白いし、 Turing Complete FM という podcast を運営しており、どの回も非常に面白い。
※11 コンパイラの有名な教科書。表紙が虎の絵である。コンパイラでおそらく最も有名な教科書はドラゴンブックと呼ばれており、表紙は竜の絵である。捻くれ者だったので学生時代にドラゴンブックではなくタイガーブックを買った。未読のまま長い月日が流れていた。
※12 ずっと在庫がなかったけれども、最近になって増刷が決まった模様。原著でもいいとは思うのだが、自分レベルだと日本語の方が読むのは楽。
※13 翔泳社のサイトから確認できる。書籍を出している方から、誤字脱字の連絡も嬉しいものだと教えていただいたので、勇気を出してみた。
※14 30日でできる! OS自作入門も実装に非常によっていると伝え聞いたので選ばなかった。
目に見える形でのおめぐみをいただけたら幸いです……。