首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

高效率字符串比较算法

2013-07-08 
高效字符串比较算法?记得以前看过一个帖子好像说字符串比较不知道说字符串拷贝。大体是这样:把字符串转成了

高效字符串比较算法?
记得以前看过一个帖子好像说字符串比较不知道说字符串拷贝。
大体是这样:把字符串转成了int然后比较,而且余数部分用了switch。忘记了具体实现。比较部分(for以下的代码)好像是这样写的,但是for以上部分还要先用strlen求长度,那不是效率很低?

我记得代码一定是用了switch的,但是具体怎么用起来的忘记了,有人知道吗?


bool Astrcmp(char* str1, char *str2)
{
int iLen1 = strlen(str1);
int iLen2 = strlen(str2);
if (iLen1 != iLen2)
return false;

//这以下的代码应该是这样写的,但是上面部分难道要求长度?那不是效率很低吗?
for (int i = 0; i <= iLen1; i += 4)
{
if( *(int*)&str1[i] != *(int*)&str2[i] )
return false;
}
switch (iLen1%4)
{
case 0:
return true;
case 1:
return str1[iLen1-1] == str2[iLen1-1];
case 2:
return (str1[iLen1-1] == str2[iLen1-1] && str1[iLen1-2] == str2[iLen1-2]);
case 3:
return (str1[iLen1-1] == str2[iLen1-1] && str1[iLen1-2] == str2[iLen1-2] && str1[iLen1-3] == str2[iLen1-3]);
}
}

[解决办法]
用int代替char,一次比较4字节,是一种优化。不过应该用CPU字,而不是int。
这个程序没有考虑strlen的代价,这是一个错误。
也没有考虑字对齐的问题,对于执行效率来说做不到通用。
另外可能考虑通过移位操作来替换switch部分。
[解决办法]
引用:
CPU字是指CPU字长吗?int不都是一个CPU字长的吗?
恩,strlen肯定是错的,但是我忘记本来是怎么实现的了。不知道怎么做。
没考虑字对齐,这个应该怎么做?

int与编译器根据所处的环境相关;如果要用位移运算的话,最好用unsigned修饰。

求串长度,应该两个串同时扫描,这样可以只扫描两者较小的长度。
1.两参数长度不同的时候,长度与比较的处理分开比较好。
2.两参数长度相同的时候,长度的处理可以放到循环体内和比较一起处理,单独处理的话需要等于多扫描了一次内存。
这两种情况脱离实际环境谈不上谁好谁差,我个人倾向于方案2,因为最坏情况只要扫描内存一次。

字对齐分三种情况,目的就是为了避免同一个CPU字的存储单元被读取两次:
1.两个参数相互对齐,并且与CPU字对齐,就是楼主的程序可以直接处理的情况。
2.两个参数相互对齐,但不与CPU字对齐,应该先处理参数与CPU不对齐的部分,然后就变成了楼主的程序可以直接处理的情况。
3.两个参数相互不对齐,应该使其中一个参数CPU对齐,另一个参数在循环体中使用临时量和移位运算使其对齐,因为寄存器的移位与或运算相对于读取内存的代价小。

热点排行