30

タイトルの通り、atoi以上の性能を発揮できるものを探しています。現在、私が知っている最速の方法は

atoi(mystring.c_str())

最後に、Boost に依存しないソリューションを希望します。これを行うための優れたパフォーマンスの秘訣はありますか?

追加情報: int は 20 億を超えることはなく、常に正であり、文字列に小数点以下の桁数はありません。

4

10 に答える 10

36

ルックアップ テーブルを使用したソリューションを試してみましたが、問題が多く、実際にはそれほど高速ではありませんでした。最速のソリューションは、想像力に欠けるものであることが判明しました。

int fast_atoi( const char * str )
{
    int val = 0;
    while( *str ) {
        val = val*10 + (*str++ - '0');
    }
    return val;
}

ランダムに生成された 100 万個の文字列を使用してベンチマークを実行します。

fast_atoi : 0.0097 seconds
atoi      : 0.0414 seconds

公平を期すために、コンパイラにインライン化させないようにして、この関数もテストしました。結果はまだ良好でした：

fast_atoi : 0.0104 seconds
atoi      : 0.0426 seconds

データがfast_atoi関数の要件に準拠していれば、かなり妥当なパフォーマンスです。要件は次のとおりです。

  1. 入力文字列に数字のみが含まれているか、空です
  2. 入力文字列は 0 から最大までの数値を表しますINT_MAX
于 2013-05-30T02:15:23.250 に答える
15

このページでは、さまざまなコンパイラを使用したさまざまな string->int 関数間の変換速度を比較します。提示された結果によると、エラー チェックを行わない単純な関数は、atoi() の約 2 倍の速度を提供します。

// Taken from http://tinodidriksen.com/uploads/code/cpp/speed-string-to-int.cpp
int naive(const char *p) {
    int x = 0;
    bool neg = false;
    if (*p == '-') {
        neg = true;
        ++p;
    }
    while (*p >= '0' && *p <= '9') {
        x = (x*10) + (*p - '0');
        ++p;
    }
    if (neg) {
        x = -x;
    }
    return x;
}

それは常にポジティブです

マイクロ最適化のために、上記のコードのネガティブ チェックを削除します。

文字列に数字以外が含まれないことを保証できる場合は、ループを変更してさらにマイクロ最適化できます

while (*p >= '0' && *p <= '9') {

に

while (*p != '\0' ) {

あなたに残すもの

unsigned int naive(const char *p) {
    unsigned int x = 0;
    while (*p != '\0') {
        x = (x*10) + (*p - '0');
        ++p;
    }
    return x;
}
于 2013-05-30T01:34:51.053 に答える
2

gcc の atoi 関数の全体を次に示します。

long atoi(const char *str)
{
    long num = 0;
    int neg = 0;
    while (isspace(*str)) str++;
    if (*str == '-')
    {
        neg=1;
        str++;
    }
    while (isdigit(*str))
    {
        num = 10*num + (*str - '0');
        str++;
    }
    if (neg)
        num = -num;
    return num;
 }

あなたの場合、空白と否定的なチェックは不要ですが、ナノ秒のみを使用します。

isdigit はほぼ確実にインライン化されるため、時間はかかりません。

ここは本当に改善の余地がありません。

于 2013-05-30T04:13:09.363 に答える
0

唯一の決定的な答えは、実際のデータであるコンパイラをチェックすることです。

私が試してみたいこと（メモリアクセスを使用していても、キャッシュによっては遅くなる可能性があります）は

int value = t1[s[n-1]];
if (n > 1) value += t10[s[n-2]]; else return value;
if (n > 2) value += t100[s[n-3]]; else return value;
if (n > 3) value += t1000[s[n-4]]; else return value;
... continuing for how many digits you need to handle ...

ift1などt10は静的に割り当てられ、一定である場合、コンパイラはエイリアシングを恐れず、生成されるマシン コードは非常にまともなものになるはずです。

于 2013-05-30T08:07:49.567 に答える
-1

これが私のものです。Atoi は私が思いつくことができる最速です。msvc 2010 でコンパイルしたので、両方のテンプレートを組み合わせることができるかもしれません。msvc 2010 では、テンプレートを組み合わせると、cb 引数を指定すると遅くなります。

Atoi はほぼすべての特殊な atoi ケースを処理し、これと同じかそれ以上の速さです。

int val = 0;
while( *str ) 
    val = val*10 + (*str++ - '0');

コードは次のとおりです。

#define EQ1(a,a1) (BYTE(a) == BYTE(a1))
#define EQ1(a,a1,a2) (BYTE(a) == BYTE(a1) && EQ1(a,a2))
#define EQ1(a,a1,a2,a3) (BYTE(a) == BYTE(a1) && EQ1(a,a2,a3))

// Atoi is 4x faster than atoi.  There is also an overload that takes a cb argument.
template <typename T> 
T Atoi(LPCSTR sz) {
    T n = 0;
    bool fNeg = false;  // for unsigned T, this is removed by optimizer
    const BYTE* p = (const BYTE*)sz;
    BYTE ch;
    // test for most exceptions in the leading chars.  Most of the time
    // this test is skipped.  Note we skip over leading zeros to avoid the 
    // useless math in the second loop.  We expect leading 0 to be the most 
    // likely case, so we test it first, however the cpu might reorder that.
    for ( ; (ch=*p-'1') >= 9 ; ++p) { // unsigned trick for range compare
      // ignore leading 0's, spaces, and '+'
      if (EQ1(ch, '0'-'1', ' '-'1', '+'-'1'))
        continue;
      // for unsigned T this is removed by optimizer
      if (!((T)-1 > 0) && ch==BYTE('-'-'1')) {
        fNeg = !fNeg;
        continue;
      }
      // atoi ignores these.  Remove this code for a small perf increase.
      if (BYTE(*p-9) > 4)  // \t, \n, 11, 12, \r. unsigned trick for range compare
        break;
    }
    // deal with rest of digits, stop loop on non digit.
    for ( ; (ch=*p-'0') <= 9 ; ++p) // unsigned trick for range compare
      n = n*10 + ch; 
    // for unsigned T, (fNeg) test is removed by optimizer
    return (fNeg) ? -n : n;
}

// you could go with a single template that took a cb argument, but I could not
// get the optimizer to create good code when both the cb and !cb case were combined.
// above code contains the comments.
template <typename T>
T Atoi(LPCSTR sz, BYTE cb) {
    T n = 0;
    bool fNeg = false; 
    const BYTE* p = (const BYTE*)sz;
    const BYTE* p1 = p + cb;
    BYTE ch;
    for ( ; p<p1 && (ch=*p-'1') >= 9 ; ++p) {
      if (EQ1(ch,BYTE('0'-'1'),BYTE(' '-'1'),BYTE('+'-'1')))
        continue;
      if (!((T)-1 > 0) && ch == BYTE('-'-'1')) {
        fNeg = !fNeg;
        continue;
      }
      if (BYTE(*p-9) > 4)  // \t, \n, 11, 12, \r
        break;
    }
    for ( ; p<p1 && (ch=*p-'0') <= 9 ; ++p)
      n = n*10 + ch; 
    return (fNeg) ? -n : n;
}
于 2014-05-19T17:37:17.113 に答える