c - 计算字符串中字符出现次数的最有效方法

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

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

(在速度和使用最少资源方面高效)。

Answer 1

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

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

顺便说一句，我将列出一些加速字符计数器的可能方法:

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

等等。

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

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