map で出現回数を数える
エラーコードごとの件数を、変数で並べていられない
ログを読んで、どのエラーが何件出たかを数えたいとします。素直に書くと、こうなります。
Python
timeout = 0
not_found = 0
for line in log:
if line == "timeout":
timeout += 1
elif line == "not_found":
not_found += 1エラーの種類が 2 つならこれで済みます。ところが本番のログには、見たことのないコードが平気で混ざります。種類が増えるたびに変数と分岐を足すことになり、しかも 知らないコードは数えられません。行が 1 本増えるたびに、コードを書き足しに戻る羽目になります。
数えたい相手が事前に分からない。これが、この形の限界です。
キーごとに、小さなカウンタを持つ
必要なのは「値を渡すと、その値専用のカウンタが出てくる」入れ物です。
Python
counts = {}
counts["timeout"] = counts.get("timeout", 0) + 1
counts["timeout"] = counts.get("timeout", 0) + 1
counts["not_found"] = counts.get("not_found", 0) + 1
print(counts) # {'timeout': 2, 'not_found': 1}変数を先に用意していないのに、timeout のカウンタも not_found のカウンタも勝手に生まれています。初めて見るコードが来ても、その場でカウンタが 1 つ増えるだけです。取り出しも追加も、中に何件入っていても一定の時間で終わります。
無いキーに足そうとすると、落ちる
上の例で counts.get("timeout", 0) と書いたのには理由があります。
Python
counts = {}
counts["timeout"] += 1
# KeyError: 'timeout'+= 1 は「今の値を取り出して、1 を足して、戻す」という意味です。まだ 1 件も入っていないキーには取り出す値が無いので、その時点で止まります。JavaScript の場合は落ちない代わりに undefined + 1 が NaN になり、数えたつもりのものが全部 NaN になります。落ちてくれるぶん、Python のほうが親切です。
get(キー, 0) は「無ければ 0 とみなす」という書き方です。数え上げでは、この 1 手間がほぼ必ず要ります。
数え終わってから探すか、数えながら覚えるか
集計したあとで、いちばん多かった件数を知りたくなることがあります。やり方は 2 通りです。全部数え終わってから表をもう 1 周して探すか、数えている最中に「今までで一番多い件数」も持っておくか。
どちらも O(n) で、出る答えも同じです。違うのは、データを何周するかだけです。
要件
- 整数を返す。最大頻度 (もっとも多く出た値の回数)
- map / HashMap / dict を使い、1 パスの O(n) で集計する
- 空配列のときは 0 を返す
入出力例
frequency([1,2,2,3,3,3]) → 3
frequency([1,2,3,4]) → 1
frequency([5,5,5,5,5]) → 5
frequency([7]) → 1
frequency([1,1,2,2]) → 2
frequency([-1,-1,-1,0,1]) → 3ヒント
