こんにちは。お久しぶりです。ふるやん(@furuya1223)です。
気がついたら社会人一年目が終わっていました。いつの間に。
先日の ICPC のスポンサー紹介動画で「競プロが業務に役立った経験はあるか」について少し触れましたが、その動画の公開が終了したので、社会人一周年記念も兼ねてそんな話をしようと思います。
※ 2021/4/3 19:03 に「動的計画法」「編集距離 DP」について加筆し、トポロジカルソートに関する記述を一部修正しました。
目次
前置き
私は大学 2 年ぐらいから AtCoder を始めた者です。レーティングは黄色ですが最終参加は 2021/1/16 です。なお、厳密には情報系の学科出身ではありません。AtCoderプロフィール
仕事では音声認識の研究開発をしています。つまり、多くのソフトウェアエンジニアとはだいぶ違うことをしています。
なので、ほとんどの人には参考にならないと思います。
あくまで、こういう事例があるんだねという程度にとどめておいてください。
本記事の内容は私個人の経験と感想です。ソフトウェアエンジニアの一般論については語れません。
また、役に立つから競プロをすべきとか、役に立たないからしないべきとか、そういう話もできません。
直接役立ったケース
DAG・トポロジカルソート・最短経路アルゴリズム
参考にしている音声認識システムの実装(C++)を読んだときに、言語モデル(WFST デコーダ)の処理が以下のような流れになっていました。
- ビームサーチで巨大な DAG の最短経路候補を探す
- ビームサーチによって作られた(幅が一定の)DAG をトポロジカルソートする
- 得られた DAG の top-k 短経路を探索する
DAG とトポロジカルソートの知識があったのですんなり読めました。
トポロジカルソートをする関数の名前が topsort となっており、トポロジカルソートを知らなかったら意味がわからなかったと思います。調べたところ、トポロジカルソートを topsort を略すのは一般的な慣習のようです。なので、調べればトポロジカルソートのことだとは分かりそうです。
top-k 探索については会社の技術ブログで記事を書きました。これは私は知らなかったアルゴリズムでした。調べて理解して記事を書けたのは、競プロでグラフの最短経路アルゴリズムの読み書きに慣れていたからかなと思います。
動的計画法(DP)
音声認識において、動的計画法が用いられるケースがいくつかあります。
古典的な隠れマルコフモデルを用いた音声認識では、最適な状態系列を見つけるためにビタビアルゴリズムが用いられますが、これは動的計画法です。
また、深層学習による音声認識には、CTC (Connectionist Temporal Classification) 誤差関数を用いるものがありますが、これによって最適なパラメータを学習するために動的計画法による計算が用いられます。
どちらも簡単にいうと、辺に遷移確率が割り当てられている DAG があるときに、ある頂点を通る確率を計算するようなものです。始点からの DP と終点からの DP で計算できます。
これらの実装を自分で書いたわけではありませんが、書籍や論文などを読んで理解するために競プロの経験が役に立ちました。
編集距離 DP
音声認識の出力がどれほど誤っているかを測る指標に WER (Word Error Rate: 単語誤り率)や CER (Character Error Rate: 文字誤り率)があります。
これらは、編集距離に基づいて計算されます。
つまり、CER = (正解と出力の編集距離)/(正解の長さ)× 100 (%) となります(さらに、100 % を超える場合は 100 % にします)。WER は単語単位で編集距離を計算します。
編集距離は、DP により高速に計算できます。
これを計算するためのコードは、私が会社に入った時点で存在していましたが、それを読んで理解するときに競プロの経験が役に立ちました。
また、最近は自作音声認識プログラミングをしていますが、そこでは編集距離 DP を手書きしました。
Trie・Aho-Corasick
ある実装に関する相談をミーティングでしていたときに、「この部分の実装は Trie で Aho-Corasick みたいにやることもできるけどそこまで高速化すべきか」みたいな話が出ました。
すぐに理解して議論についていけたのは競プロのおかげです。
なお、私は Trie も Aho-Corasick もライブラリを用意していません。調べたことがあるだけです(最近の AtCoder で出ないんだもん)。
簡潔データ構造・KMP 法・BM 法・Sufix Array
私の会社ではエンジニアやリサーチャーが持ち回りで技術ブログの記事を書いています。
自分が記事を書くだけでなく、他の人が書いた記事のレビューもします。
上記の知識についての記事が複数あり、それをレビューするときにある程度知識があるのが役立ちました。
簡潔データ構造については、競プロで使っているわけではありませんが、なんちゃって Wavelet Matrix (完備辞書を使っていない)を実装するときに調べたので知識はありました。
Suffix Array は SA-IS を実装しました。理解はしていない。
ICPC スポンサー
私の会社は ICPC のスポンサーをやっているので、先日の ICPC 横浜大会の懇親会に参加しました。オンラインでしたが。
競プロをやっていたおかげで、スポンサー紹介動画などで競プロerの方々に会社の紹介をできたのは役に立ったことかなと思います。懇親会に参加した新入社員は私だけですからね。
給料の出る懇親ができたのが大きい。
次回はオンサイトでお出かけしたいです。
間接的に役立ってるかもしれないケース
デバッグ
競プロで何百回もデバッグをしてきたので、バグの当たりをつけたり見るべき箇所を絞ったりする能力がついてる気がします。
チームのモブプログラミング(みんなで同じソースコードをいじる)でも、バグがあったときに「ここがまずそう」と最初にバグ箇所を見つけることが多いと思います。
「このエラーが出るということはこういう処理のパスを通っているはずだから」とか「このケースだけおかしいということはこれが原因っぽくて」とか、そういう考え方が競プロで身についていそうです。
実行速度の感覚
少し前に業務とは別の場面で、(プロのプログラマの方が書いたらしい)ある Python コードにおいて、list の途中の位置を指定して pop する部分を見ました。そのとき、こういうのは要素数の線形時間かかってまずそうだという直感が働きました。Python の list や pop の厳密な仕様について知らなくても、こういう感覚があります。
競プロをやっていると、パッと見では高速に動作しそうなコードでも、ある一行の処理に線形時間かかっていて TLE で落ちる、という経験をします。文字列の結合とか。
参照渡ししないと遅かったり、値渡しすべき場所で参照渡しをしてバグったり、という経験もします。
そういう経験が無いと、まずい実装をしてレビューで訂正が入って(あるいは見逃されて遅いコードが採用されて)時間をロスすることになり得ます。
それを知らずしらずのうちに防げているかもな、と思います。
言語仕様の知識
競プロをやっていると、他の人が書いたコードや解説記事を読む機会も多いです。
また、競プロ界隈でツイッターをやっていると、ショートコーディングや変態的なテクニックを使ったネタにも触れる機会が多くなります。
そのときに、自分が知らない機能を見ることがあります。
その経験のおかげで、言語仕様や標準ライブラリの機能について知識が増えました。
人間関係
大阪生まれ大阪育ち実家暮らしだった私は就職して初めて関東で一人暮らしをすることになりました。
はっきり言って暇です。家に話し相手がいないのもつまらないし、気楽になんでも話せる友達と頻繁に会えないのも退屈でした。
ですが、最近は(現・元)競プロerのボードゲーム好きの方々と一緒によくボードゲーム会をやっています。緊急事態宣言中を除き。
完全リモートワークになって、会社内でも会社外でも交友関係を広げられないなあ思っていましたが、競プロの繋がりがありました。
退屈しのぎ、ストレス解消に大いに役立っています。みんなありがとう。
競プロによる弊害はあるか
「競プロをしていたからこのミスをしたな」というようなことは、感じたことがありません。
「競プロをしていなければ良かったな」と思ったこともありません。
一方で、「競プロに時間を費やしたせいでこの能力が低いな」という話は、難しいところです。
というのも、仮に私が競プロと出会っていなかったら浮いた時間を(競プロ以上の)研究能力・開発能力の向上に充てていたか、というのが不明だからです。
大学 2 年の初夏、大学図書館の PC(だったっけ)で AtCoder の情報を見ていなかったら、機械学習コンペに参加していたかもしれませんし、見たアニメの本数が倍になっていたかもしれませんし、数論の勉強をしていたかもしれません。
「競プロの代わりにアプリ開発をすれば開発能力が上がるんだからそうすべきだ」という主張を受け入れるなら、やめるべきは競プロではなくアニメ視聴でした。ピーク時は 1 クール 15 本とか見てたんですから(ショートアニメ含む)。アニメ視聴が業務の役に立ったケースはほとんど思いつきません(一つあるかも)。競プロ同様、アニメのおかげで人生は確実に豊かになっています。
弊害の有無は、分からん。
おわりに
「意外と業務の役に立った娯楽」というのが私にとっての競プロです。