15

文字列があり、特定の文字 ('|' など) が存在するかどうかを調べたいとします。これを行うための最善かつ最速の手法は何ですか? string find の実装は知っています。これよりもさらに高速な実装を求めています。

4

7 に答える 7

35

使用するstd::string::find

if (str.find('|') != std::string::npos)
{
    // ...
}

これ以上効率的なものはありそうにありません。O（n）はあなたができる最善の方法です。標準ライブラリの実装はかなり最適なはずです。

于 2012-12-25T06:42:46.337 に答える
2

このソースから、Visual Studio 2013 Compiler で行われた経験的テストは、strchrルーチンがstd::string::find実装よりも約2 倍高速であることを示しています。

于 2014-12-28T18:22:56.033 に答える
1

Tom Tanner の回答を追加します。アプリオリな計算を行いたくない場合は、O(n) で行き詰まるでしょう。つまり、検索する文字列の長さと消費時間の間に線形相関があります。Tom は、特定の文字が発生したかどうかを示すブール値の配列 (またはベクトル) を設定することを提案しました。文字列にインデックスを付けるには O(n) が 1 回必要ですが、O(1) が含まれている場合は、任意の数の文字を O(1) (定数時間) で確認できます。このアプローチの欠点は、大量のメモリが必要になることです (Unicode をサポートする必要があると判断した場合)。

妥協案として、入力文字列に実際に存在する文字のみを格納する std::set などを使用できます。メモリ消費は、文字列内の異なる文字の数に関してほぼ線形になりますが、ルックアップは O(log n)、つまり対数になります。

もちろん、測定/プロファイリングしてから、実際に最適化しているユースケースをここで説明する必要があります。それまでは、理解しやすく読みやすいものに固執してください。

于 2014-12-06T13:07:44.567 に答える
1

もう 1 つの方法は、対応する c_str 文字列に対して strchr 関数を使用することです。

if(strchr(str.c_str(), '|'))
{
    \\found
}

ただし、速度の点で std find と比較する方法がわからない...

見つかった文字の位置は

size_t pos = strchr(str.c_str(),'|') - str.c_str();
于 2013-11-26T18:15:59.710 に答える
0

これを試すことができます：

   string s1 = "Hello";
   string s2 = "el";
   if(strstr(s1.c_str(),s2.c_str()))
   {
    cout << " S1 Contains S2";
   }
于 2015-06-02T14:04:24.370 に答える
0

これを行う方法は 1 つだけです。文字列を繰り返し処理して、探している文字が存在するかどうかを確認します。string::findこれを行うには、文字を取得して文字列内の最初の位置を返す関数を使用するstring::nposか、値が存在しない場合に行います。を使用することもできますstd::find。これは、2 つのイテレータbeginとendキー値 'k' を取得し、範囲内で最初に出現した k を指すイテレータを返し[begin, end]ます。もちろん、次のように自分で find 関数を実装することもできます。endk

string::size_type pos=string::npos;
for(string::size_type i=0; i<s.size(); ++i) {
  if(s[i] == key) {
     pos=i;
     break;
  }
}
if(pos != string::npos) {
  // key was found
} else {
  // not found
}

またはこれ：

string::iterator pos=s.end();
for(string::iterator i=s.begin(); i!=s.end(); ++i) {
  if(*i == key) {
    pos=i;
    break;
  }
}
if(pos != s.end()) {
  // found
} else {
  // not found
}

std::string::findとの詳細std::find:

于 2012-12-25T08:05:56.760 に答える
0

string::find よりも高速なものが必要であるというステートメントを考えると、私が考えることができる唯一のことは、文字列の更新ごとに最初の位置を含む内部テーブルを更新する、高度にカスタマイズされた代入演算子を持つクラスを作成することです可能なすべての文字の文字列 (char 文字列の場合は 256、ワイド文字列の場合は 65536(?))。これには O(1) ルックアップがありますが、const 以外の操作にかなりの複雑さが追加されます。

于 2012-12-25T09:49:58.253 に答える