如何快速用另一个字符替换字符串中的一个字符（我认为测试不需要通用方式）

Question

我在技术测试中被问到这个问题。
他们询问如何将字符串中的 ' ' 更改为 '_'。
我认为他们不想要共同的答案。像这样（我可以保证）

void replaceChar(char originalStr[], size_t strLength, char originalChar, char newChar 
{
    for(size_t i = 0 ; i < strLength ; i++)
    {
        if(originalStr[i] == originalChar)
        {
            originalStr[i] = newChar ;
        }
    }
}

所以我这样回答。使用单词。（其实我没有写代码，他们只是想解释怎么做）
我认为将字符串的每个 8 字节（64 位 OS）与掩码 8 字节进行比较。
如果他们相等，一次替换8byte。

当Cpu读取小于WORD的数据时，Cpu应该做清除剩余位的操作。
它很慢。所以我尝试使用WORD来比较字符。

void replaceChar(char originalStr[], size_t strLength, char originalChar, char newChar // 
    {
        size_t mask = 0;
        size_t replaced = 0;
        for(size_t i = 0 ; i < sizeof(size_t) ; i++)
        {
            mask |= originalChar << i;
            replaced |= newChar << i;
        }
        
        for(size_t i = 0 ; i < strLength ; i++)
        {
            
            // if 8 byte data equal with 8 byte data filled with originalChar
            // replace 8 byte data with 8 byte data filled with newChar 
            if(i % sizeof(size_t) == 0 && 
               strLength  - i > sizeof(size_t) && 
               *(size_t*)(originalStr + i) == mask)
            {
                *(size_t*)(originalStr + i) = replaced;
                i += sizeof(size_t);
                continue;
            }

            if(originalStr[i] == originalChar)
            {
                originalStr[i] = newChar ;
            }
        }
    }

有没有更快的方法？？

Answer 1

要走得快，首先要做到正确。原始提案的问题在于 sizeof(s) 应该是 strlen(s) 的缓存值。那么明显的问题是这种方法扫描字符串两次——首先找到终止字符，然后找到要替换的字符。

这应该通过具有已知长度的数据结构或数据结构来解决，具有足够保证的超额数据，以便可以一次处理多个字节而不会出现未定义行为。

一旦这个问题得到解决（已编辑 OP 以解决此问题），建议的扫描 8 个字节的数据以确保所有字节相同的方法的问题是，一般情况下确实有 8 个连续的字符，但可能只有 7 个。在所有这些情况下，需要扫描同一区域两次（在扫描字符串终止字符之上）。

如果字符串长度未知，最好使用低级方法：

while (*ptr != 0) {
   if (*ptr == search_char) {
       *ptr = replace_char;
   }
   ++ptr;
}

如果字符串长度已知，最好使用库方法std::replace，或者它的低级对应方法

for (auto i = 0; i < size; ++i) {
    if (str[i] == search_char) {
        str[i] = replace_char;
    }
}

任何体面的编译器都能够对此进行自动矢量化，尽管编译器可能会生成比预期更多种类的内核（一个内核用于小尺寸，一个用于中型，一个用于处理 32 或 64 字节的块）。

Answer 2

当你不知道代码的瓶颈是什么时，不要尝试优化代码。尽量写出清晰可读的代码。

这个函数的声明和定义

void replaceChar(char originalStr[], size_t strLength, char originalChar, char newChar 
{
    for(size_t i = 0 ; i < strLength ; i++)
    {
        if(originalStr[i] == originalChar)
        {
            originalStr[i] = newChar ;
        }
    }
}

没有意义，因为它重复了标准算法的行为 std::replace。

此外，对于这样一个简单的基本通用函数，您使用的标识符名称太长了。

如果你需要专门为C-strings写一个类似的函数那么它可以像下面的演示程序所示的方式寻找例如下面的方式

#include <iostream>
#include <cstring>

char * replaceChar( char s[], char from, char to )
{
    for ( char *p = s; ( p = strchr( p, from ) ) != nullptr; ++p )
    {
        *p = to;
    }
    
    return s;
}

int main() 
{
    char s[] = "Hello C strings!";
    
    std::cout << replaceChar( s, ' ', '_' ) << '\n';
    
    return 0;
}

程序输出为

Hello_C_strings!

至于你的第二个函数那就是不可读了。在 for 循环体中使用 continue 语句很难理解其逻辑。

由于字符数组不需要按 size_t 的值对齐，因此函数没有您想象的那么快。

如果你需要一个非常优化的函数，那么你应该直接用汇编语言编写它。

如何快速用另一个字符替换字符串中的一个字符（我认为测试不需要通用方式）

How to replace a char in string with another char fast(I think test didn't want common way)

c++

algorithm

replace

c-strings

c++11