1

假设我有一个char buf[12];我知道在左边用空格填充的右对齐无符号数字。因此，例如：（_________329代表_空间的地方）。我能想到的最快的解析方法是这样的：

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

但我想知道是否有更快的方法，特别是atoi考虑到我们知道它是无符号的，atoi它不假设..

4

3 回答 3

6

我假设第一个字符是为“潜在标志”保留的，并且总是“空格”？因为否则，您只需要 achar[11]而不是 a 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 algorithm，如果你有很多十进制数字，你可能会在使用例如乘以一个大数字时遇到问题。GMP（有关有符号整数运算，请参阅 mpz 部分）

其次，考虑您知道标准库不知道的内容。 Dmitry 建议使用 'fast platform-optimized strrchr，但 strrchr 无法解决遍历字符串的问题，strrchr实际上还有其他约束，例如搜索终止的空字符。

你可能知道一些事情，比如：

  • 你的数字永远不会是负数；即 atoi 不需要选择前导 +/- 符号。您已经正确地注意到了这一点，但是，这可能不是时间的主要因素。
  • 您的数字将大多是短的或大部分是长的，这将决定您是否应该开始在字符串的开头或结尾寻找空格。值得注意的是，strrchr不知道字符串的长度，因此总是从头开始读取atoi，我正在查看的实现（在 Newlib 中）也是如此。您的示例代码还暗示从字符串的开头进行搜索。
  • 您的数字将始终以 10 为底。这消除了一些数学问题。
  • 您的数字将始终适合无符号长。是的，这是有保证的，因为它们是 12 个字符，但是 atoi 不知道这一点，并且会尝试处理错误。此外，atoi()返回一个有符号整数，因此如果您需要 1,000,000,000 之类的 13 位数字，则需要解决这个问题。
  • 其他我没有想到的东西；但你可能会。

您应该从阅读源代码开始。从这个简单的练习中可以获得很多东西！我最近一直在使用Newlib并已下载并打开它，这就是我将参考的内容，但 GNU 的glibc和任何 Windows 使用的可能会有所不同。

乍一看，我看到了一个简单的优化：atoi只是对 的调用strtol，或“字符串到 long”（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有一个 if\else if\else 块，它用、isalpha和isupper函数确定字符类型和数值。这些包含一些与语言环境相关的漂亮代码；看来我们可以假设十进制值用单个c -= 0语句替换整个 if/else if/else 块。

接下来，还有一些错误检查，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);

假设快速平台优化标准函数 strrcr。

于 2012-07-13T20:25:11.867 回答