作者:冯老师,华清远见教育科技集团讲师。
在面试题中经常考到各种各种的字符串处理函数,下面就一个简单的字符串长度处理函数做讲解并演示如何编写一个高效的strlen函数。
#include <stdio.h>
#define OPTIMIZE 1
#if OPTIMIZE
/*以下代码段是针对32位CPU深度优化调整后的strlen函数,我们充分利用CPU的数据宽度,使用int指针去访问内存数据,每次按照CPU字长去读取数据,极大地利用了CPU访问内存的能力。虽然每次读取一个int型都需要判断其中是否出现空数据字节(‘\0’),但是依然要比按字节访问内存提高极大的运行速度。 */
int mystrlen(char *str)
{
/* 为了避免数据指针的自增导致频繁访问内存,所有的临时变量都声明为寄存器存储类型,以提高运行速度 */
register int *tail = (int *)str;
register int value;
register int len = 0;
char *p;
while (1) {
/* 用临时变量接受读取的内存值,目的是避免在接下来的判断表达式中使用*tail以提高运算速度(*tail会让编译器生成一条访存指令,拖慢速度) */
value = *tail;
/* 用if运算来判断每一个字节,以确保如果遇到空字节(‘\0’)则立即结束循环,否则认为没有遇到字符串结尾,则将长度计数器增加4 */
if (!(value & 0xff000000) || !(value & 0xff0000)
|| !(value & 0xff00) || !(value & 0xff))
break;
len += 4; /* 长度计数器自增4字节 */
tail++; /* 当前数据指针后移 */
}
p = (char *)tail;
while (*p++ != '\0')
len ++;
return len;
}
#else
/* 以下程序片段是简单的字符串长度计算功能,大部分程序员都会使用这种方法,原因是简单易于编写和维护。但是其运行的效率实在不敢恭维,因为其使用了一个char型指针去访问内存,每次读取一个字节,严重浪费了32位CPU的数据宽度。 */
int mystrlen(char *str)
{
char *tail = str;
while ('\0' != *tail)
tail++;
return tail - str;
}
#endif
/* 以下主程序用来测试编写的函数速度,方法是用编写的函数计算长度为50个字符的字符串一千万次,并用time函数计算运行总时间。 */
int main()
{
char *str = "12345678901234567890123456789012345678901234567890";
int len;
int i;
for (i = 0; i < 10000000; i++)
len = mystrlen(str);
return 0;
}
以下是测试结果:
没有优化后的测试结果:
优化后的测试结果: