优化思维【1】字符串去空格

In place 版本

传入的字符串将被改变。

为方便复用,一般会实现 ltrim 和 rtrim 两个函数,然后 trim 函数调用这两者实现。

  • ltrim:从 str 头部开始找到非空格字符,偏移量记为 offset,将 str 左移(move)offset 个字符。

  • rtrim:从 str 尾部向头部找到非空格字符,偏移量记为 offset,将 str 截断为 offset。

一个想当然的实现:

1
2
3
4
trim(str) {
ltrim(str)
rtrim(str)
}

假设 str 是 x 个空格 + y 个分空格 + z 个空格,则以上代码需要把 y + z 个字符向左移动 x 个位置。

更好的实现是:

1
2
3
4
trim(string& str) {
rtrim(str)
ltrim(str)
}

由于先截断,剩 x + y,再去左移,只需要把 y 个字符左移 x 个位置。

优化思路:尽量减少复制,调整顺序也是优化手段。

Copy 版本

传入的字符串不会被改变,返回一个新的字符串。

一个复用前面代码的实现:

1
2
3
4
5
6
string trim_copy(string str) {
// str is a copy
rtrim(str)
ltrim(str)
return str
}

这个版本需要复制 x + y + z 个字符,ltrim 和 rtrim 里面都有找偏移量的代码可以复用,直接找到 y 个非空格字符是起点和终点,复制这 y 个字符就好了。

1
2
3
4
5
6
string trim_copy(const string& str) {
// str is a copy
l = lfind(str)
r = rfind(str)
return str[l, r]
}

优化思路:尽量减少复制。

move

strlen、strcpy、memmove 这类函数,都有一个优化思路:机器字长对齐,一次处理一个机器字。对于长字符串,效果显著。

优化思路:针对硬件特征调整策略。