ぶちのブログ

競プロとCTFが趣味なWebエンジニアのアウトプットの場

競技プログラミングはWebエンジニアリングの役に立つか？

この記事は、AtCoder青色(highest)で、非情報系理系大卒、新卒1年目のWebエンジニアの私見です。

結論

そこそこ役に立ちます。

はじめに

先日、以下のようなツイートをしたところ反響が大きかったので、もう少し詳細に書いてみます。

業務内容と競技プログラミングの関わりについて

業務では、Webサービスの設計・インフラ・サーバーサイド・フロントエンドと、幅広く担当しています。
サービス内容としては、リコメンドや最適化などの難しいアルゴリズムとの関わりは少なく、いわゆる普通のWebサービスに相当するものだと思います。

そのようなサービスでも、競技プログラミングは、サーバーサイドとフロントエンドの開発で役に立つ場合があり、
特に多少複雑なロジックが入りがちなサーバーサイドの開発中に、明らかに競技プログラミングのおかげでコードの改善を行うことができました。

周囲のWebエンジニアのレベル感

競技プログラミング力という観点からのみで、自分の周囲のエンジニアに限った話をします。

大学などで専門的に学んでおらず、エンジニア歴が長く、優秀なWebエンジニアであっても、AtCoder換算では茶色になれるかどうかのレベル感の方が多いと思います。
(これは単に訓練を積んでいないからなので、ちゃんと取り組めば緑色~水色くらいになるのではないかと考えています)

現状として、自分の周囲に計算量に気を払ってコードを書ける人はほとんどいないように思います。

実例

簡略化した例を出します。実際にはもっと複雑でしたが、本質だけを抽出します。

a = [[2, 'b'], [1, 'a'], [3, 'c'], [4, 'd'], [5, 'e']]
b = [[2, 'あ'], [7, 'う'], [4, 'い']]

のようなデータから、

c=[[2, 'bあ'],[4, 'dい']

のようなデータを得たい(第一要素が同じものを連結する)場合に、ナイーブな実装になっていました。 (なお、第一要素のユニーク性は担保されています)

res = []
as.each do |a|
  target_b = bs.find { |b| b[0] == a[0] }
  res.push([a[0], a[1] + target_b[1]]) if target_b
end

res

RubyのArray#findは線形探索なので、この実装の計算量は、Aの要素数をN、Bの要素数をMとしてO(NM)になります。
このコードが書かれた当初は問題になっていませんでしたが、データ数が増加し、このコードがボトルネックとなっており、UXが低下していました。

HashMapを使えば簡単にO(N+M)に書き換えることができます。

hash_map_b = bs.to_h do |b|
  [b[0],b]
end

res = []
as.each do |a|
  target_b = hash_map_b[a[0]]
  res.push([a[0], a[1] + target_b[1]]) if target_b
end

res

空間計算量はO(N)またはO(M)ですが、そちらは問題にならないと判断しました。
なお、前処理としてソートをして、時間計算量をO(NlogN+MlogM)で空間計算量をO(1)として計算することも可能なはずです。

非常によく似た例が、世界で闘うプログラミング力を鍛える本のBCRについての章に載っています。

恐らく、この処理はAtCoder緑色であれば全く問題なく処理できるでしょう。
あいにく全く同じような問題は見つけられませんでしたが、300点問題あたりの典型レベルだと思います。

所感

第一に、Webサービスのボトルネックが、サーバーサイド言語による処理になることはあまり多くないです。
また、大量のデータを扱う際にも、SQLで処理することが多いため、(ちゃんとindexを貼って、N+1問題にさえ気をつければ)SQLの最適化によって隠蔽されます。

(逆に言えば、N+1問題やindexを貼り忘れるのような問題は、ほとんどやらかさないですし、すぐに修正されます)

この手の問題は、何らかの理由でSQLでの処理ができない場合で、さらにデータ数が多い場合にだけ、かなりスケールしてきてから発覚する上に、N+1問題等と比べると特定も難しいです。

一方で、普通に書いてしまいそうになる処理なので、比較的多くの場所で見受けられる、競技プログラミング的にはNGな実装なのかなと思っています。

まとめ

ここで上げた例は、Webエンジニアだけをやっていると習得しにくく、一方で、競技プログラミングをやっているとすぐに習得できる好例だと思います。

Webエンジニアが知っておくと嬉しい知識の一つに、水色くらいまでの競技プログラミングの内容は間違いなく入っていると思っています。
学生の方は、Web系の面接でも胸を張って競技プログラミングをして良いですし、すでにWebエンジニアの方も競技プログラミングを始めてみてはいかがでしょうか？

競技プログラミングはWebエンジニアリングの役に立ちます！