月間 競技プログラミングは役に立つのか立たないのか 創刊号

自分は競プロで就活有利になったと思っているので役に立つと思います。(完)
結論が出たのでこの連載は終了となります。

上記に加えて少し業務の話ができればと思います。

レイテンシ

自分はバックエンドのエンジニアでしたが、その仕事はアプリやwebフロントからきたリクエストに対して適切な返却をすることでした。
ここで結構重要な概念として　レイテンシ と言うものがあります。

レイテンシとは、応答時間のことです、ここではリクエストを送ってサーバーが反応するまでの時間、と言うことになります。
https://ja.wikipedia.org/wiki/レイテンシ

レイテンシは少なければ少ないほどいい

例えばユーザーごとの決済一覧情報を返すAPIを考えます。
ユーザー情報と決済情報は別のマイクロサービスが扱っているとします。

簡単ですね、ユーザーを取得して各IDごとに決済を取得すればいい。

user_and_payment = []
users = service1.get_users()
for user in users:
	payment = service2.get_payment(user.id)
	user_and_payment.append({
		"user": user,
		"payment": payment,
	})
return user_and_payment

これをすると深夜アラートの電話が鳴り続けます。

何が問題かというと for 文の中で別のサービスへアクセスしていることです。
この時に起きているデータフローは下記。

mainルーチンとService2が別サーバーで、DBからデータを取り出して戻ってきているので処理は0.05[s]くらいかかるかもしれません。

ユーザー数が1000人いた時、この処理は 0.05 * 1000 = 50[s] かかることになります。

これが様々なユーザーが断続的に叩くAPIならサーバーは一瞬で枯渇することになります。
(例えばライブ配信アプリで、みんながいくら課金しているかを確認するためのAPI)

じゃあどうするか、一気に取得して混ぜ合わせましょう。

user_and_payment = []
users = service1.get_users()
payments = service2.get_payments()
for user in users:
	for payment in payments:
		if user.id == payment.user_id:
			user_and_payment.append({
				"user": user,
				"payment": payment,
			})
return user_and_payment

だいぶ早くなりました、これならユーザーが1000人決済情報が1000件あっても
1000 * 1000 のプロセッサ時間で計算することができます。

競プロをやっていると2回のデータ取得と 1/1000[s] 程度かなーと想定できるかと思います。(0.2秒くらい？)

1ヶ月後またアラートで起こされました。

ユーザーが10万人、決済が100万件に増えていたからです。
2回のデータ取得と 10万 * 100万 のプロセッサ時間がかかります。
また 100[s] ほどかかるようになっています。
O(N*M)だからですね。

N*Mの掛け算を止めるためにMを下処理します、

user_and_payment = []
users = service1.get_users()
payments = service2.get_payments()

# ここでmapを作成する
payments_map = {}
for payment in payments:
	payments_map[payment.user_id] = payment

for user in users:
	payment = payments_map[user.id]
	user_and_payment.append({
		"user": user,
		"payment": payment,
	})
return user_and_payment

mapの取り出しは中で木構造が使われてたとして、高々log(N)となります。
この変更によって

2回のデータ取得と 10万 * 100万 のプロセッサ時間
=>
2回のデータ取得と 10万 + 2*(100万log(100万)) のプロセッサ時間

ここで暴言を吐くと、logは定数なので、
2回のデータ取得と 10万 + 100万(オーダー) のプロセッサ時間
でデータを取得できるようになりました。(無事0.2秒に戻りました)

こんなシーンは仕事中少なくないです。
逆に上記のレベル感を大きく逸脱するパターンはあんま見かけないですが。(DPを使わないといけない場合など)
多くの場合はデータベース設計見直しましょう、みたいな話だったりするので。

タクシーの配車アプリでグラフアルゴリズムを使うとかありそうですね。

競プロは書き捨ての関数を書く競技なので継続的な開発にどうこう、、とか言われたりしますが、
結局会社も金と人を突っ込んで収益が出てくる関数なので本質は変わらないです。

func 会社(人, 金) 収益

ご愛読ありがとうございました。