逆噴射式

« 2007年01月 | メイン | 2007年04月 »

2007年02月26日

N件のデータからK番目のデータを得る方法

もしGoogleに面接に行って「N件のデータに対して、大きい方からK番目のデータを得るアルゴリズムを考えろ」という試験を出されたら、という雑談をしたのでメモ。
Nは極めて大きい10億件とかのデータで、ソートされておらず、インデックスも張られていないとする。

■俺が最初に思いついた愚直なアルゴリズム
二分探索。
10億件のうちサンプルデータX1を1件抽出し、全件舐めてX1より大きいか小さいかを判定し、大きいものの数X1a、小さいものの数X1bを算出する。
X1aがKより大きければ、K番目のデータはX1aの範囲に、そうでなければX1bの範囲にある。
この繰り返しで絞り込む。
一応O(NlogN)だがlog₂Nの部分が激烈に大きいため実際やったら死ぬほど遅いと思う。

■次に思いついた少しマシっぽいアルゴリズム
分布数え。
1000個程度のバケットを用意し、全件舐めて1000段階に分けた評価値(Googleなら検索ワードへの適合率とか)で1000個のバケットに入る数を数える。
大きい方のバケットから順に数えればK番目のデータがどのバケットに入っているか分かる。
例えば適合率56.7～56.8%の中にあるというところまで絞り込める。
再び全件舐めて、56.7XXX%のXXXの部分で1000個のバケットに分類する。
これにより、例えば適合率56.7890%の中に目的のものがあるというのが分かる。
この時点で十分に少ない数まで絞り込めていないなら3回目の総舐めを、ある程度少ないようならバケットに入っているデータを全件取得してクイックソートする。
これもO(NlogN)だが、log₁₀₀₀Nなので総なめ回数は相当減らせる。
ただし、検索対象は何らかの数値化が可能なデータに限られる。

■Psychsの答え
バケットをK個用意し、10億件を前から順にフェッチし、挿入ソート式にバケットに突っ込んでいく。
溢れた分は捨てる。
これでバケットの一番末尾に残ってる奴がK番目。

そりゃそうだ

この回答のキモは、10億件のデータから5億番目とか言われるとエラー吐くしかなくなるが、現実問題として欲しいのは1番～100番とかであるため5億番目を取れる必要はそもそもないということ。
1万番目くらいでも恐らく十分速いしバケットも現実的サイズで済む。

実際どういうのが正解なのか、例えばGoogleの面接でこういうのを聞かれたら多分複数の状況を想定して色々答えないといけないんだろうけど、Psychsの回答は非常にスマートで感動したのでメモ。
「KってNと比べるとメチャメチャ小さくね?」ってとこに着目すればアルゴリズム自体は自明なものだけど、その着眼に即座に行かないのは俺ダメだなぁと思った。

投稿者 Juna : 01:54 | コメント (0) | トラックバック