0

データ構造に関する質問があります。プロセスの存続期間を通じて成長する文字列のコレクションがあります。さまざまな期間でプログラムの周りにこれらの文字列への参照を渡すことができるようにしたいと思います。コレクションに重複を追加したくないので、1つを渡すと、既存のエントリへの参照が返されます。つまり、次のようになります。

const std::string& add_new_entry(const std::string&)
{
    // Check if string exists
    // Return reference if it does
    // Otherwise add to collection
    // Return reference to it
}

最も単純な実装は、文字列のリストとstd::find毎回の呼び出しですが、特に50,000以上の文字列を扱っているので、それが非常に最適ではないと感じずにはいられません。サイズ変更や移動を強制せずに要素を任意に追加できるように拡張配列コンテナを作成し、間接参照比較述語を使用してアルファベット順std::setに並べられた要素でインデックスを作成してstd::string*います。15文字列の比較はたくさんのようです。

4

5 に答える 5

2

O(log n)のパフォーマンスを取り除くには、ハッシュを使用する (および is )を使用setできます(または、本質的に同じですが、一部のコンパイラでのみサポートされています)。unordered_setO(1)hash_set

(最大) 15 の文字列比較を行っていることを考えると、常にこの最大値に達するわけではなく、これらの多くは 1 つまたは 2 つの文字を比較するだけであり、unordered_set(およびハッシュの競合を処理する)のハッシュを生成する可能性は十分にあります。 ) で値​​を見つけるよりも時間がかかりますset。

また、配列を取り除き、std::set<std::string>代わりに使用してみませんか? 参照を返すこともできます:

const string& add_new_entry(const string& str)
{
    set<string>::iterator iter = yourSet.find(str);
    if (iter == yourSet.end())
      return *yourSet.insert(str).first;
    return *iter;
}

テスト。

于 2013-02-23T14:24:03.850 に答える
1

最適化はいつでも可能で、時には非常に価値がありますが、50,000 エントリの場合は必要ないかもしれません。それが実際に必要であるとすれば、試してみることができることがいくつかあります。

まず、一部のエントリが他のエントリよりも一般的に使用されている場合は、それらを別の一般的な単語辞書に保存して、最初に検索することができます。これが価値があるかどうかを確認するには、各ディクショナリ エントリに対してカウンタを保存し、エントリがアクセスされるたびにインクリメントし、長期にわたるテスト期間にわたってこれらのカウンタを調べます。

もう 1 つの価値があるのは、26^3 = 17576 などの固定サイズの辞書の配列です。ここでは、エントリの最初の 3 文字を使用して、検索する辞書を選択します。これにより、3 文字以下の単語の場合は o(1) にドロップされ、残りのエントリの検索時間が大幅に短縮されます。

于 2013-02-23T14:08:24.673 に答える
0

私はおそらくstd::set、イテレータを小さなクラスでラップして無効化をチェックするだけで、ポインタの代わりにイテレータを保持できるようにするでしょう。

時期尚早に最適化しないでください。そのコードをプロファイリングしましたか？これがボトルネックであると100％確信していますか？

于 2013-02-23T13:50:21.710 に答える
0

地図を使用してください。配列/リストを検索する必要はありません。

于 2013-02-23T13:50:24.870 に答える
-1

std::hash_set私が行く方法だと思います

于 2013-02-23T13:52:43.207 に答える