ヤフーにおけるアルゴリズム教育の取り組み

こんにちは。サイエンス1本部の真鍋です。
私は博士後期課程を修了後、2016年の4月にヤフーに新卒入社し、約半年間の新卒研修を経て現在のチームに配属となりました。それ以来2年半ほど、キーワード検索エンジンの実装と、検索結果ランキングの改善に取り組んでいます。

より具体的には、ヤフーショッピングの商品検索に関わっています。検索結果ランキングは主に機械学習で生成されたモデルによっているのですが、このモデルに商品のどんな属性や、ユーザーの皆さんのどんな行動を入力したらいいかを考え、その実現に必要なコードを実装するのが主な仕事です。快適なサービスを提供するために計算コストを削減したり、これら全てのことがスムーズに進むように運用コストを削減するのも大切な仕事です。

さて、キーワード検索エンジンもそうですが、世の中のサービスはいろいろなアルゴリズムで動いています。
今回は、そのいろいろなアルゴリズムを使いこなせるようになるために、サイエンス系の部門で行われている「アルゴリズム勉強会」についてお話ししたいと思います。

トピック

アルゴリズムを使いこなすための知識といっても広範ですが、現在は以下のトピックを扱っています。

• 計算量
• ソート
• 探索（線形探索・二分探索・ハッシュテーブル）
• スタック・キュー
• 木構造
• グラフ
• メモ化再帰
• 動的計画法

いずれも必須といえる知識ではないでしょうか。ヤフーではポテンシャル採用を行っており、プログラミングやアルゴリズムに対する受講者の理解度もまちまちなため、全体的にあまり踏み込んだ説明はせず、基本的な知識の抜けをなくすことを重視しています。

実施形態

実施形態も、受講者へのアンケートを元に毎年改善していますが、今年度は毎週一時間の座学でした。主な受講者は新入社員で、講師は先輩社員が務めます。講師は毎回最後に「宿題」を出し、受講者が次回までにそれを解いてくると、次回の冒頭で講師が解説を行うという流れになっています。もちろん、宿題を解くのも業務時間内です。

社内に宿題の提出システムもあり、解答のコードを送信すると、コンテナ内でテストケースの評価が行われ、正誤、実行時間、メモリ使用量がわかるという凝ったシステムが採用されています。宿題の提出自体は厳密にチェックしているわけではなく、解けなくてもペナルティはないためご安心ください。現在、プログラミング言語としてはC, Java, Python, Scalaなどに対応しています。

毎週決まった曜日の決まった時間に実施したのですが、もちろん他に優先度の高い業務があることもあるため、基本的には全ての資料は社内ネットワーク上にアップロードされており、それを見ればいつでも内容がわかるようになっています。

問題は例えばこんな感じです。

問題 2-B マージソート

問題文

マージソートを実装し、要素数 N の整数列を昇順にソートしてください。

制約

N <= 10^5

実行時間2秒以内

入力

入力は以下の形式で標準入力から与えられます。

N
a_1 a_2 a_3 ... a_N

出力

昇順にソートした整数列を空白区切りで出力してください。

例1

入力

4
3 2 1 4

出力

1 2 3 4

例2

入力

16
12 13 1 8 16 15 12 9 15 11 6 16 4 9 4 3

出力

1 3 4 4 6 8 9 9 11 12 12 13 15 15 16 16

効果

例えばこの問題を解いた場合、以下の効果が期待されます。

• プログラミングの基礎を身につけることができる。具体的には変数・配列・四則演算・比較・ループ・条件分岐など。
• マージソートというアルゴリズムがあることを覚えられ、ソートアルゴリズムの選択肢が増える。他のソートアルゴリズムと比較してのマージソートの特徴も覚えられるとなお良い。何も見ずに実装できるようになることを目指しても良い。
• 大きめのテストデータを使い、別の問題で実装したバブルソートと比較することで、マージソートがバブルソートより速いことが体感でわかる。テストデータの大きさが倍になると計算時間は約何倍になるかや、各ソートアルゴリズムにとっての最悪のデータ、最良のデータについても考えられるとさらに良い。
• ひいては、パフォーマンスを出すためにアルゴリズムの選択が重要ということが体感でわかる。実装するときに、その実装の効率について考えるようになるとなお良い。効率を改善できるようになればベスト。

受講者の皆さんからも、具体的なアルゴリズムを知るきっかけになった、あまり知らない分野に触れられて面白かったなどの声をいただいています。

個人的には、プログラミングの経験が浅いと落ちやすい落とし穴のようなものがあり、それに早め（実務より前）に落ちられるのもアルゴリズム勉強会の長所だと思っています。
例えば、配列の先頭の要素を削除すると、残りの要素を全て一つ手前にずらすことになるので、要素数に比例した計算量がかかってしまう、というのが頻出の例でしょうか。

おわりに

アルゴリズム勉強会の紹介、いかがでしたか？　ヤフーは2/9（土）、アルゴリズムを活用したプログラミングの能力を競う「みんなのプロコン 2019」を主催します！

コンテストの詳細はこちらよりご確認ください。

アルゴリズム勉強会の問題には、プログラミングコンテストの問題をベースにしたものも多いです。このことからもわかるように、プログラミングコンテストに参加するのもアルゴリズムに関する知識をつけるよい方法だと思います。アルゴリズムに興味のある方、そしてもちろん競技プログラミングに興味のある方、ぜひご参加ください！