1

いくつかの要素のセットが与えられます、例えば：

int set1[5] {5601, 935, 4153, 2195, 422};
int set2[5] {5601, 935, 23, 44, 422};
int set3[5] {4205, 935, 4153, 2195, 15};
int set4[5] {4205, 589, 4015, 44, 422};

順序が重要な場合（つまり、1、2、3が2、1、3と異なる場合）、特定のセットを見つけるための効率的なアルゴリズムは何ですか？たとえば、次の場所を特定します。

int value[5] {5601, 935, 23, 44, 422};

考慮事項：

  1. 新しいセットの挿入コストは問題ではないため、検索時間を最適化するために、任意のデータ構造に保存できます。

  2. セットには、それぞれ1〜1,000,000個の要素が含まれます（おおよそ、1〜1000個のセットがあります（これもおおよそ）。ただし、要素の数は、特定のセットのセットで常に同じになります（たとえば、1つである場合）。セットには10​​個の要素があり、すべてのセットには10​​個の要素があります）。

フォローアップの質問です。これをC++で実装するので、オープンソースのC ++ライブラリ（STL、Boost、QTが望ましいですが、検討します）に存在するかどうかにかかわらず、推奨されるアルゴリズムを調べたいと思います。他の人も）。

4

4 に答える 4

5

順序が重要な場合は、セットではなくシーケンスを確認します。用語が重要です。

検討しているシーケンスは約1,000であるため、ハッシュテーブルに格納するだけで簡単にパフォーマンスを向上させることができます。たとえば、各要素の文字列表現とある種の区切り文字を連結し、それをハッシュすることによって、各シーケンスを表す文字列を作成することを検討します。

于 2012-08-01T17:28:56.247 に答える
4

std::vector<set_type>セットを保存するには、を使用します。すべてのセットをコンテナに挿入します。を使用してコンテナを並べ替えstd::sortます。を使用して要素を検索しますstd::binary_search（またはstd::lower_bound、要素へのイテレータが必要な場合）。

使用するタイプはset_type、各セットの要素数によって異なります。要素の数が少ないことがわかっている場合は、std::array<T, N>それで十分です。それ以外の場合は、を検討してstd::vector<T>ください。

于 2012-08-01T17:27:40.313 に答える
0

セットの順序を定義してから、それらをツリーに挿入します。または、ハッシュコードとコンパレータを定義し、それらをハッシュテーブル化します。

于 2012-08-01T17:26:27.713 に答える
0

この場合、ハッシュテーブルを使用します。アクセス時間は次のようになりますO(1)（最悪の場合はそうですO(n)が、ハッシュ関数が適切であれば、これは問題ではありません）

したがって、Hashtabelが十分に大きく、スペースについて心配する必要がない場合、これは間違いなく最速の検索方法になります。（バイナリ検索がにあることを考慮してくださいO(log(n))）

ハッシュテーブルは、新しいC++0x標準のSTLでのみ使用できます。STL::TR1を参照してください

于 2012-08-02T22:52:08.830 に答える