条件が「16桁の数文字列、最大一千万件、未ソート」で、「その全データがユニークであること」を確かめるアルゴリズムのセオリーって何だろう。

考えてたのは以下

  • なんとかして、二分探索を毎回行なうようにする
  • ハッシュ
  • sort | uniq

とか。初めの、二分探索を毎回行なうようにするというのは、探索が失敗した場合はその要素を途中に挿入しないといけない。配列だと挿入はコスト高だし、リスト構造だと二分探索できるのかなー?

というか、リスト構造の二分探索ができるのは二分木か。普通の二分木はソートされたデータが入力されたデータがきたら、結果的にリニアサーチになるのに、AVL木を使えばソートされたデータが入力された場合も、探索が O(log n) でいけるか。

うーむ。普通の二分木探索をしていていいのだろうか > 某プログラム

あとハッシュは意外に難しい。ハッシュ関数が悪いのか、ハッシュ数(?)が悪いのか、テストしたら半分以上が衝突する。

コメントを残す

メールアドレスが公開されることはありません。