[数值计算] 批处理求字符串长度的表驱动算法

plp626

求字符串长度在许多代码中是很关键的子过程

现在综合起来比较好的算是[折半法点击查看代码] 【不用自行管理变量，且效率较高】
判断1000以内长度的字符串 耗费时间单位25，而其他的使用goto命令的耗费时间都和他不在一个数量级上!

对于非常频繁的求字符串长度的代码，还有更好的算法，本帖为大家隆重推荐ifexist的一个小代码，我只是对他的思想做了延伸

算法思想为ifexist的如下代码

set s=%19876543210&echo the length of "%1" is %s:~9,1%
复制代码

查阅相关资料，此种思想算法属于 表驱动算法 范畴


只要你理解预处理的机制，代码是支持所有特殊字符的

:: strlen256 // 最大字符串长度256
setlocal enabledelayedexpansion

::::::::::::如果你觉得下面两句比较耗时间，可以直接把list的值【512字节】求出然后用set命令赋值::::::::::::::::
set zz=0 1 2 3 4 5 6 7 8 9 a b c d e f&set "list="
for %%a in (%zz%)do for %%b in (%zz%)do set list=!list!%%a%%b
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
rem 使用范例 // 【耗费的时间单位仅为 2.3】
set s=your strings
set "s=!list!!s!!s!"&set/a len=0X!s:~-512,2!
echo %len%

下面代码支持字符串的最大长度为1024

:: strlen1024
setlocal enabledelayedexpansion

::::::::::::如果你觉得下面三句比较耗时间，可以直接把list的值【2048字节】求出然后用set命令赋值::::::::::::::::
set zz=0 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v
set z=10&(for %%a in (%zz:~20%)do set/a %%a=z,z+=1)&set "list="
for %%a in (%zz%)do for %%b in (%zz%)do set list=!list!%%a%%b
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

rem 使用范例 // 【耗费的时间单位仅为 2.3】
set s=your strings
set "s=!list!!s!!s!"&set/a len=!s:~-2048,1!*10+!s:~-2047,1!
rem 老帖为“set "s=!list!!s!!s!"&set l=!s:~-2048,2!&set/a len=!l:~,1!*10+!l:~-1!”
echo %len%

对于更长的字符串，用类似的方法可以扩充到任意长度[cmd支持最大命令行8K]，
根据实际情况需要选定list字符串作为“表”，表的字节数随待求字符串的最大长度 基本上是线性递增的

----------------------------------------------------------- 更新一下 --------------------------------------------------------

关于生成“list表”有快速方法，下面代码生成表耗时用18~25个时间单位
【一个时间单位为一次set 赋值所耗费的时间，点此查看详情】

rem 生成strlen256的那个表：
@setlocal enabledelayedexpansion
@set zz= 0 1 2 3 4 5 6 7 8 9 a b c d e f&set list=&for %%a in (!zz!)do set list=!list!!zz: =%%a!
@echo %list%>list.txt

::strlen1024
setlocal enabledelayedexpansion
rem 此表字节数3072，如果嫌太大可以使用原帖那个strlen1024的表，字节数2048
set zz= 0 1 2 3 4 5 6 7 8 9 a b c d e f&set lt=&set "list="
for %%a in (%zz%)do set "lt=!lt!!zz: = %%a!"
for %%b in (%zz:~0,8%)do set "list=!list!!lt: =%%b!"
rem 使用范例
set s=your strings
set "s=!list!!s!!s!!s!"&set/a len=0X!s:~-3072,3!
echo %len%

[ 本帖最后由 plp626 于 2009-10-13 11:22 编辑 ]

tiandyoin

回复 14# garyng

算法效率:
    二分法(折半法): O(logn)
    表驱动(游标法): O(n)=O(根号n*根号n)
    遍历法: O(n)

tiandyoin

回复 1# plp626


    像极了秤子上的游标，叫“游标法”更形象

yyykkkyyyy

呵呵，开眼界啦，早有个接着“傻”的求字节数的想法哪位来点评一下：
for /f "delims=:" %%i in ('(echo mystrings^&echo y^)^|findstr/o ".*"')do set/a len=%%i-3

abcdshenji

:: strlen1024
setlocal enabledelayedexpansion

::::::::::::如果你觉得下面三句比较耗时间，可以直接把list的值【2048字节】求出然后用set命令赋值::::::::::::::::
set zz=0 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v
set z=10&(for %%a in (%zz:~20%)do set/a %%a=z,z+=1)&set "list="
for %%a in (%zz%)do for %%b in (%zz%)do set list=!list!%%a%%b
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

rem 使用范例 // 【耗费的时间单位仅为 2.3】
set s=your strings
set "s=!list!!s!!s!"&set/a len=!s:~-2048,1!*10+!s:~-2047,1!
rem 老帖为“set "s=!list!!s!!s!"&set l=!s:~-2048,2!&set/a len=!l:~,1!*10+!l:~-1!”
echo %len%
复制代码

其中的“(for %%a in (%zz:~20%)do set/a %%a=z,z+=1)”这句，似乎多余了。。

garyng

妙！
折半法 第一次听过
快速 简洁！

JooKin

请问这个有测试过吗？

:: strlen1024
setlocal enabledelayedexpansion

::::::::::::如果你觉得下面三句比较耗时间，可以直接把list的值【2048字节】求出然后用set命令赋值::::::::::::::::
set zz=0 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v
set z=10&(for %%a in (%zz:~20%)do set/a %%a=z,z+=1)&set "list="
for %%a in (%zz%)do for %%b in (%zz%)do set list=!list!%%a%%b
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

rem 使用范例 // 【耗费的时间单位仅为 2.3】
set s=your strings
set "s=!list!!s!!s!"&set/a len=!s:~-2048,1!*10+!s:~-2047,1!
rem 老帖为“set "s=!list!!s!!s!"&set l=!s:~-2048,2!&set/a len=!l:~,1!*10+!l:~-1!”
echo %len%
复制代码

1、超过31个字符就胡乱显示了
2、长度为28个字符显示为2147483647

基拉freedom

...........大家
有没有什么办法把中文字符替换掉
或者把所有的字符都替换成一个.......................
用字节计算 只需把中文或其他占用位不同的字符换掉就好了 不过还没找到好方法的说

523066680

自第一次见到批处理收集(2007) 后又过了两年
批处理有了崛起式的发展，各位，谁有时间进行新的批处理大全收集？
我想想哈，要不交给技术组……


回复前几楼说的：

要不两种方法都算一次 作为验证？或者给出两个结果：一个字节数，一个字符数

[ 本帖最后由 523066680 于 2009-10-7 21:19 编辑 ]

基拉freedom

........这倒是 一个8位 一个16位.........哎

plp626

 
echo ”%~1“>%tmp%\$
for %%a in (%tmp%\$)do set/a byte=%%~za-4
复制代码

这个是求字符串的字节数 ：sizeof("string") =/= strlen("string")

但是话说回来，对于纯英文的字符，这个代码不是一般的健壮，

[ 本帖最后由 plp626 于 2009-10-7 20:49 编辑 ]

zqz0012005

唉，中英文混合怎么办？

基拉freedom

我有一个很傻很天真的想法
真的很傻
把字符先放入一个文件 然后用dir命令查找字节

D:\>echo 123456789+>111.txt

D:\>dir 111.txt
驱动器 D 中的卷没有标签。
卷的序列号是 48F9-7985

D:\ 的目录

2009-10-07  20:25                12 111.txt
               1 个文件             12 字节
复制代码

然后 字节数-2
然后我又很傻得做了一个

@echo off&setlocal enabledelayedexpansion
set /p s=请输入字符:
echo %s%>12as.txt
for /f "skip=6 tokens=3" %%i in ('dir 12as.txt') do (set /a a=%%i-2&echo !a!&pause&exit)
复制代码

特殊字符支持不能

[ 本帖最后由 基拉freedom 于 2009-10-7 20:36 编辑 ]

plp626

原帖由 zqz0012005 于 2009-10-7 09:29 发表
算法果然深奥而强大！只是我没怎么接触。。。

变量的最大长度是8KB，用这个方法的缺点是导致被计算字符串长度要再次受到限制。

这种一维完全表太消耗字符串了，要设法换成多维数组之类的另一种表。


字符截 ...

此类算法的思想本质就是根据实际情况选表，最通用的表，一定是占内存最大的；

微软的cmd有点像一个cpu，我们用的命令就是他的基本指令，如果这样理解，cmd功能很弱也无可厚非，

zqz0012005

算法果然深奥而强大！只是我没怎么接触。。。

变量的最大长度是8KB，用这个方法的缺点是导致被计算字符串长度要再次受到限制。

这种一维完全表太消耗字符串了，要设法换成多维数组之类的另一种表。


字符截取功能本身就是要先计算长度的（特别是出现负数），为什么M$不把这个长度作为某种结果给出呢？%var::length%。。。

[ 本帖最后由 zqz0012005 于 2009-10-7 10:12 编辑 ]