hashmap で頻度集計

1 万件を数えるのに、1 億回比べている

配列の中で一番多く出てくる値を知りたいとします。素直に書くと、値を 1 つ取り出して「この値は何回出てくるか」を配列全体を歩いて数え、それを全要素ぶん繰り返す形になります。

要素が 100 個なら 1 万回、1 万個なら 1 億回。数えている相手はずっと同じ配列なのに、同じ場所を何度も歩き直しています。

紙を 1 枚だけ持って、1 周で終わらせる

人が手で数えるときは、正の字を書く紙を 1 枚だけ持って、上から順に 1 回読むだけです。同じことをプログラムでやります。正の字を書き込む紙にあたるのが hashmap で、Python なら dict、JavaScript なら Map がそれです。

大事なのは get(code, 0) の 0 です。初めて見るコードには、まだ欄がありません。tally[code] + 1 と書くと Python はその場でエラーになり、JavaScript では undefined + 1 が NaN になって、以後ずっと数が壊れたままになります。「無ければ 0 から」を最初に書いてください。

これで、要素が 1 万個でも 1 万回で表が埋まります。

1 周で済むのは、表から欄を引くのに端から探す必要がないからです。値そのものが置き場所を決めるので、欄が 1 万件に増えても引く速さは変わりません。数える相手も整数に限りません。文字列でも同じ形なので、単語の出現回数もエラーコードの集計も、書くコードはほとんど同じになります。

数え終わってから、選ぶところで詰まる

表ができたら、一番大きい数の行を選びます。手が止まるのは、同じ回数の行が 2 つ以上あったときです。[4, 4, 3, 3, 2, 2] を数えると、こうなります。

3 つとも 2 回で並んでいます。どれを返すか決めていないと、表から取り出す順しだいで答えが変わります。しかも、その順は言語や実装によって違います。手元では通ったのに提出したら落ちる、という形で表に出てくるので厄介です。

今回は同点なら小さいほうの値を返す約束です。選ぶ側の条件には、回数の比較と値の比較の 2 つが要ります。回数だけを見ていると、同点のときに先に見た行が残ってしまいます。

空の配列に最頻値はない

要素が 1 つも無ければ、一番多い値は決められません。今回は -1 を返します。空の表に対して「一番大きい行」を探しても何も見つからないので、初期値がそのまま返ります。配列の長さを先に見て、分けてしまうのが確実です。

1. 配列は最大数千要素まで対応すること
2. 二重ループ (O(n^2)) ではなく hashmap を使った O(n) で実装する
3. 頻度が同じ値が複数ある場合は、その中で最も小さい値を返す。空配列なら -1 を返す