首页 文章

优化批处理脚本中实现的暴力算法

提问于
浏览 次
1

此批处理脚本的目的是实现一个简单的Brute Force算法，以便生成所有可能的10个字母数字字符长字符串，字符与下一个字符之间不会重复 .

set alphanumerics=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,0,1,2,3,4,5,6,7,8,9

for %%l in (%alphanumerics%) do (
    for %%m in (%alphanumerics%) do (
        for %%n in (%alphanumerics%) do (
            for %%o in (%alphanumerics%) do (
                for %%p in (%alphanumerics%) do (
                    for %%q in (%alphanumerics%) do (
                        for %%r in (%alphanumerics%) do (
                            for %%s in (%alphanumerics%) do (
                                for %%t in (%alphanumerics%) do (
                                    for %%u in (%alphanumerics%) do (

if %%u NEQ %%t (
    if %%t NEQ %%s (
        if %%s NEQ %%r (
            if %%r NEQ %%q (
                if %%q NEQ %%p (
                    if %%p NEQ %%o (
                        if %%o NEQ %%n (
                            if %%n NEQ %%m (
                                if %%m NEQ %%l (
                                    echo %%l%%m%%n%%o%%p%%q%%r%%s%%t%%u >> output.txt
                                )
                            )
                        )
                    )
                )
            )
        )
    )
)
                                    )
                                )
                            )
                        )
                    )
                )
            )
        )
    )
)

这个脚本的主要问题是，为了完成任务所需的时间量仍然非常大，因为尽管各种 if 分支正在过滤最终输出，但仍然会由 for 块计算出数千个无效组合 . 因此，我真的想改进整个脚本，以最好的方式使用所有计算能力而不浪费它 . 我正在考虑在并行进程之间分配整个算法 . 或者，基于2的字符串生成器的强大功能：在第一步中，脚本可以生成并存储所有可能的字符对 .

for %%x in (%alphanumerics%) do (
    for %%y in (%alphanumerics%) do (
        if %%y NEQ %%x (
            echo.%%x%%y >> output.txt
        )
    )
)

之后，在第二步中，它可以使用先前生成的伴随来匹配它们，产生四个字符长的字符串;然后，八个字符长等

for /f %%v in (output.txt) do (
    set firstvar=%%v
    set firstchar=!firstvar:~1!
    ;First character of the listed couples

    for /f "skip=1" %%w in (output.txt) do (
        set secondvar=%%w
        set secondchar=!secondvar:~0,1!
        ;Last character of the listed couples

        if !secondchar! NEQ !firstchar! (
            echo.!firstvar!!secondvar! >> output_2.txt
        )
    )   
)

总之，我如何才能改进这个算法以节省时间？

algorithm batch-file brute-force

3 回答

  • 4

    下面的解决方案比你的快得多，也许这是在批处理文件中执行此操作的最快方法 .

    @echo off
setlocal EnableDelayedExpansion

set "alphanumerics=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,X,Y,Z,0,1,2,3,4,5,6,7,8,9"

(for %%a in (%alphanumerics%) do (
   for %%b in (%alphanumerics%) do if %%a neq %%b (
      for %%c in (%alphanumerics%) do if %%b neq %%c (
         for %%d in (%alphanumerics%) do if %%c neq %%d (
            for %%e in (%alphanumerics%) do if %%d neq %%e (
               for %%f in (%alphanumerics%) do if %%e neq %%f (
                  for %%g in (%alphanumerics%) do if %%f neq %%g (
                     for %%h in (%alphanumerics%) do if %%g neq %%h (
                        for %%i in (%alphanumerics%) do if %%h neq %%i (
                           for %%j in (%alphanumerics%) do if %%i neq %%j (
                              echo %%a%%b%%c%%d%%e%%f%%g%%h%%i%%j
                           )
                        )
                     )
                  )
               )
            )
         )
      )
   )
)) > output.txt
    回复于
  • 1
    26 lowercase + 26 uppercase + 10 digits = 62 characters

    如果每个位置有61个字符（邻居限制），除了第一个不受前一个字符限制的字符外，则必须生成

    (61^9)*62 = 725037057755716742  combinations.

    每秒生成1000000个组合，您需要22991年才能生成完整列表，并且需要在每个值后有10个字符和CRLF终结符，7728 PB的存储空间 .

    但......

    NOTE 1
    脚本已编辑 . 由于JosefZ指出原始代码失败，因为批处理文件中的字符串替换不区分大小写（我忘记了） . 代码已更改为面对问题，包括填充程序，以便能够区分较低和较高的字符，但不包括在输出中 . 无论如何，在答案的最后可以找到原始的错误代码 .

    @echo off
    setlocal enableextensions disabledelayedexpansion

    set "alphanumerics=,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z"
    set "alphanumerics=%alphanumerics%,!_!A,!_!B,!_!C,!_!D,!_!E,!_!F,!_!G,!_!H,!_!I,!_!J,!_!K,!_!L,!_!M,!_!N,!_!O,!_!P,!_!Q,!_!R,!_!S,!_!T,!_!U,!_!V,!_!W,!_!X,!_!Y,!_!Z"
    set "alphanumerics=%alphanumerics%,0,1,2,3,4,5,6,7,8,9"
    set "_="

    rem Just for testing : 4*(3^9) = 78732 combinations
    set "alphanumerics=,a,b,!_!A,!_!B"

    setlocal enabledelayedexpansion
    for %%a in (!alphanumerics!
    ) do for %%b in (!alphanumerics:^,%%a^=!
    ) do for %%c in (!alphanumerics:^,%%b^=!
    ) do for %%d in (!alphanumerics:^,%%c^=!
    ) do for %%e in (!alphanumerics:^,%%d^=!
    ) do for %%f in (!alphanumerics:^,%%e^=!
    ) do for %%g in (!alphanumerics:^,%%f^=!
    ) do for %%h in (!alphanumerics:^,%%g^=!
    ) do for %%i in (!alphanumerics:^,%%h^=!
    ) do for %%j in (!alphanumerics:^,%%i^=!
    ) do echo(%%a%%b%%c%%d%%e%%f%%g%%h%%i%%j

    执行代码时， !_! 将包含在 for 可替换参数中，但由于变量 _ 为空，它将不包含在 echo 命令的输出中，替换为延迟扩展解析器阶段中的空字符串 .

    这是答案中的原始（和错误）代码 . 不能正确处理大小写字符串替换 .

    @echo off
    setlocal enableextensions enabledelayedexpansion

    rem Changed to include a starting comma
    set "alphanumerics=,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,X,Y,Z,0,1,2,3,4,5,6,7,8,9"

    for %%a in (%alphanumerics%
    ) do for %%b in (!alphanumerics:^,%%a^=!
    ) do for %%c in (!alphanumerics:^,%%b^=!
    ) do for %%d in (!alphanumerics:^,%%c^=!
    ) do for %%e in (!alphanumerics:^,%%d^=!
    ) do for %%f in (!alphanumerics:^,%%e^=!
    ) do for %%g in (!alphanumerics:^,%%f^=!
    ) do for %%h in (!alphanumerics:^,%%g^=!
    ) do for %%i in (!alphanumerics:^,%%h^=!
    ) do for %%j in (!alphanumerics:^,%%i^=!
    ) do echo %%a%%b%%c%%d%%e%%f%%g%%h%%i%%j

    NOTE 2
    在写完之后我看到这是JosefZ's answer中的相同方法，但由于在过程中没有存储变量，它应该稍快一些 .

    回复于
  • 4

    您可以提前排除可能的邻居匹配，如下所示 . 请注意， alphanumerics 变量中的密码种子被剪切，输出仅缩小到每个万字，仅用于演示目的 .

    @ECHO OFF
SETLOCAL EnableExtensions EnableDelayedExpansion
set "alphanumerics=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,X,Y,Z,0,1,2,3,4,5,6,7,8,9,"
set "alphanumerics=a,b,c,d,e,A,B,C,D,E,0,1,2,3,4,5,"
set "alphanumerics=a,b,c,A,B,C,0,1,2,"
set "alphanumerics=a,b,A,B,0,1,"
set /A "_counter=0"
rem > output.txt (
for %%l in (%alphanumerics%) do (
    set "al=!alphanumerics:%%l,=!"
    for %%m in (!al!) do (
        set "am=!alphanumerics:%%m,=!"
        for %%n in (!am!) do (
            set "an=!alphanumerics:%%n,=!"
            for %%o in (!an!) do (
                set "ao=!alphanumerics:%%o,=!"
                for %%p in (!ao!) do (
                    set "ap=!alphanumerics:%%p,=!"
                    for %%q in (!ap!) do (
                        set "aq=!alphanumerics:%%q,=!"
                        for %%r in (!aq!) do (
                            set "ar=!alphanumerics:%%r,=!"
                            for %%s in (!ar!) do (
                                set "as=!alphanumerics:%%s,=!"
                                for %%t in (!as!) do (
                                    set "at=!alphanumerics:%%t,=!"
                                    for %%u in (!at!) do (

          rem echo %%l%%m%%n%%o%%p%%q%%r%%s%%t%%u
          set /A "_counter+=1"
          set /A "_inter=_counter %% 100000"
          if !_inter! EQU 0 echo %%l%%m%%n%%o%%p%%q%%r%%s%%t%%u !_counter!

                                    )
                                )
                            )
                        )
                    )
                )
            )
        )
    )
)
echo %_counter%
ENDLOCAL
goto :eof

    但是，我担心我们没有足够的时间（以及磁盘空间）来完成您的任务，因为迭代计数呈指数级增长甚至更快！

    有 set "alphanumerics=a,b,A,B,0,1," 的可能密码（在几分钟内找到） . 要查看增长时间（和空间），以下是使用 set "alphanumerics=a,b,c,A,B,C,0,1,2," （密码种子中只有三个字符 c,C,2, 更多）获得的结果的摘录：在超过 ten million iterations 之后仍然具有前导 a ...

    acbcB2A21A 9600000
acbAcA2ABc 9700000
acbA121A1A 9800000
acbCB1aBCA 9900000
acb0bcAcba 10000000
acb01abCA1 10100000
acb1c0AcbA 10200000
acb12cABC2 10300000
acb2BacB2b 10400000
acAba0Bc02 10500000
^CacAbAB1bCb 10536175
Terminate batch job (Y/N)? y
    回复于

相关问题