有关字符串翻转reverse的思考

孟子曰:“尽信《书》,则不如无《书》”

陈硕Muduo一书第12章中提及“用异或交换变量是错误的”。校招面试的时候经常遇到这个问题,竟然没有深入思考这一点。

首先来看看翻转一个字符串的三种方法:

  • 方法一:
1
2
3
4
5
6
7
8
9
10
11
12
void reverse_by_swap(char* str, int n) {
char *b = str;
char* e = str + n - 1;
while(b < e) {
char t = *b;
*b = *e;
*e = t;
++b;
--e;
}
}
  • 方法二:
1
2
3
4
5
6
7
8
9
10
11
12
void reverse_by_xor(char* str, int n) {
char *b = str;
char* e = str + n - 1;
while (b < e) {
*b ^= *e;
*e ^= *b;
*b ^= *e;
++b;
--e;
}
}
  • 方法三:
1
2
3
void reverse_by_std(char* str, int n) {
std::reverse(str, str + n);
}

使用下面程序来测试三种方法耗时:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Timestamp ts;
for (int i = 0; i < 1000000; ++i)
reverse_by_swap(r, 10);
int64_t t1 = ts.elapsed();
ts.update();
for (int i = 0; i < 1000000; ++i)
reverse_by_xor(l, 10);
int t2 = ts.elapsed();
ts.update();
for (int i = 0; i < 1000000; ++i)
std::reverse(s, s+ 10);
int t3 = ts.elapsed();
logger().info("t1=" + std::to_string(t1) + " t2: " + std::to_string(t2) + " t3: " + std::to_string(t3));

测试的字符串分为长字符串和短字符串两种(样例随机选择,能够支持最后结论就好):

1
2
char *str1 = "0123456789";
char *str2 = "012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789";

三种方法的时间耗时如下表,单位纳秒:

字符串 方法一 方法二 方法三
str1 4960 8928 6447
str2 85311 230144 11904

可以看出方法二的复杂度明显高于其他两个方法,以后在面试的时候可以让学生分析为什么会这样。对于方法一和方法三,在字符串较短时方法一更高效,字符串较长时方法三更高效。在网上搜了一圈,没看出std::reverse是怎么实现的。cppreference给出的可能实现如下:

1
2
3
4
5
6
template<class BidirIt>
void reverse(BidirIt first, BidirIt last) {
while ((first != last) && (first != --last)) {
std::iter_swap(first++, last);
}
}

这三种方法的对比得出了几点结论:

  • 标准库的实现往往是最佳的选择;
  • 深入思考打败人云亦云;
  • 没有测试数据作证的揣测都是臆想;
  • premature optimization is the root of all evil

本文作者:ZeroJiu
本文链接: http://www.freehacker.cn/reading/reverse/
版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 CN 许可协议。转载请注明出处!
温馨提示:开启科学上网访问本站,能获得更好的阅读体验,并启用Disqus评论功能和作者交流。