[分享]批处理分段法计算字符串长度

netbenton

受到拆半算法的启发，突然想到这种分段法。与大家分亨，不知道是否已有先例。
此方法无论是通用性和速度,都具有很大的优越性。

1. 
   
2. @echo off&setlocal enabledelayedexpansion
   
3. set str=
   
4. :rep
   
5. 
   
6. :::::串长度计算代码:::::::::
   
7. set/a end=8189,add=end
   
8. :lp
   
9. if %add%==1 goto :ok
   
10. set /a ben=end-add,add=^(end-ben^)/30+1
    
11. for /l %%a in (%ben%,%add%,%end%) do (if "!str:~%%a,1!"=="" set end=%%a&goto :lp)
    
12. set end=0
    
13. :ok
    
14. :::::::::::::::::::::::::::::::
    
15. 
    
16. 
    
17. ::测试用代码
    
18. echo %end%
    
19. set str=!str!a
    
20. pause
    
21. goto :rep

复制代码

lxzzr

1. @echo off
   
2. SETLOCAL ENABLEDELAYEDEXPANSION
   
3. set /p a=请输入要计算长度的字符串:
   
4. for /l %%a in (1,1,100000) do (
   
5. set k=!a:~%%a,1!
   
6. if not defined k (
   
7. echo 字符串长度:%%a
   
8. pause>nul
   
9. exit
   
10. )
    
11. )

复制代码

[ 本帖最后由 lxzzr 于 2009-4-23 03:14 编辑 ]

随风

lxzzr 版主想简单了吧。
你的代码1000000000000000000已经超出了cmd的最大数字范围，cmd把他当作字符串处理，所以很快，但%%a不可能得到最终的值，改为一百万再试试？
并且代码获取字符串长度后，如果还需要继续运行怎么办？

1. @echo off
   
2. SETLOCAL ENABLEDELAYEDEXPANSION
   
3. set /p a=请输入要计算长度的字符串:
   
4. for /l %%a in (1,1,1000000) do (
   
5.    set k=!a:~%%a,1!
   
6.    if not defined k (
   
7.    echo 字符串长度:%%a
   
8.    goto loop
   
9. ))
   
10. :loop
    
11. echo 这里还需要对字符串进行处理。
    
12. pause

复制代码

lxzzr

随风版主说的是，我想的有点简单了....

netbenton

改了一下，减少了一次goto :lp循环，并且for /l 次数也从30降为21,速度有所提升

1. @echo off&setlocal enabledelayedexpansion
   
2. set str=
   
3. :rep
   
4. 
   
5. 
   
6. set/a end=8189,add=end
   
7. :lp
   
8. if %add%==1 goto :ok
   
9. set /a ben=end-add,add=^(end-ben+20^)/21
   
10. for /l %%a in (%ben%,%add%,%end%) do (if "!str:~%%a,1!"=="" set end=%%a&goto :lp)
    
11. set end=0
    
12. :ok
    
13. echo %end%
    
14. 
    
15. 
    
16. 
    
17. set str=!str!a
    
18. pause
    
19. goto :rep

复制代码

二楼说的最简单的方法应该是这个吧：
str 为字符串变量

1. 
   
2. if not defined str set num=0&goto :ok
   
3. for /l %%a in (0,1,8189) do (if "!str:~%%a,1!"=="" set num=%%a&goto :ok)
   
4. :ok

复制代码

此法并非不可用，只是效率一般，串越长越慢
虽然只有一个for ，并且for /l的速度很快，但是也需要时间的
因为在系统在解释for /l时已经分配了8189次if "!str...命令行

[ 本帖最后由 netbenton 于 2009-4-23 17:56 编辑 ]

随风

是否考虑写成 “函数”

netbenton

又改了一下，把8189改成了8190，否则最后一段取不到结果
写成函数如下：

1. :::::::::::::::::::::::::::::::::::::::::
   
2. :getstrlen  分段法取字符串长度
   
3. ::  用法用途：
   
4. ::  把代码放到批处理中作为函数使用
   
5. ::  取指定字答串的长度
   
6. ::  调用方法：
   
7. ::  call :getstrlen 字符串变量名 结果变量名
   
8. ::::::::::::::::::::::::::::::::::::::::::
   
9. 
   
10. setlocal enabledelayedexpansion
    
11. set "str=!%1!"
    
12. :rep
    
13. set/a end=8190,add=end
    
14. :lp
    
15. if %add%==1 goto :ok
    
16. set /a ben=end-add,add=^(end-ben+20^)/21
    
17. for /l %%a in (%ben%,%add%,%end%) do (if "!str:~%%a,1!"=="" set end=%%a&goto :lp)
    
18. set end=0
    
19. :ok
    
20. endlocal&set %2=%end%&goto :eof

复制代码

netbenton

1. 
   
2. @echo off&setlocal enabledelayedexpansion
   
3. set str=
   
4. :rep
   
5. 
   
6. ::变量ds用来指定分段数,可随意指定（2到8190）都可以。
   
7. set/a ds=4,ds1=ds-1
   
8. 
   
9. if not defined str set end=-1&goto :ok
   
10. set/a end=0,add=8190
    
11. for /l %%a in (0,1,14) do (
    
12. if !add!==1 goto :ok
    
13. set /a end+=add,ben=end-add,add=^(end-ben+ds1^)/ds
    
14. for /l %%b in (!ben!,!add!,!end!) do (if not "!str:~%%b,1!"=="" set end=%%b)
    
15. )
    
16. :ok
    
17. set /a end+=1
    
18. echo !end! !str!
    
19. 
    
20. set str=!str!a
    
21. pause
    
22. goto :rep
    

复制代码

可以做到随意n分段，分为2段时，就像随风版主的拆半法了，到底分多少段才是最快速的呢？

raymai97

回复 8# netbenton


请问可以解释一下何为“折半算法”吗？我看了半天头都晕了都不明白啊~

garyng

回复 9# raymai97


你的折半法是指 搜索 还是？

raymai97

回复 10# garyng


    这个帖子的折半算法~ 效率高很多，问题是我不明白啊~

garyng

回复 11# raymai97

具体我也不清楚啦。。
可是效率极高！！

CrLf

回复 11# raymai97


回复 12# garyng


    十进制8191=4096+2048+1024+512+256+128+64+32+16+8+4+2+1=二进制的1111111111111
用二进制来理解可能比较简单，先判断第一位（从左至右）的状态，大于则标记相应位为 1，小于则标记为 0。

raymai97

回复 13# CrLf


OMG你们这群数学天才，汇编对你们来说肯定是小意思了……
我真的很好奇你们的头脑是怎样练出来的，难道你们在学校数学都是拿第一的？
真的很佩服你们，你们几年前的帖子比我现在的水平还要高，恐怕外国人也没这么强……

ok切入正题，我还是不太明白这段：

1. set /a ben=end-add,add=^(end-ben^)/30+1
   
2. for /l %%a in (%ben%,%add%,%end%) do (if "!str:~%%a,1!"=="" set end=%%a&goto :lp)

复制代码

先说上面那段：
ben=end-add(8189-8189)?
add=(end-ben)/30+1 (8189-0)/30+1
为何要除30+1呢？

CrLf

回复 14# raymai97


    这跟数学好有什么关系...
    那个代码中先除 30 再加 1 是用无限逼近的办法，类似于 batman 发过的开方算法