条件が「16桁の数文字列、最大一千万件、未ソート」で、「その全データがユニークであること」を確かめるアルゴリズムのセオリーって何だろう。
考えてたのは以下
- なんとかして、二分探索を毎回行なうようにする
- ハッシュ
- sort | uniq
とか。初めの、二分探索を毎回行なうようにするというのは、探索が失敗した場合はその要素を途中に挿入しないといけない。配列だと挿入はコスト高だし、リスト構造だと二分探索できるのかなー?
というか、リスト構造の二分探索ができるのは二分木か。普通の二分木はソートされたデータが入力されたデータがきたら、結果的にリニアサーチになるのに、AVL木を使えばソートされたデータが入力された場合も、探索が O(log n) でいけるか。
うーむ。普通の二分木探索をしていていいのだろうか > 某プログラム
あとハッシュは意外に難しい。ハッシュ関数が悪いのか、ハッシュ数(?)が悪いのか、テストしたら半分以上が衝突する。