对pos搜索函数的研究以及优化思路···-阿里云开发者社区

开发者社区> :br阶乘> 正文

对pos搜索函数的研究以及优化思路···

简介: 代码摘自delphi的Pos函数。。。总的来说,若我理解无误的话,该函数才用的搜索机制并不是非常高明。
+关注继续查看

代码摘自delphi的Pos函数。。。总的来说,若我理解无误的话,该函数才用的搜索机制并不是非常高明。。。只是简单的使用了一个倒序搜索,仅此而已。。。但其速度优于BM,应该是由于其对CPU的优化。。。

 

   首先先介绍一下register 调用约定: 从左到右,优先使用寄存器(EAX,EDX,ECX),然后使用堆栈!这个调用约定和C++里面的__fastcall有些类似,不同的是__fastcall优先使用的只有ECX和EDX。这两种调用约定应该说是最快速的调用约定。。

 

    再贴一部分比较重要的源码,,源码都注释过,,也没什么解释的。。

开始为准备做工作:

       push  ebx   ;保护ebx esp-4
       push  esi   ;保护esi esp-4
       add   esp, -16   ;esp-16  char* i,j,b,p;
       test  edx, edx   ;测试被搜索字符串
       jz    @NotFound
       test  eax, eax   ;测试要搜索的子串
       jz    @NotFound
       mov   esi, [ebp+8]  ;esi = strLen
       mov   ebx, ecx    ;ebx = substrLen
       cmp   esi, ebx   ;strLen < substrLen 则跳出
       jl    @NotFound
       test  ebx, ebx   ;substrLen == 0 则跳出
       jle   @NotFound
       dec   ebx   ;substrLen--
       add   esi, edx   ;
       add   edx, ebx   ;指向开始比较的位置。str偏移为strlen(substr)的位置,比较关键,后期字符串搜索和这个指针有密切的关系
       mov   [esp+8], esi  ;j指向被搜索字符串的尾部
       add   eax, ebx
       mov   [esp+4], edx  ;i指向要搜索子串的尾部位置
       neg   ebx   ;ebx,substrLen长度减一的补码
       movzx ecx, byte ptr [eax] ;ecx = substrLen[0]
       mov   [esp], ebx   ;[esp] = ecxc
       jnz   @FindString

开始具体的搜索:
    @FindString:
           sub   esi, 2  ;
           mov   [esp+12], esi ;p = strLen-2,指向被搜索字符串后输2的位置
    @FindString2:
           cmp   cl, [edx]  ;
           jz    @Test0  ;
    @AfterTest0:
           cmp   cl, [edx+1]
           jz    @Test1
    @AfterTest1:
           add   edx, 2  ;str = str + 2;
           cmp   edx, [esp+12] ;
           jb    @FindString4 ;从后向前比较如果在从后数两位以上则执行每四位比较一次的操作
           cmp   edx, [esp+8] ;
           jb    @FindString2 ;如果后面只剩了两位,则只能进行最后两位的操作。
           xor   eax, eax
           jmp   @Exit1

 (Test0 , Test1 , Test2 , Test3操作相同,只是调整了一下指针的位置,只是调整了一下指针的位置)

 

其它的感觉也没什么好注释的,在上面可以看到,这个算法其实思路非常简单,个人感觉,如果用这种优化方式来实现sunday算法的话,还可以让速度再次增加。。。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
函数的⽂档说明 | 手把手教你入门Python之四十一
本节重点介绍函数的⽂档说明,函数应⽤:打印图形和数学计算
1109 0
LeetCode 700. 二叉搜索树中的搜索
给定二叉搜索树(BST)的根节点和一个值。
85 0
JavaScript创建对象(四)——组合使用构造函数和原型模式
在JavaScript创建对象(三)——原型模式中,我们阐述了原型模式存在的两个问题:一是没办法通过构造函数初始化对象属性,二是共享引用类型的数据导致数据错乱。
825 0
+关注
30
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载