Board logo

标题: [文本处理] [分享]批处理字符串长度函数：二分搜索算法 [打印本页]
作者: neorobin    时间: 2009-12-11 17:55     标题: [分享]批处理字符串长度函数：二分搜索算法

二分搜索算法是一种较高效的搜索算法, 它的空间复杂度是较低的, 时间复杂度也只是对数级别增长.
(搜索了一下, 原来 随风 也写过这个算法, 居然标号和我用的都一样: binsearch, 申明: 我这里绝无任何抄袭,
我的算法多了一个二倍搜索上界的阶段, 随风的版本, 初始上界是固定的
随风 版: http://bbs.bathome.net/viewthread.php?tid=4219&page=1#pid27019
plp626 对随风版的效率分析 http://bbs.bathome.net/viewthread.php?tid=5993&page=1#pid38750)

我这里提出的算法对于确定一个长度(非字节长度, 全半角同一处理) Length < 2 的 n 次方 的字符串,

大约需 2n 次搜索即可确定, 即 搜索次数 ≈ 2*log₂Length

本算法的基本原理:
第 1  阶段, 用 2 倍搜索法搜索出 Length 的上界,
第 2  阶段, 用 2 分搜索法确定出 Length 的值, 初始下界为 0 或者 初始上界/2(初始下界为 0 也只需 1  次搜索调整后即变为 初始上界/2).

算法理解:
例如: 设一个字符串的长度是 1000, 将首个字符到最后一个字符依序定义为 第0 到 第999 个字符,
      以下的搜索就是对字符的索引(定义的第某个)进行搜索,
     搜索结束时, t 值成为 999, 返回 t+1=1000 就是我们所要的结果.
     
第一阶段, 2 倍搜索, 上界逐次变化的序列为: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024
    此时, %%u 的值为 1024, 所以 if "!str:~%%u,1!" equ "" 的判断为真,
    执行 goto binSearch, 转入第二阶段.
   
第二阶段, 2 分搜索,
    t=(lower+upper)/2=(0+1024)/2=512, 判断 "!str:~%%t,1!" equ "" 为假, lower=t=512         |->下界增大->|                   |
    t=(lower+upper)/2=(512+1024)/2=768, 判断 "!str:~%%t,1!" equ "" 为假, lower=t=768     |->下界增大->|                   |
    t=(lower+upper)/2=(768+1024)/2=896, 判断 "!str:~%%t,1!" equ "" 为假, lower=t=896     |->下界增大->|                   |
    t=(lower+upper)/2=(896+1024)/2=960, 判断 "!str:~%%t,1!" equ "" 为假, lower=t=960     |->下界增大->|                   |
    t=(lower+upper)/2=(960+1024)/2=992, 判断 "!str:~%%t,1!" equ "" 为假, lower=t=992     |->下界增大->|                   |
    t=(lower+upper)/2=(992+1024)/2=1008, 判断 "!str:~%%t,1!" equ "" 为真, upper=t=1008   |                   |<-上界减小<-|
    t=(lower+upper)/2=(992+1008)/2=1000, 判断 "!str:~%%t,1!" equ "" 为真, upper=t=1000   |                   |<-上界减小<-|
    t=(lower+upper)/2=(992+1000)/2=996, 判断 "!str:~%%t,1!" equ "" 为假, lower=t=996     |->下界增大->|                   |
    t=(lower+upper)/2=(996+1000)/2=998, 判断 "!str:~%%t,1!" equ "" 为假, lower=t=998     |->下界增大->|                   |
    t=(lower+upper)/2=(998+1000)/2=999, 判断 "!str:~%%t,1!" equ "" 为假, lower=t=999     |->下界增大->|                   |
    t=(lower+upper)/2=(999+1000)/2=999,
    到此 判断 if !t! equ !lower! 成立, 于是执行 (set /a %1=t-1) & exit /b
    返回 长度值 %1=t+1, 但实际代码中考虑参数加了 2 个双引号, 所以 返回结果就为 t+1-2=t-1.
  
总体分析: 第一阶段, 从 1 到 1024 共 10 个数字, 变化次数是 9.
                第二阶段, 搜索了 10 次, 所以总共搜索了 19 次, 证实了 搜索次数 ≈ 2*log₂Length

这是一种很普通的算法, 自认为也是很好的算法.
只是目前对某些特殊字符不能输出正确结果, 希望在特殊字符方面认识深入的朋友们多关注, 并提出改良方案.
优点: 搜索迅速, 不用巨量数字的变量, 适应超长字符串, 无文件操作

在命令行输入单个字符时, 得不到正确结果的有下列:
造成退出的 "    返回长度为 0的: ! %  返回长度为 2 的 ^  其它字符(包括|<>&@)都能得到正确的结果 1.
对于多个特殊字符的组合目前尚未测试.

字符串长度其它的算法:

有用 "最大长度" 个变量来索引计算的
http://bbs.bathome.net/viewthread.php?tid=4482&page=1#pid30563

有最容易想到的顺序逐一搜索法
http://bbs.bathome.net/viewthread.php?tid=1480&page=2#pid20046

还有更简单的文件大小法:
将串内容输出重定向到文件, 再读取文件大小

还有管道加 findstr /o 偏移量算法的
  1. @echo off & setlocal enabledelayedexpansion

  2. :loop

  3. cls & (set sss=) & set /p sss=请输入一个字符串:

  4. (call :strLen len "!sss!")

  5. echo "!sss!"&echo\&echo 长度:!len!

  6. pause & goto loop

  7. exit /b         &rem end of main program

  8. rem 调用时, 字符串值必须加上双引号对, 以适应串中含有空格的情况; 不能用字符串变量名作为参数

  9. :strLen lenVarName "strValue"

  10. (set str=%2)

  11. if "!str!" equ """" (set %1=0)&exit /b

  12. (set /a lower=0, upper=1)

  13. :searchUpper

  14. for /f "tokens=1" %%u in ("!upper!") do if "!str:~%%u,1!" equ "" goto binSearch

  15. (set /a upper*=2)

  16. goto searchUpper

  17. :binSearch

  18. set /a "t=(lower+upper)/2"

  19. if !t! equ !lower! (set /a %1=t-1) & exit /b

  20. for /f "tokens=1" %%t in ("!t!") do  if "!str:~%%t,1!" equ "" (set /a upper=t) else (set /a lower=t)

  21. goto binSearch

  22. exit /b
复制代码

[ 本帖最后由 neorobin 于 2009-12-11 20:10 编辑 ]
作者: wc726842270    时间: 2011-3-2 09:12

以前不怎么关注这些，现在看来有些错误了，不过这种贴子在这儿，可能会石入大海

[ 本帖最后由 wc726842270 于 2011-3-2 09:13 编辑 ]



欢迎光临 批处理之家 (http://www.bathome.net/) Powered by Discuz! 7.2