[文本处理] 求字符串长度，简短高效的批处理代码（多种算法）

plp626

这是迄今为至，我多年来看过的批处理代码中，见到的最优美的一段代码，不和大家分享一下实在不好意思。
原以为，求字符串长度的方法在二分法和查表法后不会有突破了，但我发现时我的思想是太懒了。

二分回溯法（现在更正下，准确的叫法应该是优化的二分法）求字符串长度：
原帖：http://www.dostips.com/forum/viewtopic.php?f=3&t=1429

setlocal enabledelayedexpansion
set "$=!%1!#"
set len=&for %%a in (4096 2048 1024 512 256 128 64 32 16 8 4 2 1)do if !$:~%%a^,1!. NEQ . set/a len+=%%a&set $=!$:~%%a!
endlocal&If %2. neq . (set/a%2=%len%)else echo %len%
复制代码

关于求字符串长度，以前论坛里讨论过不少，但就代码长度，支持最长字符串，和执行耗时来综合考虑，
我“个人认为”都没有超越上面这段代码。

把原代码小修小补增加了30多K的字节（原帖是联合256位的表），可以减少相当于大概2~7次set 赋值命令所耗费的时间（效率提高8%~30%）:

:strlen <stringVarName> [retvar] 
:: 思路： 二分回溯联合查表法
:: 说明： 所求字符串大小范围 0K ~ 8K；
::    stringVarName ---- 存放字符串的变量名
::    retvar      ---- 接收字符长度的变量名
setlocal enabledelayedexpansion
set "$=!%1!#"
set N=&for %%a in (4096 2048 1024 512 256 128 64 32 16)do if !$:~%%a!. NEQ . set/aN+=%%a&set $=!$:~%%a!
set $=!$!fedcba9876543210&set/aN+=0x!$:~16,1!
endlocal&If %2. neq . (set/a%2=%N%)else echo %N%
复制代码

对于上面代码
如果所求字符串长度不超过4096：
可以将4096 2048 1024 512 256 128 64 32 16改为2048 1024 512 256 128 64 32 16

如果所求字符串长度不超过2048：
可以将4096 2048 1024 512 256 128 64 32 16改为      1024 512 256 128 64 32 16
以此类推。。。
=============================================================
测试一下效率

@echo off&setlocal enabledelayedexpansion
:: 将strlen函数内敛到变量_strlen中,测试字符串长度小于4096；入口参数#1，返回变量##
set "_strlen=set $=^!#1^!#&set ##=&(for %%a in (2048 1024 512 256 128 64 32 16)do if ^!$:~%%a^!. NEQ . set/a##+=%%a&set $=^!$:~%%a^!)&set $=^!$^!fedcba9876543210&set/a##+=0x^!$:~16,1^!"

:: 生产一个长度为4096字符个数的字符串
set str=.&for /l %%a in (1 1 12)do set str=!str!!str!

:: 测试一下速度，4000次
set bt=%time%
for /l %%a in (1 1 4000)do (
        set #1=!str:~-%%a!
        (%_strlen%)
        echo 长度:!##!
)
set et=%time%
:: 计算花费时间
set /a ct=1!et:~-5,2!!et:~-2!-1!bt:~-5,2!!bt:~-2!,ct+=-6000*("ct>>31")
echo ---------------------&echo 开始时间：%bt%&echo 结束时间：%et%
echo 4000次测试用时：%ct% 跑秒&echo -----------------------
pause
复制代码

plp626

在这里把论坛里求字符串长度的帖子做一个索引，大家可以把这些方法相互做个比较，
也许你能从中提炼出精华得到更代码更简洁效率更高效的方法也不一定。

求字符串长度练习（各种方法，真是大杂烩，很多带有goto循环的和调用三方的方法）
http://www.bathome.net/viewthread.php?tid=1480

当字符串较长时不得不用的方法——二分法
http://bbs.bathome.net/viewthread.php?tid=4219

对字符串长度有限制的查表法：
（9位和40位）http://www.bathome.net/viewthread.php?tid=3136 （6楼）
（16位）http://www.bathome.net/viewthread.php?tid=1249 （15楼）
（255位和1024位）http://www.bathome.net/viewthread.php?tid=5994
关于查表法还有很多相关代码，但思想都来源于9位法，不再列举。
======================================================

下面对这些求字符串长度的典型方法做个大致的汇总（代码均来自上面的索引贴子）
带有goto循环的方法，使得效率极为低下，这里不列举。
调用三方工具求长度的方法（如findstr/o 法，vbs法，for/f +dir法，xcopy法）效率更极为低下，这里不列举

方法一：思路最直接，代码最简短，但效率最低的方法（所求字符串较长时不宜采用）
原帖：http://www.bathome.net/viewthread.php?tid=1480

set/p str=input a string:
set StrMAX=1000
if not defined str set num=0&goto :ok
for /l %%a in (0,1,%StrMAX%) do if "!str:~%%a,1!"=="" set num=%%a&goto :ok
:ok
echo 长度=!num!
复制代码

方法二：适合求长字符串的二分法：
原帖：http://bbs.bathome.net/viewthread.php?tid=4219

set /p s=please input a string:
setlocal enabledelayedexpansion
set /a n=8189*2,max=1&set "var="
for /l %%a in (1 1 14) do (
   if defined var set /a n=var
   set /a n/=2
   for %%i in (!n!) do (
      if "!s:~%%i,1!"=="" (set /a var=n) else (
         set s=!s:~%%i!&set /a max+=%%i,var-=%%i
)))  
endlocal&echo 长度：%max%
复制代码

方法2.X 改进的二分搜索法（效率提高不少）
原帖：http://www.dostips.com/forum/viewtopic.php?f=3&t=1429

set /p str=input a string
SETLOCAL ENABLEDELAYEDEXPANSION
    set "str=A!str!"
    set len=0
    for /L %%A in (12,-1,1) do (
        set /a "len|=1<<%%A"
        for %%B in (!len!) do if "!str:~%%B,1!"=="" set /a "len&=~1<<%%A"
ENDLOCAL&echo 长度：%len%
复制代码

方法三：查表法
当所求字符串长度小于16时，速度最快最简短的查表法：
原帖：http://www.bathome.net/viewthread.php?tid=1249 （15楼）

set str=!str!fedcba9876543210&set/a len=0x!str:~15,1!
echo 长度%len%
复制代码

当所求字符串字符数小于256时，速度最快（和上面代码效率相当）但代码较长的查表法
（一般说来，若用较短的程序生产该512表，至少需要16次set赋值语句的执行）：
原帖： http://www.bathome.net/viewthread.php?tid=5994

@echo off&setlocal enabledelayedexpansion
set/p str=input a string:
set "$=000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f404142434445464748494a4b4c4d4e4f505152535455565758595a5b5c5d5e5f606162636465666768696a6b6c6d6e6f707172737475767778797a7b7c7d7e7f808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9fa0a1a2a3a4a5a6a7a8a9aaabacadaeafb0b1b2b3b4b5b6b7b8b9babbbcbdbebfc0c1c2c3c4c5c6c7c8c9cacbcccdcecfd0d1d2d3d4d5d6d7d8d9dadbdcdddedfe0e1e2e3e4e5e6e7e8e9eaebecedeeeff0f1f2f3f4f5f6f7f8f9fafbfcfdfeff%str%%str%"
set/a len=0x!$:~-512,2!
echo 长度：%len%
pause
复制代码

方法四：等长替换计算法
原帖: 见本贴13楼lllsoslll的代码
（效率低于纯查表法，仅次于二分回溯法，优势在于表的生产不是很占用时间，且代码较短）
注意注意，"SET $=123456789$" 中，等号后的空白字符不是空格符！，而是ascii码为127的那个del字符；

set/p #1=string:?

SET $=123456789$&FOR /L %%a in (1 1 3)Do SET $=!$!!$!!$!!$!!$!!$!
SET $=!#1!`$!$!&SET $=!$:~0,2376!&SET $=!$:*`$=!&SET/A"$=-1,##=2372-(!$:123456789$=11+!+!$:~-1!)"

echo length=!##!
复制代码

其他方法：待续。。。

--------------------------------- 更新1 -------------------------------
下面算法思想是基于16查表法，先求出待测字符串长度对16的"倍数值"，再求对16的余数值；最后相加

@echo off
setlocal enabledelayedexpansion
:: 要测试的字符串
set $1=123456789012345678901234567890123456789012345670
:: 该字符串长度不超过256且大于0
set $2=256
rem ----------------------------------------------

rem ----------------------------------------------
echo 长度为 %$%
pause
复制代码

当$2指定为256，这段代码的耗时相当于10次set赋值操作的耗时，
对于短字符串求长度，效率和代码体积上，很实用（效率很高，且算法简单，容易理解记忆）
---------------------------------------------------------------------

如果把16位表换为256为表， 那么对于小于4096长度以内的字符串，由于512位的表占用了不少空间， 会影响 外部环境 赋值，取值操作效率，
关于这个问题， 有时间我再做测试，

预期这个效率兴许会比1楼代码效率高。。。
经测试， 对于长字符串，该方法较比1楼的代码 效率提高了25%左右

随风

非常巧妙的方法，赞！
集效率简短于一身
果然~~

caruko

也是二分法的一种..
每次检测后就截断的确可以省去IF判断，很巧妙！
至于直接使用4096省去计算，早已经有用过。
而16位以后改查表法感觉提升的效率有限。

那个移位法，没怎么看懂，但是也是计算2的N次方，的确不如直接用4096快。

CrLf

也想过类似的思路，但是当时思维惯性，只想到了二分回溯补位，并没有用变量偏移，一墙之隔啊，可惜当时没想这么深入，呵呵。

plp626

有一种直觉，几乎接近真实了
就求字符串长度来说，还有比一楼更快代码更简洁的代码。

CrLf

我的想法：

@echo off
set "$=%1"
setlocal enabledelayedexpansion
set len=8192
(for %%a in (4096 2048 1024 512 256 128 64 32 16 8 4 2 1)do (
	set /a len-="%%a!$:~%%a,1!"||set $=!$:~%%a!
))2>nul
echo %len%
::未考虑字符串包含数字、特殊字符的情况
复制代码

稍加改进后仍然难以克服特殊字符的难关：

@echo off
set "$=%1"
setlocal enabledelayedexpansion
set len=8192
(for %%a in (4096 2048 1024 512 256 128 64 32 16 8 4 2 1)do (
	set /a len-="%%a*^!(1-1!$:~%%a,1!)"||set $=!$:~%%a!
))2>nul
echo %len%
pause
::不惧怕数字了，但是仍然没有办法在set /a中很好地转义特殊字符，看来要想通用，那个if是不能省的了
复制代码

terse

当多数人的思维在二分法和查表法后 正如plp626兄说道 "我们的思想是太懒了"
看这段精妙代码后 和plp626兄一样 我“个人认为” 似乎都没有超越上面这段代码
现在想法 结合查表法至 2048 位 然后 for %%a in (4096 2048)do...
表太长了  不贴这里了

netbenton

发现，楼主的这个代码和16字符限制的查表法合并才是最佳的，即8 4 2 1项用查表法代替。效率应该可以提高20%，增加的字符也不多

plp626

同findstr类似，又一个外部命令求字符串长度的方法（适合于纯英文字符），连续的宽字符被视为1个字符；

@echo off
setlocal enabledelayedexpansion
set str=www.bathome.net
set n=0
for /f "delims=" %%a in ('cmd/u/cecho !str!^|more')do set/a n+=1
set n
pause
复制代码

如果要给英文字符串中每个字符后加换行符，这是个简洁的方案；

wankoilz

无聊翻看经典帖子，发现前两段代码好像都少算了一个字符，比如第二段代码，在执行到

set $=!$!fedcba9876543210&set/aN+=0x!$:~16,1!
复制代码

的时候，变量$的长度范围应该是1-16(不考虑$长度为0)，而fedcba9876543210只能表达0-15
所以似乎应该把这一句改成这样：

set $=!$!!$!100f0e0d0c0b0a090807060504030201&set/aN+=0x!$:~32,2!
复制代码

小小疏忽，请明察

xxpinqz

回复 11# wankoilz

因为源代码在字符串后补了一个字符，所以才用位移16,例字符串"abcd",实际扩展开来：$=abcd#fedcba9876543210    所以len=4

fedcba9876543210,这个本来就是取15位以内长度，没人说能取16位。

wankoilz

哦哦对的，是我自己没仔细看，在原字符串后加上一位就对了。
楼主的代码确实是简练！
不过对于我来说，不改动原字符串更容易理解 ：

:strlen <stringVarName> [retvar] 
:: 思路： 二分回溯联合查表法
:: 说明： 所求字符串大小范围 0K ~ 8K；
::    stringVarName ---- 存放字符串的变量名
::    retvar      ---- 接收字符长度的变量名
setlocal enabledelayedexpansion
set "$=!%1!"
set N=&for %%a in (4096 2048 1024 512 256 128 64 32 16)do if !$:~%%a!. NEQ . set/aN+=%%a&set $=!$:~%%a!
set $=!$!!$!100f0e0d0c0b0a090807060504030201
set/aN+=0x!$:~32,2!&set/aN+=0x!$:~16,1!
endlocal&If %2. neq . (set/a%2=%N%)else echo %N%
复制代码

CrLf

回复 13# wankoilz


    看来个人有个人的习惯写法，我比较倾向用其他手段代替补位，这样可以兼容最长的变量（除了 , 这个变态的变量名），不过代码就稍显冗长了：

@echo off&setlocal enabledelayedexpansion

for /l %%a in (1 1 8189) do set s=!s!;
call :strlen s len

echo len=%len%
pause&exit/b

:strlen <stringVarName> [retvar] 
:: 思路： 二分回溯联合查表法
:: 说明： 所求字符串大小范围 0K ~ 8K；
::    stringVarName ---- 存放字符串的变量名
::    retvar      ---- 接收字符长度的变量名
setlocal enabledelayedexpansion&set $=!%1!&set N=0
if defined $ (
	for %%a in (4095 2047 1023 511 255 127 63 31 15)do if !$:~%%a!. NEQ . set/aN-=~%%a&set $=!$:~%%a,-1!
	set $=!$!fedcba987654321&set/aN+=0x!$:~15,1!
)
endlocal&If %2. neq . (set %2=%N%)else echo %N%
复制代码

wankoilz

这样的话，fedcba9876543210中的0都可以省了。
不过我还是觉得用4096  2048……更好，因为每个数字正好对应于二进制上的一位，理解和计算都更好一点。