競技プログラミングは業務の役に立つか？　~ OSSデベロッパー編 ~

こんにちは。データプラットフォーム本部の鯵坂（@ajis_ka）です。

OSSデベロッパーとしてヤフーでの業務でApache Hadoop（以下、Hadoop）コミュニティで開発を続ける傍ら、昨年から趣味として競技プログラミングを始め、オンラインやオンサイトのコンテストに参加しています。

Hadoop Committerとしての仕事

Hadoopは、オープンソースの並列分散処理基盤で、分散ストレージであるHDFS（Hadoop Distributed FileSystem）と、リソース管理を担当するYARN（Yet Another Resource Negotiator）の2つのコンポーネントで主に構成されています。Oath, Microsoft, Twitterなど大規模データを保持・活用している企業に特に利用されており、Yahoo! JAPANでも利用されています。私は2013年からHadoopコミュニティでの活動を続けており、2014年12月からCommitter（公式リポジトリへのpush権限を持つ人）に就任、2016年1月からPMC（Project Management Committee）メンバに就任して、パッチ投稿やレビューなどのいわゆるOSSコミュニティでの開発に加え、リリースマネージャ、脆弱性の修正/公表、新規Committerの選出といったコアな活動も実施してきました。

• 参考: Apache Hadoop 2.9.2をリリースした話

これらコミュニティでの活動の詳細については、2月中旬に別枠で記事を投稿する予定です。よろしければそちらも併せてご覧ください。

競技プログラミングに興味を持ったきっかけ

私は2018年9月にヤフーに転職してきたのですが、その際に採用選考の1つとしてコーディングテストを受験しました。これまでHadoopコミュニティで長く活動しており、その間コーディングはずっと続けていたので、さすがに全問解けるだろうと高をくくっていました。しかしながら、最後の1問が難しくて、当時の私では全く歯が立ちませんでした。それが非常に悔しかったので、さらなるコーディング力を身に付けたいと思い、AtCoderにアカウントを登録してコンテストに参加し続け、2018年の末に青コーダー（レート1600~1999, 上位7％）になることができました。コーディングテストの最後の1問が解けるくらいの実力はすでに身についたと思っていますが、過去問を解いたりコンテストに参加すること自体が楽しくて、今でも競技プログラミングを続けています。

• AtCoderアカウント: https://atcoder.jp/users/aajisaka
• 今年中に黄コーダー（レート2000~2399, 上位3％）になることを目指して、コンテストの過去問を解く、頻出のデータ構造やアルゴリズムをライブラリ化するなどの精進をしています。

実のところ、大学4年で研究室に配属されたときに研究室の先輩から競技プログラミングに誘われていました。それから10年以上たった今になってから競技プログラミングにのめりこんでいるなんて当時の自分には信じられないだろうなぁと思いますし、誘われたときに始めておけばよかったと若干後悔しています。逆に、社会人から競技プログラミングを始めても十分に楽しめると思うので、「競技プログラミングをやってみたいと思っているけど、やってる人は学生ばかりだし…」と躊躇している社会人にもぜひ参加してほしいな、と思います。

普段の業務と競技プログラミングの関わり

Hadoopの開発と似た点

私は競技プログラミングを始めてまだ半年ほどなのですが、Hadoopの開発と競技プログラミングには関連があると考えています。Hadoopは大規模データを高速に処理するためのミドルウエアなので、そのミドルウエア自体が高速であることは非常に重要です。そのため、ミドルウエア内部でも時間計算量を気にしながら開発することになります。また、Hadoopの上で動作するアプリケーションになるべく多くのメモリを割り当てたいため、Hadoop自体が利用するメモリはできる限り節約しなければなりません。そのため、空間計算量にも気を配る必要があります。これらは競技プログラミングで求められるスキルと本質的に同じであると考えています。補足ですが、私が尊敬しているHadoopのコア開発者がCoding Standards for Apache Hadoopというコーディング規約を書いており、そこでも計算量やデータ構造に関して注意すべきポイントが詳細に記載されています。

私の場合、セグメント木などの競技プログラミングにおいて頻出のデータ構造を全く知らない、ダイクストラ法などの頻出アルゴリズムについても大学の授業では習ったけど実装をしたことがない、というような状態で競技プログラミングを始めたのですが、Map, Set, Arrayといった基本的なデータ構造はHadoopの開発を通じてひととおり自在に扱えるようになっていたのでAtCoderでいうところの水コーダー（レート1200~1599）になるのはあまり苦労しませんでした。

Hadoopの開発と違う点

Hadoopの開発と競技プログラミングの最大の違いは、分散処理かそうでないかだと考えています。競技プログラミングは、Google Distributed Code Jamなど一部の例外を除くと分散処理には対応していませんが、Hadoop上で動作するアプリケーションは、多数の物理サーバーで分散実行されます。そのため、アプリケーションを実装するときやチューニングを実施するときには、分散実行された状態でどれだけ処理が高速になるかを考える必要があります。

近年では、Apache Hive, Apache Spark, Apache Flinkなど、分散処理であることを意識させずに分散処理を実装するためのミドルウエアやフレームワークが整いつつあります。しかしながら、それらのフレームワークを利用して実装されたアプリケーションをチューニングをするためには、そのアプリケーション内で分散処理される部分とそうでない部分をWebUIやログ、ソースコードなどを見ながら確認し、分散処理されなかった部分をなるべく減らすにはどうすればよいか、といった考慮をする必要があります（他にもチューニングの観点は多数ありますが、ここでは省略します）。分散処理に向かないアルゴリズムで記載されている場合には、処理を丸ごと書き換えるようなこともありえます。

とはいえ、計算量のオーダーを正しく見積もることは分散処理であっても非常に重要です。例えば、N件のレコードを処理するのにO(NlogN)かかるプログラムとO(N^2)かかるプログラムがあり、定数部分は同じだと仮定します。それら2種類のプログラムに1億件のレコードを処理させると前者のほうが10万倍以上高速となり、仮にO(N^2)のプログラムをサーバー10000台で分散処理させたとしても、サーバー1台で動作させたO(NlogN)のプログラムの性能に勝ることは絶対にありません。

競技プログラミング同好会での取り組み

ヤフー社内には競技プログラミング同好会があり、新入会員として参加しています。最近は、社内のプログラミングコンテストに向けて作問やテストを実施しています。作問をするのは初めての経験だったのですが、問題に応じたストーリーを考えるなど、問題を解くのとはまた違った楽しさがあります。作問では問題文を作成するだけではなくテストケースの作成も必要ですが、そこでコーナーケースを考えるのも面白いです（これは業務での開発と似たところがあります）。

最後に

ヤフー株式会社では、2/9（土）に「みんなのプロコン2019」を開催します。

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

今年で3回目になるヤフー主催の競技プログラミングコンテストです。ヤフーに応募する前は、ヤフーが競技プログラミングのコンテストを主催していることは全く知らなかったのですが、同好会があったり、社内コンテストの参加者も多く、自分を含め競技プログラミングを楽しんでいる人が多くいるように感じています。「興味はあったけどなかなか手を出せていなかった」という人もいるかもしれませんが、もし、少しでも興味があれば今回の「みんなのプロコン」が初参加という方でもかまいませんので、ぜひご参加ください！