Board logo

标题: [数值计算] 批处理求字符串长度的表驱动算法 [打印本页]

作者: plp626    时间: 2009-10-7 06:24     标题: 批处理求字符串长度的表驱动算法


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

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

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

算法思想为ifexist的如下代码
  1. 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 编辑 ]
作者: 随风    时间: 2009-10-7 06:48

626兄一发帖都是好帖啊,没有一个不让人看得“头痛”的 ^_^
作者: plp626    时间: 2009-10-7 07:00

原帖由 随风 于 2009-10-7 06:48 发表
626兄一发帖都是好帖啊,没有一个不让人看得“头痛”的 ^_^


我喜欢拿来主义...

至今没有一个算法的思想 从头到脚全是原创的

[ 本帖最后由 plp626 于 2009-10-12 17:42 编辑 ]
作者: 随风    时间: 2009-10-7 07:20

懂得拿来已经是很高境界了,全部原创,兄的追求太高了吧。。。
作者: zqz0012005    时间: 2009-10-7 09:29

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

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

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


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

[ 本帖最后由 zqz0012005 于 2009-10-7 10:12 编辑 ]
作者: plp626    时间: 2009-10-7 13:09

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

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

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


字符截 ...


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

微软的cmd有点像一个cpu,我们用的命令就是他的基本指令,如果这样理解,cmd功能很弱也无可厚非,
作者: 基拉freedom    时间: 2009-10-7 20:26

我有一个很傻很天真的想法
真的很傻
把字符先放入一个文件 然后用dir命令查找字节
  1. D:\>echo 123456789+>111.txt
  2. D:\>dir 111.txt
  3. 驱动器 D 中的卷没有标签。
  4. 卷的序列号是 48F9-7985
  5. D:\ 的目录
  6. 2009-10-07  20:25                12 111.txt
  7.                1 个文件             12 字节
复制代码
然后 字节数-2
然后我又很傻得做了一个
  1. @echo off&setlocal enabledelayedexpansion
  2. set /p s=请输入字符:
  3. echo %s%>12as.txt
  4. 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 编辑 ]
作者: zqz0012005    时间: 2009-10-7 20:41     标题: 回复 7楼 的帖子

唉,中英文混合怎么办?
作者: plp626    时间: 2009-10-7 20:47

  1. echo ”%~1“>%tmp%\$
  2. for %%a in (%tmp%\$)do set/a byte=%%~za-4
复制代码
这个是求字符串的字节数 :sizeof("string") =/= strlen("string")

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

[ 本帖最后由 plp626 于 2009-10-7 20:49 编辑 ]
作者: 基拉freedom    时间: 2009-10-7 20:59

........这倒是 一个8位 一个16位.........哎
作者: 523066680    时间: 2009-10-7 21:17

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


回复前几楼说的:

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

[ 本帖最后由 523066680 于 2009-10-7 21:19 编辑 ]
作者: 基拉freedom    时间: 2009-10-7 21:32

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

请问这个有测试过吗?
  1. :: strlen1024
  2. setlocal enabledelayedexpansion
  3. ::::::::::::如果你觉得下面三句比较耗时间,可以直接把list的值【2048字节】求出然后用set命令赋值::::::::::::::::
  4. 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
  5. set z=10&(for %%a in (%zz:~20%)do set/a %%a=z,z+=1)&set "list="
  6. for %%a in (%zz%)do for %%b in (%zz%)do set list=!list!%%a%%b
  7. :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
  8. rem 使用范例 // 【耗费的时间单位仅为 2.3】
  9. set s=your strings
  10. set "s=!list!!s!!s!"&set/a len=!s:~-2048,1!*10+!s:~-2047,1!
  11. rem 老帖为“set "s=!list!!s!!s!"&set l=!s:~-2048,2!&set/a len=!l:~,1!*10+!l:~-1!”
  12. echo %len%
复制代码
1、超过31个字符就胡乱显示了
2、长度为28个字符显示为2147483647
作者: garyng    时间: 2011-11-9 21:14

妙!
折半法 第一次听过
快速 简洁!
作者: abcdshenji    时间: 2011-11-9 23:23

  1. :: strlen1024
  2. setlocal enabledelayedexpansion
  3. ::::::::::::如果你觉得下面三句比较耗时间,可以直接把list的值【2048字节】求出然后用set命令赋值::::::::::::::::
  4. 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
  5. set z=10&(for %%a in (%zz:~20%)do set/a %%a=z,z+=1)&set "list="
  6. for %%a in (%zz%)do for %%b in (%zz%)do set list=!list!%%a%%b
  7. :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
  8. rem 使用范例 // 【耗费的时间单位仅为 2.3】
  9. set s=your strings
  10. set "s=!list!!s!!s!"&set/a len=!s:~-2048,1!*10+!s:~-2047,1!
  11. rem 老帖为“set "s=!list!!s!!s!"&set l=!s:~-2048,2!&set/a len=!l:~,1!*10+!l:~-1!”
  12. echo %len%
复制代码
其中的“(for %%a in (%zz:~20%)do set/a %%a=z,z+=1)”这句,似乎多余了。。
作者: yyykkkyyyy    时间: 2011-11-10 10:57

本帖最后由 yyykkkyyyy 于 2011-11-10 11:15 编辑

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

回复 1# plp626


    像极了秤子上的游标,叫“游标法”更形象
作者: tiandyoin    时间: 2023-4-11 00:37

回复 14# garyng

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




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