在一个字符串中计算一个字符出现的次数的最有效方法

Question

我正在编写一个非常简单的函数，以计算在给定字符串中特定字符出现的次数。我已经有了一个可行的函数，但是想知道是否有更有效或更优先的方法来完成这个任务。

以下是函数代码:

size_t strchroc(const char *str, const char ch)
{ 
    int c = 0, i = 0;

    while(str[i]) if(str[i++] == ch) c++;
    return c;
}

我个人无法想到任何让这段代码更加高效的方法。只是为了学习，不知道是否有人知道如何使此函数更加高效（在速度和资源使用上都更少的情况下）。

- Keith Miller

---

除非您能保证字符串已排序，否则这是您可以做的最好的事情。它是一个线性算法，在恒定空间中运行。 - FrankieTheKneeMan

根据您方法的声明，c和i的类型应为size_t。 - Pierre

以 str 开头，后跟一个字母的函数名称被保留供标准库（未来）使用。http://www.gnu.org/software/libc/manual/html_node/Reserved-Names.html - wildplasser

这是否是一个热点？如果不是，就没必要关心。如果是的话，你可以通过找到一种方法尽量不经常调用它（例如，进行单次通行以计算所有你感兴趣的字符，缓存结果，并更改需要了解这些计数的任何内容）来获得更高的性能。 - user395760

@KeithMiller，不仅仅是函数名称，而是外部标识符。 - eq-

Answer 1

首先，除非你的函数真的需要严格控制时间，否则不要试图过度优化。只需使用提供的代码，因为它很容易验证正确性，而且不会试图仅仅为了好玩而变得聪明。

如果函数确实需要非常高的速度，则有许多方法可以进一步优化它。实际上有非常多种方法。其中一些方法期望或假定您拥有特定的字符串内存布局（例如，它们在字边界上分配，并且分配也总是填充到字边界）。因此，您需要小心，因为该算法可能适用于某些处理器、编译器和内存分配器的组合，但在其他情况下可能失败。

仅仅是为了好玩，我列出了一些可能加速字符计数的方法：

• 每次读取一个单词（32或64位整数）的字符串。由于L1缓存和乱序预计算执行，这不一定有太大帮助。这需要对最后一个单词进行环路结束调整，以避免误计算空终止符后面的字节。只能用于字对齐和填充的内存分配器。
• 移除条件语句，改为计算所有字符的计数（到一个数组中），并返回所需字符的计数。（这将删除条件语句，如果您事先知道字符串长度，则可以进行循环展开，这样不仅可以减少条件分支，而且可以进行优秀的循环展开）。
• 如果您在其他地方已经计算出字符串的长度，则可以使用它来展开循环。或者更好的是，将其编写为for循环，并应用适当的#pragma和编译器选项，让编译器为您执行循环展开。
• 使用汇编语言编写程序。在这种情况下，先打开所有编译器优化，然后再反汇编程序——你很可能会发现编译器已经使用了所有你知道和未知的潜在技巧。
• 如果您的字符串可能非常大（兆字节级别），这里我有一些猜测——通过OpenCL/CUDA使用显卡可能会提供一些潜力。

等等。

但是，如果你面对的是一个真实世界中的问题，我真的、真的建议你坚持你所拥有的函数。如果这只是一个玩具问题，并且您正在进行优化以便于学习，那么请继续。微调是学习CPU和指令集的有趣方式，但对于99.999999...%的编程任务来说，它不值得这样做。

- Santeri Paavolainen

---

很棒的回答，但实际上我正在尝试学习CPU和指令集。谢谢你的回答。 - Keith Miller

Answer 2

您可以使用指针来迭代字符串，并稍加努力，每个字符仅使用一次*：

size_t strchroc(const char *str, const char ch)
{ 
    size_t c = 0;
    char n;
    while ((n=*str++), ((n==ch)? ++c : 0), n)
        ;
    return c;
}

并不是编译器不能将您的代码优化为完全相同的代码，只是为了好玩。

- rodrigo

---

今年（我看到的）第一个在for循环之外使用逗号运算符的人。哇！！！ - jn1kk

Answer 3

在使用函数之前，应该使用strchr()（如果你知道长度，也可以使用memchr()）进行匹配。如果有匹配，你可以从第一个匹配字符的位置开始，然后从那里继续。

除非你的字符串非常短或者匹配非常早，否则这样做应该会更快。

- Bragi Acculum

Answer 4

你可以摆脱变量 i。

size_t strchroc(const char *str, const char ch){ 
    size_t c = 0;
    while(*str != '\0') {
        if(*str == ch) c++;
        str++;
    }
    return c;
}

- hackattack

Answer 5

size_t count_the_string(const char *str, const char ch){
    size_t cnt ;
    for(cnt=0; *str; ) {
        cnt += *str++ == ch;
    }
    return cnt;
}

对于等效的do { ...} while();变体，GCC生成的代码没有条件跳转（当然除了循环的跳转），与@hakattack的解决方案相当。

size_t count_the_string2(const char *str, const char ch){
    size_t cnt=0 ;
    do {
        cnt += *str == ch;
    } while (*str++);
    return cnt;
}

- wildplasser

Answer 6

在进行了一次快速的低质量基准测试后，我得出了对于任意长度字符串的以下结果。

在大型字符串（100M+）上，它并没有显示出太大的差异，但在较短的字符串（句子、普通文本文件等）上，改进约为25%。

unsigned int countc_r(char *buf, char c)
{
    unsigned int k = 0;

    for (;;) {
        if (!buf[0]) break;
        if ( buf[0] == c) ++k;
        if (!buf[1]) break;
        if ( buf[1] == c) ++k;
        if (!buf[2]) break;
        if ( buf[2] == c) ++k;
        if (!buf[3]) break;
        if ( buf[3] == c) ++k;
        buf += 4;
    }

    return k;
}

- Runium