8

C++を使用して単語(std::string)を大文字にする最速の方法は何ですか?

-O3 フラグを指定して g++ 4.6.3 を使用する Debian Linux では、この関数を使用boost::to_lowerすると、AMD Phenom(tm) II X6 1090T プロセッサ (3200 MHz) で実行の単一スレッドで約 24 秒で 81,450,625 ワードが大文字化されます。

void Capitalize( std::string& word )
{
    boost::to_lower( word );
    word[0] = toupper( word[0] );
}

この関数を使用std::transformすると、約 10 秒で同じことが行われます。テストの合間に VM をクリアするので、この違いはまぐれではないと思います。

sync && echo 3 > /proc/sys/vm/drop_caches

void Capitalize( std::string& word )
{
    std::transform(word.begin(), word.end(), word.begin(), ::tolower);
    word[0] = toupper( word[0] );
}

もっと速い方法はありますか？速度のために移植性を失いたくはありませんが、標準 C++ またはブースト付き標準 C++ で動作するより高速な方法がある場合は、それらを試してみたいと思います。

ありがとう。

4

6 に答える 6

5

高速化するいくつかの方法:
1. を使用しないでくださいto_lower。遅いです。s も使用しないifでください。文字から小文字バージョンにマップする 256 エントリのテーブルと、大文字用の別のテーブルを作成します。
2. を使用しないでください。transform最初の文字へのポインターを取得し、null ターミネーターまでループします。
3. メモリに問題がない場合は、2 つの文字シーケンスをマップするテーブルを使用します。この場合、終了を処理する別のテーブルが必要になります。
4. アセンブリでこれを行うことができれば、はるかに高速になります。

于 2012-05-21T17:37:03.387 に答える
2

大文字化が本当にボトルネックである場合は、手書きのサイクルとインラインの toper/tolower 関数を使用して、独自の大文字化の実装を作成してください。必要に応じて ASM を使用してください。

于 2012-05-21T17:16:53.397 に答える
1

g++ -03 Fedora 18 でコンパイルされた std::transform よりも高速であることがわかった実装があります。

パフォーマンス時間 (秒):
変換にかかった時間: 11 秒
私の実装にかかった時間: 2 秒
テスト データ サイズ = 26*15*9999999 文字

inline void tolowerPtr(char *p) ;

inline void tolowerStr(std::string& s)
{char* c=const_cast<char*>(s.c_str());
size_t l = s.size();
  for(char* c2=c;c2<c+l;c2++)tolowerPtr(c2); 
};

inline void tolowerPtr(char *p) 
{
switch(*p)
{
  case 'A':*p='a'; return;
  case 'B':*p='b'; return;
  case 'C':*p='c'; return;
  case 'D':*p='d'; return;
  case 'E':*p='e'; return;
  case 'F':*p='f'; return;
  case 'G':*p='g'; return;
  case 'H':*p='h'; return;
  case 'I':*p='i'; return;
  case 'J':*p='j'; return;
  case 'K':*p='k'; return;
  case 'L':*p='l'; return;
  case 'M':*p='m'; return;
  case 'N':*p='n'; return;
  case 'O':*p='o'; return;
  case 'P':*p='p'; return;
  case 'Q':*p='q'; return;
  case 'R':*p='r'; return;
  case 'S':*p='s'; return;
  case 'T':*p='t'; return;
  case 'U':*p='u'; return;
  case 'V':*p='v'; return;
  case 'W':*p='w'; return;
  case 'X':*p='x'; return;
  case 'Y':*p='y'; return;
  case 'Z':*p='z'; return;
};
return ;
}

void testtransform( std::string& word )
{
std::string word2=word; 
time_t t;
time_t t2;
time(&t);
std::cout << "testtransform: start " << "\n";
int i=0;
for(;i<9999999;i++) 
{    word2=word;
    std::transform(word2.begin(), word2.end(), word2.begin(), ::tolower);
}
time(&t2);
std::cout << word2 << "\n";
std::cout << "testtransform: end " << i << ":"<< t2-t << "\n";
}

void testmytolower( std::string& word )
{
std::string word2=word; 
time_t t;
time_t t2;
time(&t);
std::cout << "testmytolower: start " << "\n";
int i=0;
for(;i<9999999;i++)
{   word2=word;
    cstralgo::tolowerStr(word2);
}
time(&t2);
std::cout << word2 << "\n";
std::cout << "testmytolower: end " << i << ":"<< t2-t << "\n";
}

int main(int argc, char* argv[])
{
   std::string word ="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
   word =word+word+word+word+word+word+word+word+word+word+word+word+word+word+word;
   testtransform( word);
   testmytolower( word);
   return 0;
}

パフォーマンスをさらに改善できるかどうかを知りたいです。

于 2013-04-09T16:57:04.827 に答える
-1

必要な疑似コードは次のとおりです。 




for(int i=0 to given_str.length)

{ upper[i]=(char*)given_str[i]-32;  // in ascii tbl, any lower case char - upper case char=32

}

return upper;

于 2012-10-03T09:17:58.580 に答える