最初の質問は、std::string::erase再割り当てしますか?
2 番目の質問です。特定の単語や語句を .NET ファイルからすばやく消去するためのより高速な方法はありますstd::stringか? 文字列の長さは通常約 300K です。
質問する
2328 次
7 に答える
4
21.4.1/3
erase() または pop_back() メンバー関数は例外をスローしません。
アロケータにはそのような制限が存在しないため、再割り当てを行わない、行わない、または行うことができないと言っても過言ではないと思いますstd::string::erase。
于 2013-02-20T07:57:11.150 に答える
2
std :: string::eraseが再割り当てをトリガーするかどうかは実装に依存することはすでに述べました。だから私は文字列検索に集中したかったのです。この問題に対する従来のアプローチは、Aho-Corasickアルゴリズムを使用することです。
あるいは、David Musserは、Boyer-MooreアルゴリズムとKnuth-Morris-Prattアルゴリズムのハイブリッドを使用して、大きな干し草の山（文字列）で針（部分文字列）を検索することに関する論文を書きました。論文はこちらから入手できます。これを適応させることは、おそらくAho-Corasick実装をロールするよりも簡単でしょう。
Musserのアプローチの展示は、素朴な検索と置換よりも高速な動作である必要があります。BMスキップループとKNPルックアップテーブルを変更して、交換しようとしているすべての針を考慮に入れることで、アルゴリズムを目的に合わせて調整できるはずです。事前に出力バッファを割り当て、干し草の山の一致しないすべてのセグメントを追加することにより、出力文字列を繰り返し作成します。このアプローチは、針の数が増え、BM / KNPルックアップが飽和するにつれて、効果が低下します。
于 2013-02-20T08:00:01.507 に答える
1
- いいえ、
std::string::erase再割り当てしません。再割り当てする必要がなく、必要のないものに対して (再割り当て時間) を支払わないのが C++ の哲学であるためです。 - 何を消去したいか、および何を意味するかによって異なります (すばやく入力するか実行するか)。
最初に行うことは、もちろん、削除したい単語/フレーズを見つけるための高速なアルゴリズムを見つけることです. 次に、消去するチャンクが 1 つしかない場合std::string::eraseは、ニーズに完全に適合するはずです。ただし、たとえば、文字列「000aa11111bbbbb2222222c3333333333」があり、文字を含むすべてのフレーズを消去したい場合、それらを次々と見つけて消去すると、文字列の残りの複数のコピーが作成されます。「1」は 1 回コピーされます。 2 は 2 回コピーされます。したがって、文字列に消去するフレーズが多数ある場合、パフォーマンスを向上させる可能性があります。文字列に残す必要があるチャンクを個別にコピーし、消去するチャンクを上書きするだけです: (| は、文字列が正しい"）：
- "000|aa11111bbbbb2222222c3333333333"
- "00011111|11bbbbb2222222c3333333333"
- "000111112222222|2222222c3333333333"
- "000111112222222333333333|33333333"
- "000111112222222333333333"
そうすれば、最初に消去されたフレーズの後のすべての文字を 1 回だけコピーする必要があります。
于 2013-02-20T07:59:44.947 に答える
0
MS の VC6 を使用しており、この最後の DO は std::string::erase() 呼び出しでバッファーを再割り当てします。時々大きな文字列を使用しているため、コードからすべての erase() 呼び出しを削除する必要があり、これにより大きな速度低下が見られました。したがって、コンパイラに注意して、erase() を避けてください。個人的に、私は reaffectations str = ""; を使用します。回避策として。
于 2013-09-02T09:17:54.080 に答える