はじめまして。freee株式会社の浅羽です。普段はSREや情シス等のエンジニアリングマネージャーをしつつ、エンジニアの新卒採用も担当しております。
昨年の話になりますが、機会がありまして早稲田大学の清水先生が担当されている「アルゴリズムとデータ構造」の特別講義を2コマ(12/15, 22)させていただきました。
- 対象は情報系の大学2年生
- C言語でアルゴリズムとデータ構造を学習
- データベースの授業はまだ行われていない
- 一コマは90分
- 学生さんはマシンを持参して課題をその場で解くことが可能
資料や練習問題等を公開しましたので、せっかくなのでどういう内容の講義だったかを紹介したいと思います。
講義内容をどうするか？
当然ですが大学の先生が知識や教え方のプロです。1エンジニアがアルゴリズムとデータ構造の講義を普通にやっても、普段の講義のクオリティを超えるのは難しいと思いました。
一方でWebサービスの開発・運営をしている中でどうアルゴリズムとデータ構造が使われているかについては多少はお話できるかなと思い、どう使われているかの実例をベースにお話するほうがよさそうとなり、講義内容を組み立てました。また、なるべくイメージできるように、習得済みのアルゴリズムとデータ構造だけでしっかり理解できるように、なるべく新し概念を入れないようにしました。
とはいえ、RDBMSも少し扱う関係上、どうしても次の年で学ぶ予定のデータベースについて扱う必要があったので、なるべく難しい概念は話さないようにしつつ、まだ講義では習っていない内容については説明しました（したつもりです）。
Webサービスの一般的な要件
freeeのサービスインフラの話というよりは、なるべく一般化してどういう要件が求められているかを最初に説明しました。とはいえ全部を話そうとするとそれだけで一コマ使えそうなボリュームになりそうなので、そのあとにアルゴリズムとデータ構造の話につながるようなトピックだけを選んでお話しました。
- リクエストに対してレスポンスを速く返したい
- 何かしらのデータを読み書きすることが多い
- ユーザが識別されることが多い（ログイン機能等）
アルゴリズムとデータ構造の紹介
全部を紹介するのは当然難しいのと、受講済みの講義内容だけでイメージできるように、以下の3つに絞ってお話をしました。最初はもっと用意しないとまずいかなと思いましたが、演習も含めると十分な量となりました。
- RDBMSで使われているアルゴリズムのうちの一部
- B+Tree
- ソート
- テーブル結合
- いかに速くデータを検索・操作するかの一例として紹介
- KVS
- セッション管理を例に紹介
- ユーザの識別の一つの手法として紹介
- キュー
- 非同期処理を実現するためのコンポーネントとして紹介
- レスポンスタイムを早くするために急いで処理しなくても良いものは後回しにするよ、という説明
練習問題
テーブル結合を3つのアルゴリズムを実装してもらい、入力データが大きくなった場合にどれくらい実行時間が変わってくるかを計測してもらいました。
Nested Loop Joinに関しては内部表のスキャンはフルスキャンのみ実装している前提なので、実際はB+Treeからのフェッチでそこまで重くならないこともあるよ、とは口頭で補足しつつ、データが数十万件くらいになると大きく実行時間が変わってくるのを体験してもらいました。
GitHubに解答例を置いておきました。 github.com
講義後の感想
学生さんは非常に熱心に聞いてくれていて、授業の最後にアンケートを取らせていただいたのですが、おかげさまで満足していただけたようでホッとしております。幾つかフィードバックをいただいたので、たとえば演習時間をもう少し確保するなどを取り入れて次回の改善に結びつけたいと思っております。
宣伝
freeeでは現在2019年新卒エンジニアを積極採用中です。もし興味ある方はfreeeの新卒採用ページをぜひ御覧ください！
