アルゴリズムとデータ構造についてOSSから勉強する会に参加してみました
1月12日に、アルゴリズムとデータ構造についてOSSから勉強する会に参加してきました。
場所
Samurai Startup Island | SSI
〒140-0002 東京都品川区
東品川2-2-28 Tビル2F
品川からバスに乗ろうかと思ったら、バス停の場所がわからず、バスを逃した為、品川から歩きで向かいました。
場所はスタートアップ系のシェアオフィスを使わせていただいたようで、とても、広くて快適でした。
きっかけ
きっかけは、core-algorithms-deployedだったとのこと
ds.algorithms - Core algorithms deployed - Theoretical Computer Science Stack Exchange
勉強会で対象に設定していた人たち
対象者と参加者レベルについて
- 対象者
・アルゴリズム・データ構造を学びたい（学び直したい）人
・ついでにOSSのcode readingしたい人
- 参加者レベル（以下の要件を満たす人が半数いれば良し）
このぐらいの設定で、敷居がグッと下がっていて、参加しやすかったです。
特に、主催者のn_at_yasukun_orgさんもその辺り非常に気を配って頂いて、グループ分け等をしていただいたので、とても良かったです。
ちなみにこれらのお話は、事前に公開されているgoogle docsにも書いてあります。
会のモチベーションについて - Google Drive
スケジュール
スケジュールはこんなかんじでした。
14:00 -- 14:30 主催者からこのシリーズのモチベーションについての説明
14:30 -- 15:00 自己紹介とアイスブレーキング
15:00 -- 16:30 前半戦（進め方は1週間前のオンラインミーティングで決定）
16:30 -- 17:00 おやつタイム（CodeIQ様がおやつを用意してくれます！！）
17:00 -- 18:30 後半戦（進め方は1週間前のオンラインミーティングで決定）
18:30 -- 19:00 クロージング
19:00 -- 懇親会
ちょっと時間は短めだった気はするのですが、結果的に自分たちのグループはなんとか発表できてよかったです。
ただ、もっと長い時間ソースを読めたり議論したりしても面白かったかなぁと思いました。
お話を伺っていて、凄くいいなと思ったのが、主催の方が以下のようなルールを設けていた所です。
・分かる人がわからない人を助けましょう
・助けられたらお礼に何かをしてあげましょう
- 例1) 助けられた人がわからない事を説明してあげる
- 例2) あるいは別の分からない人に説明してあげる 等など・教えてもらってもわからないのは、教える人が悪い！
・役割分担はあんまりよくないので、やらないほうがいいかも
- 例）俺、コードを読む係だから、お前、テストコード書く係な！みたいな。
こういうのマジ大切だと思います。
こういう空気を積極的に作っていただいたおかげで、会自体も和気あいあいとしていてとても楽しかったです。
議論中に脱線した話とかもありまして、とても勉強になりました。
例）kernelのコードは、割り算を使ってはいけない事になっている等。
→理由としては、何かの間違えで、0で割り算をさせることになるとOSがクラッシュする為、掛け算に変換して割り算を行っている。
取り扱ったテーマ
取り扱う内容は、事前に主催者の人が選定してくださっていました。
こんな感じ。
- Linked List
- doubly linked list
- lock-free linked list
- B+ Trees
- Priority sorted list
- Red-Black trees
- Redix trees
- Priority heap
- Hash functions
- Hash tables
- Bit arrays
- Semaphores
- spin locks
- Binary search
- Binary search with B-trees
- Depth first search
- Breadth first search
- Merge sort
- Bubble sort
- Knuth-Morris-Pratt string matching
- Boyer-Moore pattern mathing
よくよく見てみると、知っている内容が一つや二つぐらいあるのではないでしょうか。
OSSのkernelコードリーディングっていうと、かなり仰々しいイメージが有るのですが、実際に見てみると、
馴染みがあるアルゴリズムがいくつかあって、それが僕にとっては心の救いでした。
チーム編成の仕方
「はい、二人組作ってー」な恐怖な展開はなかったです。
普通に、自分の席以外のどこかに移ってーみたいな感じでやってました。
ただ、最初に、
「この中でグルの人いますか？」
「この中でウィザードの人いますか？」
みたいに、かなりぶっとんだ聞き方をしてるのには、ワラタ。
グルやウィザードはいなかったけれども、firefoxのJavaScriptエンジンのコミッタの人はいて、びっくりした。
チームができてから…
チームができますと、その中でチームでどの部分のコードを読むかみたいな話し合いになります。
僕のチームは、HashFunctions、HashTablesを解析しようということで、読み進めることになりました。
詳細はこちら↓
LinuxKernelのHashFunction(ハッシュ関数)の仕組みについて - 手が震えたらBARに行こう
おやつタイム
今回は、CodeIQの人が、おやつを提供してくれました！
どうもありがとうございます。
僕は歌舞伎揚げといちごポッキーをバリバリ食べてました。
でも、このおやつタイムのおかげで、和気藹々と話ができたりして、よかったです。
ちなみに、よかったら、解いてみてNE！と出されたのが以下の問題
挑戦者求む！【アルゴリズム】初歩的なアルゴリズムとC言語の問題 by アルゴリズムとデータ構造についてOSSから勉強する会 中村 泰行│CodeIQ
ちなみに自分は、
こ…こんなの簡単だよ（震え声）
って感じでした。
後半戦
後半戦はそろそろ発表資料作らないとNE！
みたいな感じになってきたので、ポツポツと資料を作り始めることに。
発表会
各チームが自分たちの調べたアルゴリズムについて発表をする感じでした。
基本的にCで書かれているコードが多くて、マクロを使いまくってる印象でした。
最初は↓ぐらいできたらいいよねーみたいな話だったのですが、自分たちの班は、テストコードまでは用意できませんでした。
チーム成果物のテンプレ（参考）
アルゴリズム・データ構造の概要
擬似コード
利点・欠点
何処で利用されているか？
テストコード／使ってみたコード
でも、テンプレがあるのは、とてもありがたかったです！
懇親会
近所のさくらなんとかで懇親会！
当日名刺を持っておらず、大変に失礼しました。
ただ、いろんな話で盛り上がれて、とてもおもしろかったです。
あと、なんか、貼らなきゃいけない使命感に駆られたので、以下のリンクを貼っておきます。
ウンコード・マニア
登 大遊 - 某大学にアヒルボートを置いた学生 (誰かは、公開されていない)... | Facebook
とまぁ、そんな感じでした。
とても勉強になりました。
どうもありがとうございました。
次もできたら、参加したいなと思います。
よろしくお願いいたします。
