3

我正在编写一个非常简单的函数，它计算某个字符在给定字符串中出现的次数。我有一个工作功能，但想知道是否有更有效或更优选的方法来执行此操作。

这是功能：

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

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

我个人想不出任何方法来提高这段代码的效率。并且想知道（只是为了学习）是否有人知道使此功能更有效的方法。

（在速度和使用最少资源的意义上是高效的）。

4

6 回答 6

5

首先，除非你的函数真的对时间敏感，否则不要试图过度优化。只需使用您提供的那个，因为它很容易验证正确性，并且它不会仅仅为了它而变得聪明。

如果该功能确实需要快速，那么有很多方法可以对其进行更多优化。很多，真的很多方法。其中一些要么期望或假设您拥有的字符串的特定内存布局（例如，它们被分配在字边界上，并且分配也总是填充到字边界）。所以你需要小心，因为该算法可能适用于处理器、编译器和内存分配器的某种组合，而在其他方面可能会失败。

只是为了它，我将列出一些加速字符计数器的可能方法：

  • 一次读取字符串一个单词（32 位或 64 位整数）。由于 L1 缓存和推测/无序执行，不一定有很大帮助。这需要对最后一个字进行循环结束调整（NUL 终止符后的字节数错误）。仅与字对齐和填充内存分配器一起使用。
  • 删除条件，而是计算所有字符的计数（到数组）并返回所需字符的计数。（这将删除条件，如果您事先知道字符串长度，它可以实现出色的循环展开，并删除一个条件分支点。）
  • 如果您事先知道字符串的长度（在其他地方计算），您可以使用它来展开循环。或者更好的是，将其编写为 for 循环并应用合适的 #pragma 和编译器选项，以使编译器为您执行循环展开。
  • 用汇编程序编写例程。在走这条路之前，先启动所有编译器优化并反汇编例程——你可能会发现编译器已经使用了你知道的所有潜在技巧，还有一些你没有使用。
  • 如果您的字符串可能非常大（兆字节）——我在这里推测——通过 OpenCL/CUDA 使用显卡可能会提供一些潜力。

等等。

但是，如果您遇到实际问题，我真的非常建议您坚持使用现有的解决方案。如果这是一个玩具问题，并且您正在优化它的乐趣，请继续。

循环剃须是学习 CPU 和指令集的一种有趣方式，但对于 99.999999...% 的编程任务来说，不值得付出努力。

于 2012-09-12T20:49:59.230 回答
3

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

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;
}

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

于 2012-09-12T18:30:08.697 回答
1

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

这应该快得多，除非你的字符串很短，或者很早就匹配。

于 2012-09-12T19:46:07.190 回答
0

你可以摆脱变量i。

size_t strchroc(const char *str, const char ch){ 
    size_t c = 0;
    while(*str != '\0') {
        if(*str == ch) c++;
        str++;
    }
    return c;
}
于 2012-09-12T18:27:48.710 回答
0 
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;
}
于 2012-09-12T18:41:29.643 回答
0

在快速进行低质量基准测试后，我最终得到了任意长度的字符串。

在巨大的字符串（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;
}
于 2013-10-31T02:17:48.983 回答