计算字符串中字符发生次数的最有效方法

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%的编程任务来说,这是不值得的.