对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算法的话,还可以让速度再次增加。。。

目录
相关文章
|
3月前
|
算法
【算法系列篇】递归、搜索和回溯(四)
【算法系列篇】递归、搜索和回溯(四)
|
1天前
深度优化搜索,字典树
深度优化搜索,字典树
12 0
|
4月前
|
算法 前端开发 搜索推荐
二分查找算法:搜索有序数组中目标元素的利器
二分查找算法:搜索有序数组中目标元素的利器
|
3月前
|
算法
【算法系列篇】递归、搜索与回溯(一)
【算法系列篇】递归、搜索与回溯(一)
|
3月前
|
算法
【算法系列篇】递归、搜索和回溯(三)
【算法系列篇】递归、搜索和回溯(三)
|
3月前
|
算法
【算法系列篇】递归、搜索和回溯(二)
【算法系列篇】递归、搜索和回溯(二)
|
3月前
|
算法 前端开发 索引
前端算法-搜索插入位置
前端算法-搜索插入位置
|
9月前
|
Java 索引
力扣35搜索插入位置:思路分析+图文详解+代码实现+拓展java源码
力扣35搜索插入位置:思路分析+图文详解+代码实现+拓展java源码
79 0
|
11月前
|
算法
一篇文章带你整体了解算法中的基本问题《查找》
查找 本章对算法中的基本问题--查找做了一个简要介绍,包含了一些基本算法思想以及评价,后续文章详细介绍一些算法,欢迎关注本系列。 可以转载,但请声明源链接:文章源链接justin3go.com(有些latex公式某些平台不能渲染可查看这个网站)
46 0
|
存储 并行计算 算法
秒懂算法 | 搜索基础
本篇介绍了BFS和DFS的概念、性质、模板代码。
114 0
秒懂算法 | 搜索基础