java 如何缩短我的(非常基本的)蛮力算法的处理时间?

idv4meu8  于 2023-03-16  发布在  Java
关注(0)|答案(5)|浏览(168)

我正在学习java atm,我有点困在当前的任务,我的教练昨天给了我...
练习是:
1.创建一个4位数的密码(就像字符串变量一样)。(允许0-9之间的数字和一个或多个以下特殊字符:'!','#','%')
1.通过检查所有可能性,找到一种强行破解密码的方法。
1.测量并输出处理所需的时间。
1.此外,输出查找密码所需的“尝试”次数。
(My培训师说我应该尽可能少地使用方法,因为我现在甚至还不知道如何编写方法或如何使用类等。)
我设法让它工作,但在现在的情况下,它需要大约60毫秒才能通过循环。我的教练现在告诉我,我应该试着让它处理得更快,这样最少需要大约20毫秒。
我已经知道是什么让我的代码变慢了。这是因为我总是检查所有的可能性,把它们都添加到一个ArreyList中,然后我检查,如果pw与ArreyList中的其中一个可能性匹配。浪费时间。现在我的目标是像以前一样检查所有的可能性,但只是直到找到密码。之后,它应该会停止循环。这样它也停止添加其余不必要的组合。我试了又试,但现在我决定打电话求助:)
这是我的准则

import java.util.ArrayList;
        import java.util.Scanner;

        public class trynew {
        public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);

        char[] digits = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '#', '!', '%'};

        System.out.println("\nPlease create 4 digit password. Allowed are numbers between 0-9 and following characters: #,!,%");

        String passw = scn.nextLine();

        ArrayList<String> check_it = new ArrayList<String>();

        long start1 = System.currentTimeMillis();

        for (int i = 0; i < digits.length; i++) {
            for (int j = 0; j < digits.length; j++) {
                for (int k = 0; k < digits.length; k++) {
                    for (int l = 0; l < digits.length; l++) {
                        check_it.add(digits[i] + "" + digits[j] + "" + digits[k] + "" + digits[l]);
                    }
                }
            }
        }

        long end1 = System.currentTimeMillis();

        for (String sv : check_it) {
            if (sv.equals(passw)) {
                System.out.println("\nThe Password is: " + sv);
                System.out.println("It took " + check_it.indexOf(sv) + " tries, to find the password.");
            }
        }
        System.out.println("Process time was " + (end1 - start1) + " milliseconds.");

        }
    }



My approach  was to make the loop like that:

    for (int i = 0; i < digits.length; i++) { 
        for (int j = 0; j < digits.length; j++) {
            for (int k = 0; k < digits.length; k++) {
                for (int l = 0; l < digits.length; l++) {

                   if (!(digits[i] + "" + digits[j] + "" + digits[k] + "" + digits[l]).equals(passw)){
                        check_it.add(digits[i] + "" + digits[j] + "" + digits[k] + "" + digits[l]);
                    }

                }
            }
        }
    }

然后我尝试使用while循环代替if,尝试设置布尔值等。我还设法使它只添加组合,直到找到pw,但不知何故,处理时间不会减少:/
我之所以要把连击加到check_it ArreyList里面,是因为不然的话,我不知道怎么得到它尝试的次数,直到找到。。。
有没有人能帮帮我,或者戳我正确的方向?!谢谢&问候!

4szc88ey

4szc88ey1#

这是我想到的。

private static final char[] digits = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '#', '!', '%'};

public static int guessPw(String pw) {
    int attempts = 0;
    char [] word = new char[pw.length()];
    for (char a : digits) {
        word[0] = a;
        for (char b : digits) {
            word[1] = b;
            for (char c : digits) {
                word[2] = c;
                for (char d : digits) {
                    word[3] = d;
                    attempts++;
                    if (pw.equals(String.valueOf(word))) {
                        return attempts;
                    }
                }
            }
        }
    }
    return -1;
}

public static void timeAttempt(String pw) {     
    long start = System.nanoTime();
    int attempts = guessPw(pw);

    
    System.out.println(String.format("It took %dms and %d attempts to guess '%s'", TimeUnit.MILLISECONDS.toSeconds(System.nanoTime() - start), attempts, pw));
}
public static void main(String[] args) {
    timeAttempt("0000");
    timeAttempt("%%%%");
}
plupiseo

plupiseo2#

这段代码应该可以工作。它只是在密码被找到时中断每个循环。

int tries = 0;
   boolean found = false;
   for (int i = 0; i < digits.length; i++) {
            for (int j = 0; j < digits.length; j++) {
                for (int k = 0; k < digits.length; k++) {
                    for (int l = 0; l < digits.length; l++) {
                        tries++;
                        if ((digits[i] + "" + digits[j] + "" + digits[k] + "" + digits[l]).equals(passw)) {
                           found = true;
                           break;
                        }
                    }
                    if (found)
                      break;
                }
               if (found)
                  break;
            }
            if (found)
                  break;
        }

我不建议使用这段代码!它相当粗略。为什么不把for循环变成一个函数呢?当你找到密码时,你可以从那里返回尝试。但是我认为你可以自己解决这个问题:)
编辑:我会给予你一个没有函数的解决方案的提示。你觉得这个while循环怎么样?

while(!(digits[i] + "" + digits[j] + "" + digits[k] + "" + digits[l]).equals(passw))

在那里你只需要按照正确的顺序“生长”l,k,j和i:)

fhg3lkii

fhg3lkii3#

和Ryan发布的非常相似。基本上你想避免创建一个字符串。
在这里,我将输入的密码转换为一个char数组,并使用Arrays.equals()将输入的密码与生成的密码进行比较:

public static void main(String[] args) {       
    Scanner scn = new Scanner(System.in);

    char[] digits = {'0', '1', '2', '3', '4', '5', '6', 
                     '7', '8', '9', '#', '!', '%'};

    System.out.println("\nPlease create 4 digit password.");
    System.out.println("Allowed are numbers between 0-9 and following characters: #,!,%");
    System.out.print("Password: ");
    
    String response = scn.nextLine();
    char[] password = response.toCharArray();
    
    long start1 = System.currentTimeMillis();

    int counter = 0;
    char[] pw = new char[4];
    boolean foundIt = false;
    for (int i = 0; i < digits.length && !foundIt; i++) {
        pw[0] = digits[i];
        for (int j = 0; j < digits.length && !foundIt; j++) {
            pw[1] = digits[j];
            for (int k = 0; k < digits.length && !foundIt; k++) {
                pw[2] = digits[k];
                for (int l = 0; l < digits.length && !foundIt; l++) {
                  counter++;
                  pw[3] = digits[l];
                  foundIt = Arrays.equals(pw, password);
                }
            }
        }
    }
  
    long end1 = System.currentTimeMillis();

    System.out.println("\nThe Password is: " + response);
    System.out.println("It took " + counter + " tries, to find the password.");

    System.out.println("Process time was " + (end1 - start1) + " milliseconds.");
  }
ubby3x7f

ubby3x7f4#

它的处理速度如此之慢的原因是因为你所有的代码都是在一个线程中运行的。你可以通过使暴力代码多线程化来大大减少整体处理时间。
应用程序运行缓慢的另一个原因是,它使用了许多嵌套循环来确定digits的所有可能组合。与其使用这些嵌套循环,不如计算digits的排列。
一旦你有了所有可能的排列列表,你可以使用java 8的parallelStream()anyMatch()来检查哪个排列以多线程的方式匹配密码。换句话说,计算机将能够 * 同时 * 匹配2个或更多的排列与pass,这将大大减少处理时间。下面是一个使用parallelStream()/anyMatch()的例子。

AtomicInteger threadSafeCounter = new AtomicInteger(); //Always use a thread safe integer when multiple threads will be manipulating it. This is to avoid race conditions.

    char[] digits = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '#', '!', '%'};

    Scanner scn = new Scanner(System.in);

    System.out.println("\nPlease create 4 digit password. Allowed are numbers between 0-9 and following characters: #,!,%");

    String passw = scn.nextLine();

List<String> permutationList = new ArrayList(); //Calculate the 4-digit permutations from `digits` and add them to this list.

    long start1 = System.currentTimeMillis();
    permutationList.parallelStream().anyMatch(combination -> {
        threadSafeCounter.incrementAndGet();
        if(combination.equals(passw)){
            System.out.println("\nthe password is " + passw);
            System.out.println("It took " + threadSafeCounter.get() + " tries, to find the password.");
            return true;
        }
        else return false;
    });

    long end1 = System.currentTimeMillis();

    System.out.println("Process time was " + (end1 - start1) + " milliseconds.");

你可以在in this SO thread中找到一个关于如何从digits生成排列的例子。如果你在前面提到的SO线程中修改Subash发布的代码,排列生成代码本身也可以被多线程化。要做到这一点,你需要使用Fork/Join framework
EDIT:Heres a nice article解释了permutationscombinations之间的区别,在我的例子中我计算排列而不是组合的原因是因为在这种情况下顺序/排列很重要。

w41d8nur

w41d8nur5#

您在找到密码后立即跳出循环的方法是朝着正确方向迈出的一步。但是,您当前代码的问题在于,它仍然会在检查是否找到密码之前生成所有可能的组合,这可能会相当耗时。
相反,你可以修改你的循环来检查每一个生成的组合,并在找到密码后跳出循环。下面是你可以做到这一点的一种方法:

String foundPassword = null;
int numTries = 0;

long startTime = System.currentTimeMillis();

for (int i = 0; i < digits.length; i++) {
    for (int j = 0; j < digits.length; j++) {
        for (int k = 0; k < digits.length; k++) {
            for (int l = 0; l < digits.length; l++) {
                String combination = digits[i] + "" + digits[j] + "" + digits[k] + "" + digits[l];
                numTries++;
                if (combination.equals(passw)) {
                    foundPassword = combination;
                    break;
                }
            }
            if (foundPassword != null) {
                break;
            }
        }
        if (foundPassword != null) {
            break;
        }
    }
    if (foundPassword != null) {
        break;
    }
}

long endTime = System.currentTimeMillis();
long elapsedTime = endTime - startTime;

if (foundPassword != null) {
    System.out.println("\nThe Password is: " + foundPassword);
    System.out.println("It took " + numTries + " tries, to find the password.");
} else {
    System.out.println("Password not found.");
}
System.out.println("Process time was " + elapsedTime + " milliseconds.");

相关问题