1

char buf[12];左側にスペースが埋め込まれた右詰めの符号なし数字が常にあることがわかっている があるとします。たとえば、_________329( は_スペースを表します)。私がそれを解析することを考えることができる最速の方法は、次のようなものです:

while (*buf == ' ') buf++;
atoi(buf);

しかし、特に想定していないatoi署名されていないことがわかっている場合は、より高速な方法があるかどうか疑問に思っていました..atoi

4

3 に答える 3

6

最初の文字は「潜在的な兆候」のために予約されており、常に「スペース」であると思いますか? char[11]そうしないと、 の代わりにのみが必要になるためchar[12]です。とにかく、固定サイズは手動ループ展開を可能にします:

unsigned parse(const char(&b)[12])
{
    return ((((((((((b[1] & 15))
             * 10 + (b[2] & 15))
             * 10 + (b[3] & 15))
             * 10 + (b[4] & 15))
             * 10 + (b[5] & 15))
             * 10 + (b[6] & 15))
             * 10 + (b[7] & 15))
             * 10 + (b[8] & 15))
             * 10 + (b[9] & 15))
             * 10 + (b[10]& 15);
}

この& 15トリックはスペースとゼロを同じように扱い、ASCII (スペース = 32、ゼロ = 48) と EBCDIC (スペース = 48、ゼロ = 240) の両方で機能することに注意してください。私はまだ他の文字エンコーディングをチェックアウトしていません:)

これは実際に より速いですか、それとも遅いですatoiか? それを知る唯一の方法は、測定することです。atoiしかし、標準関数を使用すると常に可読性が向上するため、私はおそらくそのまま使用します。

于 2012-07-13T21:46:08.670 に答える
1

まず、なぜこれを行っているのかを自問してください。「buf」が非常に長いファイルである場合、 Schmiel the Painter アルゴリズムに苦しむ可能性があり、10 進数の桁数が非常に多い場合、たとえば . GMP (符号付き整数演算については mpz セクションを参照)

次に、標準ライブラリが知らないことを知っていることを検討してください。 Dmitry は'fast platform-optimized ' を使用することを提案してstrrchrいますが、文字列を繰り返し処理する問題を回避するために strrchr でできることは何もなく、strrchr実際には終端の null 文字を検索するなどの追加の制約があります。

次のようなことを知っているかもしれません。

  • 数値が負になることはありません。つまり、atoi は先頭の +/- 記号を取得する必要はありません。これは正しく指摘されていますが、これはおそらくタイミングの主要な要因ではありません。
  • 数字はほとんどが短いか、ほとんどが長いため、文字列の先頭と末尾のどちらでスペースを探し始めるかが決まります。特に、strrchr文字列の長さがわからないため、常に最初から読み取ります。これはatoi、私が見ている実装 (Newlib) と同様です。サンプルコードは、文字列の先頭からの検索も意味します。
  • 数値は常に 10 進数になります。これにより、数学が少し省略されます。
  • あなたの数字は常にunsigned longに収まります。はい、これは 12 文字なので保証されていますが、atoi はこれを認識しておらず、何らかのエラー処理を試みます。また、atoi()符号付き整数を返すため、1,000,000,000 のような 13 ビットの数値が必要になった場合に対処する必要があります。
  • 私が考えていなかった他の何か; しかし、あなたはそうかもしれません。

ソースを読むことから始めるべきです。この簡単なエクササイズから、非常に多くのことが得られます。私は最近Newlibを使用しており、それをダウンロードして開いているので、それを参照しますが、GNU のglibcと Windows が使用するものはおそらく異なるでしょう。

一見すると、単純な最適化が見られます。これatoiは単に , または 'string to long' を呼び出すだけですstrtol(私のプラットフォームでは int と long はどちらも 32 ビットです。より大きなものを得るには 'long long' が必要です)。コンパイラはおそらくそれを直接呼び出しに最適化しますが、サイクルを節約できる可能性があります。表向きは速度に敏感なアプリケーションの場合は、すぐに strtol() を呼び出してください。むしろ、strtoul「string to unsigned long」を呼び出します。それがあなたがしていることだからです。他に注目すべきものを何も呼び出さない関数ができたので、それを見てみましょう。今のところ、再入可能なものは無視してください。ブラケットに注意してください。一部の if にはブラケットがあり、関連する else にはブラケットがありません (これはスタイルの悪い IMO です。私はどこでもブラケットを好みます)。

unsigned long _strtoul_r
    (struct _reent *rptr, _CONST char *nptr, char **endptr, int base)
{
  register const unsigned char *s = (const unsigned char *)nptr;
  register unsigned long acc;
  register int c;
  register unsigned long cutoff;
  register int neg = 0, any, cutlim;

  /*
   * See strtol for comments as to the logic used.
   */
  do {
    c = *s++;
  } while (isspace(c));
  if (c == '-') {
    neg = 1;
    c = *s++;
  } else if (c == '+')
    c = *s++;
    if ((base == 0 || base == 16) &&
    c == '0' && (*s == 'x' || *s == 'X')) {
    c = s[1];
    s += 2;
    base = 16;
  }
  if (base == 0)
    base = c == '0' ? 8 : 10;
  cutoff = (unsigned long)ULONG_MAX / (unsigned long)base;
  cutlim = (unsigned long)ULONG_MAX % (unsigned long)base;
  for (acc = 0, any = 0;; c = *s++) {
    if (isdigit(c))
      c -= '0';
    else if (isalpha(c))
      c -= isupper(c) ? 'A' - 10 : 'a' - 10;
    else
      break;
    if (c >= base)
      break;
    if (any < 0 || acc > cutoff || (acc == cutoff && c > cutlim))
    any = -1;
    else {
      any = 1;
      acc *= base;
      acc += c;
    }
  }
  if (any < 0) {
    acc = ULONG_MAX;
    rptr->_errno = ERANGE;
  } else if (neg)
    acc = -acc;
  if (endptr != 0)
    *endptr = (char *) (any ? (char *)s - 1 : nptr);
  return (acc);
}

関数の定義から始めて、アプリケーションがシングルスレッドの場合、取り除くことができる再入可能性の問題があることに気付きます。char **ptr 引数もあります。これは、必要のない、解析された数値の後の文字列へのポインターを格納します。長さの定義もないため、文字列の長さを見つけるにはヌル文字を検索する必要があります。

このアプリケーションでは、*s はレジスタとして定義されています。これは私のプラットフォームでは意味がありますが、あなたのプラットフォームでは意味がないかもしれません。必要のない他の整数もいくつか定義されています。

do/while ループにisspace()は、スペース、水平タブ、改行、垂直タブ、フィード、およびキャリッジ リターン文字をチェックする呼び出しがあります。必要なのはスペースだけです。また、弦の前から始まり、後ろに向かって動作します。主に小さな数字がある場合は、それを変更してください。

次に、いくつかの基本的なテストを行います。基数は 0 にすることができ、基数の自動検出 (サイクルが必要) を可能にし、それが 8 または 16 の場合は、先頭の '0' または先頭の '0x' を許容しますが、これを知る必要もテストする必要もありません。

次に、'cutoff' 変数と 'cutlim' 変数を作成します。表向きは範囲チェックが必要ないため、これらは必要ありません。

最後に、最後の for ループに到達します。isdigit、isalpha、関数で文字の種類と数値を決定する if\else if\else ブロックがありisupperます。これらには、見かけ上のロケール依存コードが組み込まれています。if/else if/else ブロック全体を単一のc -= 0ステートメントに置き換える 10 進数値を想定できるようです。

次に、安価で保持するのに適したエラー チェックがいくつかありますif (c >= base)。C は符号なしであることを思い出してください。たとえば、*s がスペース (0x20) ('0', 0x30 より小さい) の場合、これは (unsigned)(0x30 - 0x20) = 255 - 10 と評価されます。基数 (10) より大きい。完璧ではありませんが、かなり良く、非常に安価です。

次に、ブロック内でいくつかの境界チェックがif (any...あり、関数の実際の内容に到達しますacc *= base; acc += c;。これを最適化するためにできることはほとんどありませんが、バイナリベースがあれば、これをシフトに変換できます。プロセッサに高速なハードウェア乗算器があることを願っています。これが Arduino ISR の場合、問題が発生します。積和などの DSP アセンブリ命令を調べて、これを高速化することをお勧めします。

for ループの後に、無視できるエラー処理と負の数の処理があります。

したがって、要約すると、頻繁に実行している場合は、特殊なケースを処理する新しい関数を作成します。

unsigned long TwelveCharDecimalStringWithLeadingSpacestoul(char *nptr)
{
    register const unsigned char *s = (const unsigned char *)nptr;
    register unsigned long acc;
    register int c, base = 10;

  do {
    c = *s++;
  } while (c == ' ');

  for (acc = 0;; c = *s++) {
    c -= '0';
    if (c >= base) {
      _errno = ERANGE;
      acc = -1;
      break;
    }
    acc *= base;
    acc += c;
  }
  return (acc);
}

の一般性を取り除きatoi、少し高速にするために行った仮定を使用します。ただし、この操作が非常に頻繁に行われるか、非常に高速に行われる必要がある場合を除き、おそらく、はるかに単純で、明確で、安全で、柔軟性があり、一般的に優れている方がよいでしょう。

unsigned long result = 0;
char *begin = strrchr(buf, ' ');
result = strtoul(buf, NULL, 10);

if (result == 0 && errno == ERANGE)
   // Handle error

編集: 書き終えて、FredOverflow がより良い回答を投稿したことに気付きました。ループをアンロールし (私はそれをしませんでした。必要ではないように思われましたが、必要に応じて既知の期間のループをアンロールできます)、 で巧妙なトリックを実行し& 15ます。ただし、上記の関数は、一般的なケースで一部の標準ライブラリ呼び出しを高速化するという問題に対処する方法を示す良いデモンストレーションです。

于 2012-07-13T22:37:55.480 に答える
0

このコードはより高速になる可能性があります。

char *begin = strrchr(buf, ' ');
atoi(begin ? begin : buf);

プラットフォームに最適化された高速な標準関数 strrchr を想定しています。

于 2012-07-13T20:25:11.867 に答える