7

我正在使用scanf("%d", &someint). 因为我想看看 scanf 是否是一个瓶颈，所以我使用 实现了一个简单的整数解析函数fread，就像：

int result;
char c;

while (fread(&c, sizeof c, 1, stdin), c == ' ' || c == '\n')
    ;

result = c - '0';
while (fread(&c, sizeof c, 1, stdin), c >= '0' || c <= '9') {
     result *= 10;
     result += c - '0';
}

return result;

但令我惊讶的是，这个函数的性能（即使有内联）大约差了 50%。不应该有可能改进 scanf 的特殊情况吗？不fread应该很快（附加提示：整数是（编辑：大部分）1或2位数字）？

4

4 回答 4

8

我遇到的开销不是解析本身，而是许多调用fread（与fgetc, 和朋友相同）。对于每次调用，libc 必须锁定输入流以确保两个线程不会踩到对方的脚。锁定是一项非常昂贵的操作。

我们正在寻找的是一个为我们提供缓冲输入的函数（重新实现缓冲实在是太费力了），但又能避免fgetc.

如果我们可以保证只有一个线程在使用输入流，我们可以使用 中的函数unlocked_stdio(3)，例如getchar_unlocked(3)。这是一个例子：

static int parseint(void)
{
    int c, n;

    n = getchar_unlocked() - '0';
    while (isdigit((c = getchar_unlocked())))
        n = 10*n + c-'0';

    return n;
}

上述版本不检查错误。但它保证会终止。如果需要进行错误处理，最后检查一下就足够feof(stdin)了ferror(stdin)，或者让调用者去做。

我最初的目的是在 SPOJ 提交编程问题的解决方案，其中输入只有空格和数字。所以还有改进的余地，即isdigit检查。

static int parseint(void)
{
    int c, n;

    n = getchar_unlocked() - '0';
    while ((c = getchar_unlocked()) >= '0')
        n = 10*n + c-'0';

    return n;
}

无论是在性能方面，还是在便利性和可维护性方面，都很难超越这个解析例程。

于 2015-01-17T12:35:41.423 回答
4

您将能够通过缓冲显着改进您的示例 - 将大量字符读入内存，然后从内存版本中解析它们。

如果您从磁盘读取数据，您的缓冲区可能会提高性能，因为您的缓冲区是块大小的倍数。

编辑：您可以让内核通过使用mmap将文件映射到内存来为您处理这个问题。

于 2011-12-12T23:51:48.650 回答
1

这是我使用的东西。

 #define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
 char _;

但是，这只适用于整数。

于 2015-01-17T01:45:37.987 回答
-2

根据你的说法，我得出以下事实：

  • 数字在 0-99 范围内，占 10+100 个不同的字符串（包括前导零）
  • 您相信您的输入流符合某种规范并且不会包含任何意外的字符序列

在这种情况下，我会使用查找表将字符串转换为数字。给定一个字符串 s[2]，查找表的索引可以通过s[1]*10 + s[0]、交换数字并利用ASCII中'\0'等于的事实来计算。0

然后，您可以通过以下方式读取您的输入：

// given our lookup method, this table may need padding entries
int lookup_table[] = { /*...*/ };

// no need to call superfluous functions
#define str2int(x) (lookup_table[(x)[1]*10 + (x)[0]])

while(read_token_from_stream(stdin, buf))
        next_int = str2int(buf);

在今天的机器上，很难想出更快的技术。我的猜测是，这种方法的运行速度可能比任何scanf()基于方法的方法快 2 到 10 倍。

于 2011-12-13T00:37:15.813 回答